核心内容摘要
78立穿13解锁生活无限可能,从此刻开始!
原文地址https://wiki.postgresql.org/wiki/Sudoku_solver数独求解器兼容的 PostgreSQL 版本
0编写语言SQL依赖项无这是我编写的一个不算特别快的数独求解器。
输入格式为‘_’ 代表空单元格而 ‘b’ 到 ‘j’ 代表数字 1…9。
棋盘以列优先顺序存储这意味着字符串的前 9 个字符编码了第一列从上到下随后的 9 个字符是第二列依此类推。
提示你可以通过使用 ksudoku 保存游戏来创建新的数独谜题。
withrecursive board(b,p)as(-- 以列优先顺序表示的数独棋盘因此可以使用 substr() 来获取某一列values(__g_cd__bf_____j____c__e___c__i___jd__b__h___id____e__g__b__f_e_f____g____j_h__c_::char(
,
unionallselectb,pfrom(-- 生成候选棋盘selectoverlay(b placing new_charfromstrpos(b,_)for
::char(
,strpos(b,_),new_charfromboard,(selectchr(nascii(b))fromgenerate_series(0,
n)new_char_table(new_char)wherestrpos(b,_)
r(b,p,new_char)where-- 确保新字符在其列中不重复出现-- 有两个检查因为我们要排除 p 自身的位置strpos(substr(b,1(p-
/9*9,(p-
%
,new_char)0andstrpos(substr(b,p1,8-(p-
%
,new_char)0and-- 确保新字符在其行中不重复出现new_charnotin(selectsubstr(b,1i*9(p-
%9,
fromgenerate_series(0,
iwherep1i*9(p-
%
and-- 确保新字符在其所在的 3x3 宫内不重复出现new_charnotin(selectsubstr(b,1i%3i/3*9(p-
/27*27(p-
%9/3*3,
fromgenerate_series(0,
iwherep1i%3i/3*9(p-
/27*27(p-
%9/3*
)select-- 以下子查询用于以 \n 分隔的人类可读格式表示棋盘(selectstring_agg((selectstring_agg(chr(ascii(
ascii(substr(b,1yx*9,
)-ascii(b)),)rfromgenerate_series(0,
x),E\n)fromgenerate_series(0,
y)human_readable,b board,p depth,(selectcount(*)fromboard)stepsfromboardwherestrpos(b,_)0limit5000;此示例展示了如何使用递归公共表表达式Recursive CTE来通用地编码任何回溯算法步骤如下将初始情况置于递归 CTE 的union之前。
在UNION之后放置一个生成下一个可能候选值的查询。
在此查询中你将读取递归 CTE请确保仅读取未完成的候选方案方法是在该查询的where子句中指定此条件。
你可以并且很可能应该剪除无效的候选方案方法是将生成候选值的子查询包裹在另一个子查询中并使用剪除条件进行过滤。
剪枝很重要不仅是为了速度还因为 PostgreSQL 会存储此查询返回的每一行所有候选解直到不再需要为止你可能会用尽磁盘空间尽管在 PostgreSQL
2 中你可以使用temp_file_limit限制该空间或者使用单独的临时表空间。
最后在最外层递归 CTE 表中将提供所有候选方案。
如本例所示如果你剪除了所有无效的候选方案那么所有完整的候选方案也将是有效的解。
可能的状态空间将按广度优先搜索进行处理。