DeepSeek辅助总结postgresql wiki提供的数独求解器

原文地址：https://wiki.postgresql.org/wiki/Sudoku_solver
数独求解器

兼容的 PostgreSQL 版本
9.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(81),0)unionallselectb,pfrom(-- 生成候选棋盘：selectoverlay(b placing new_charfromstrpos(b,'_')for1)::char(81),strpos(b,'_'),new_charfromboard,(selectchr(n+ascii('b'))fromgenerate_series(0,8)n)new_char_table(new_char)wherestrpos(b,'_')>0)r(b,p,new_char)where-- 确保新字符在其列中不重复出现-- （有两个检查，因为我们要排除 p 自身的位置）：strpos(substr(b,1+(p-1)/9*9,(p-1)%9),new_char)=0andstrpos(substr(b,p+1,8-(p-1)%9),new_char)=0and-- 确保新字符在其行中不重复出现：new_charnotin(selectsubstr(b,1+i*9+(p-1)%9,1)fromgenerate_series(0,8)iwherep<>1+i*9+(p-1)%9)and-- 确保新字符在其所在的 3x3 宫内不重复出现：new_charnotin(selectsubstr(b,1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3,1)fromgenerate_series(0,8)iwherep<>1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3))select-- 以下子查询用于以 '\n' 分隔的人类可读格式表示棋盘：(selectstring_agg((selectstring_agg(chr(ascii('1')+ascii(substr(b,1+y+x*9,1))-ascii('b')),'')rfromgenerate_series(0,8)x),E'\n')fromgenerate_series(0,8)y)human_readable,b board,p depth,(selectcount(*)fromboard)stepsfromboardwherestrpos(b,'_')=0limit5000;

此示例展示了如何使用递归公共表表达式（Recursive CTE）来通用地编码任何回溯算法，步骤如下：

1. 将初始情况置于递归 CTE 的union之前。
2. 在UNION之后，放置一个生成下一个可能候选值的查询。在此查询中，你将读取递归 CTE；请确保仅读取未完成的候选方案，方法是在该查询的where子句中指定此条件。
3. 你可以（并且很可能应该）剪除无效的候选方案，方法是将生成候选值的子查询包裹在另一个子查询中，并使用剪除条件进行过滤。剪枝很重要，不仅是为了速度，还因为 PostgreSQL 会存储此查询返回的每一行（所有候选解），直到不再需要为止，你可能会用尽磁盘空间（尽管在 PostgreSQL 9.2+ 中，你可以使用temp_file_limit限制该空间，或者使用单独的临时表空间）。
4. 最后，在最外层，递归 CTE 表中将提供所有候选方案。如本例所示，如果你剪除了所有无效的候选方案，那么所有完整的候选方案也将是有效的解。

可能的状态空间将按广度优先搜索进行处理。