数独求解器

代码片段

插入排序

适用于 PostgreSQL

9.0+

用

SQL

依赖

无

由 我 编写的速度不快的数独求解器。输入格式：'_' 代表空单元格，'b' 到 'j' 代表 1 到 9。棋盘以列主序保存，这意味着第一列从上到下编码在字符串的前 9 个字符中，接下来的 9 个字符是第二列，依此类推。

提示：你可以使用 ksudoku 保存游戏以创建新的数独。

with recursive board(b, p) as (
  -- sudoku board expressed in column-major order, so substr() can be used to fetch a column
  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)
  union all select b, p from (
    -- generate boards:
    select overlay(b placing new_char from strpos(b, '_') for 1)::char(81), strpos(b, '_'), new_char
    from board, (select chr(n+ascii('b')) from generate_series(0, 8) n) new_char_table(new_char)
    where strpos(b, '_') > 0
  ) r(b, p, new_char) where
    -- make sure the new_char doesn't appear twice in its column
    -- (there are two checks because we are excluding p itself):
    strpos(substr(b, 1+(p-1)/9*9, (p-1)%9), new_char) = 0 and
    strpos(substr(b, p+1, 8-(p-1)%9), new_char) = 0 and
    -- make sure the new_char doesn't appear twice in its row:
    new_char not in (select substr(b, 1+i*9+(p-1)%9, 1)
                     from generate_series(0, 8) i
                     where p <> 1+i*9+(p-1)%9) and
    -- make sure the new_char doesn't appear twice in its 3x3 block:
    new_char not in (select substr(b, 1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3, 1)
                     from generate_series(0, 8) i
                     where p <> 1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3)
) select
    -- the following subquery is used to represent the board in a '\n' separated human-readable form:
    ( select string_agg((
        select string_agg(chr(ascii('1')+ascii(substr(b, 1+y+x*9, 1))-ascii('b')), '') r
        from generate_series(0, 8) x), E'\n')
      from generate_series(0, 8) y
    ) human_readable,
    b board,
    p depth,
    (select count(*) from board) steps
  from board where strpos(b,'_') = 0 limit 5000;

此示例展示了如何使用以下步骤使用递归 CTE 来泛型地编码任何回溯算法

• 在递归 CTE 的联合之前放置初始情况。
• 在 UNION 之后，放置一个生成下一个可能的候选值的查询。在此查询中，您将读取递归 CTE；请确保您只读取不完整的候选者，通过在该查询的 where 子句中指定此条件。
• 您可以在生成候选值的子查询周围使用另一个子查询，并使用修剪条件对其进行过滤，从而修剪无效候选者（并且可能应该这样做）。修剪非常重要，不仅是为了速度，还因为 PostgreSQL 会存储此查询返回的每一行（所有候选解），直到不再需要它们为止，并且您可能会耗尽磁盘空间（尽管您可以在 PostgreSQL 9.2+ 中使用 temp_file_limit 来限制该空间，或者使用一个单独的临时表空间）。
• 最后，在最外层，您将拥有递归 CTE 表中可用的所有候选者。在这种情况下，如果您修剪了所有无效的候选者，那么所有完整的候选者也将是有效的解。

可能状态的空间将在 BFS（广度优先搜索）中进行处理。