用SQL求解数独(Sudoku)

时间:2021-03-01 02:41:32

看来用XSLT解数独已经没有挑战性了, 因为XSLT是披着XML外衣的函数编程语言。所以闲人中的闲人们用新时代的汇编--SQL,来解决数独问题。当然不是SQL 92了,而是用了Oracle10g里介绍的MODEL语句。这么看来,邹键老大用SQL解简单算法题也不算离谱。:-D

Oracle的MODEL语句允许我们创建多维数组,并通过设定规则来处理数组,得到新的结果。规则本身可以递归。计算后数组本身不必被破坏。听上去是不是像用Oracle作后台的Excel?不过我提到过Excel也是函数编程系统么?用SQL解数独的基本思路就是用MODEL语句描述数独成立的规则,当应用select语句时,这些规则被执行,满足规则的数组也就是数独答案就被搜索出来了。

不过我还是对SQL兴趣不大。对Oracle更没有兴趣。只是觉得这种奇技淫巧有想象力,因而有意思。就好像有人用regex(不是严格意义的regular expression)解决数独问题一样:regex匹配是NP-complete问题,而数独也是。所有从regex规约到Sudoku肯定可行。于是我们为给定的数独谜面创建一坨字符串和一坨模式,用regex引擎匹配它们。字符串匹配成功的充要条件是该数独有解。