DBA挑战AI: 一条SQL解数独

CREATE TABLE sudoku_puzzles (  
    id SERIAL PRIMARY KEY,  
    board TEXT NOT NULL  -- 81位字符串，1-9为已知数字，'.' 代表空格  
);  

INSERT INTO sudoku_puzzles (board) VALUES   
('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79');  

WITH RECURSIVE solve(board, pos) AS (  
    -- 基础部分：找到第一个待填的位置  
    SELECT   
        board,   
        position('.'IN board) as pos  
    FROM sudoku_puzzles  
    WHEREid = 1-- 指定题目ID  

    UNIONALL

    -- 递归部分：尝试填入 1-9  
    SELECT   
        substring(board, 1, pos - 1) || val || substring(board, pos + 1),  
        position('.'INsubstring(board, 1, pos - 1) || val || substring(board, pos + 1))  
    FROM solve,   
    (SELECTchr(ascii('1') + i) AS val FROM generate_series(0, 8) i) AS nums  
    WHERE pos > 0-- 只要还有 '.' 就继续填  
      -- 约束条件检查 (优雅的核心：一行逻辑判断行、列、宫)  
      ANDNOTEXISTS (  
          SELECT1FROM generate_series(1, 9) i  
          WHERE   
            -- 行冲突检查  
            substring(board, ((pos-1)/9)*9 + i, 1) = val  
            OR
            -- 列冲突检查  
            substring(board, ((pos-1)%9) + (i-1)*9 + 1, 1) = val  
            OR
            -- 3x3 宫冲突检查  
            substring(board,   
                (((pos-1)/27)*27 + (((pos-1)%9)/3)*3) + ((i-1)/3)*9 + ((i-1)%3) + 1, 1) = val  
      )  
)  
-- 最终结果：pos=0 表示没有空格了  
SELECT board AS solution   
FROM solve   
WHERE pos = 0;  

SELECT regexp_replace(  
    '534678912672195348198342567859761423426853791713924856961537284287419635345286179',  
    '(.{9})',  
    '\1' || chr(10),  
    'g'  
) AS matrix_view;  

5 3 4  
6 7 2  
1 9 8  

WITH RECURSIVE   
-- 1. 生成 1-9 的数字序列  
nums AS (SELECT generate_series(1, 9)::textAS val),  

-- 2. 递归解决核心  
solve(board, solved) AS (  
    -- 基础部分  
    SELECT board, falseFROM sudoku_puzzles WHEREid = 1
      
    UNIONALL
      
    (  
      WITH current_state AS (  
          SELECT board FROM solve WHERENOT solved  
      ),  
      -- 计算所有空格的坐标和当前可填的候选数数量  
      candidates AS (  
          SELECT   
            cs.board,  
            p.pos,  
            array_agg(n.val) as valid_vals  
          FROM current_state cs  
          CROSSJOIN generate_series(1, 81) p(pos)  
          CROSSJOIN nums n  
          WHEREsubstring(cs.board, p.pos, 1) = '.'-- 只针对空格  
            ANDNOTEXISTS ( -- 约束检查  
                SELECT1FROM generate_series(1, 9) i  
                WHEREsubstring(cs.board, ((p.pos-1)/9)*9 + i, 1) = n.val -- 行  
                   ORsubstring(cs.board, (p.pos-1)%9 + (i-1)*9 + 1, 1) = n.val -- 列  
                   ORsubstring(cs.board, ((p.pos-1)/27)*27 + (((p.pos-1)%9)/3)*3 + ((i-1)/3)*9 + (i-1)%3 + 1, 1) = n.val -- 宫  
            )  
          GROUPBY cs.board, p.pos  
      ),  
      -- 关键：找到候选数最少的那个格子（MRV 策略）  
      best_candidate AS (  
          SELECTDISTINCTON (board) * FROM candidates ORDERBY board, array_length(valid_vals, 1) ASC
      )  
      -- 执行填值  
      SELECT   
          substring(bc.board, 1, bc.pos - 1) || v.val || substring(bc.board, bc.pos + 1),  
          position('.'INsubstring(bc.board, 1, bc.pos - 1) || v.val || substring(bc.board, bc.pos + 1)) = 0
      FROM best_candidate bc  
      JOINunnest(bc.valid_vals) v(val) ONtrue
    )  
)  
SELECT board FROM solve WHERE solved;  
  

WITH RECURSIVE
initialAS (  
    SELECT   
        board,  
        -- 初始化行掩码  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(0, 8) r  
            LEFTJOINLATERAL (  
                SELECTsubstring(board, r*9 + i, 1) as ch, i  
                FROM generate_series(1, 9) i  
            ) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT ch::intas val) v  
            GROUPBY r ORDERBY r  
        ) s) asrows,  
        -- 初始化列掩码  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(1, 9) c  
            LEFTJOINLATERAL (  
                SELECTsubstring(board, (i-1)*9 + c, 1) as ch  
                FROM generate_series(1, 9) i  
            ) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT ch::intas val) v  
            GROUPBY c ORDERBY c  
        ) s) as cols,  
        -- 初始化宫掩码  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(0, 8) b  
            LEFTJOINLATERAL (  
                SELECTsubstring(board, (b/3)*27 + (b%3)*3 + ((i-1)/3)*9 + ((i-1)%3) + 1, 1) as ch  
                FROM generate_series(1, 9) i  
            ) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT ch::intas val) v  
            GROUPBY b ORDERBY b  
        ) s) as boxes  
    FROM sudoku_puzzles WHEREid = 1
),  
solve(board, rows, cols, boxes, pos) AS (  
    SELECT board, rows, cols, boxes, position('.'IN board) FROMinitial
    UNIONALL
    (  
        -- 使用 OFFSET 0 是 PG 的优化技巧，强制物化  
        SELECT   
            substring(curr.board, 1, curr.pos - 1) || n || substring(curr.board, curr.pos + 1),  
            curr.rows[:row_idx-1] || (curr.rows[row_idx] | (1 << (n-1))) || curr.rows[row_idx+1:],  
            curr.cols[:col_idx-1] || (curr.cols[col_idx] | (1 << (n-1))) || curr.cols[col_idx+1:],  
            curr.boxes[:box_idx-1] || (curr.boxes[box_idx] | (1 << (n-1))) || curr.boxes[box_idx+1:],  
            position('.'INsubstring(curr.board, 1, curr.pos - 1) || n || substring(curr.board, curr.pos + 1))  
        FROM (  
            SELECT *,   
                   ((pos-1)/9) + 1as row_idx,   
                   ((pos-1)%9) + 1as col_idx,   
                   ((pos-1)/27)*3 + ((pos-1)%9/3) + 1as box_idx   
            FROM solve WHERE pos > 0LIMIT1000
        ) curr  
        CROSSJOIN generate_series(1, 9) n  
        WHERE (curr.rows[row_idx] & (1 << (n-1))) = 0
          AND (curr.cols[col_idx] & (1 << (n-1))) = 0
          AND (curr.boxes[box_idx] & (1 << (n-1))) = 0
    )  
)  
SELECT board FROM solve WHERE pos = 0;  

WITH RECURSIVE
initialAS (  
    SELECT   
        board,  
        -- 初始化行掩码：确保 SUM 结果被强制转为 int  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(0, 8) r  
            LEFTJOINLATERAL (SELECTsubstring(board, r*9 + i, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT (ch::text)::intas val) v  
            GROUPBY r ORDERBY r  
        ) s) asrows,  
        -- 初始化列掩码  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(1, 9) c  
            LEFTJOINLATERAL (SELECTsubstring(board, (i-1)*9 + c, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT (ch::text)::intas val) v  
            GROUPBY c ORDERBY c  
        ) s) as cols,  
        -- 初始化宫掩码  
        (SELECT array_agg(m) FROM (  
            SELECTCOALESCE(SUM(1 << (val - 1)), 0)::intas m  
            FROM generate_series(0, 8) b  
            LEFTJOINLATERAL (SELECTsubstring(board, (b/3)*27 + (b%3)*3 + ((i-1)/3)*9 + ((i-1)%3) + 1, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSSJOINLATERAL (SELECT (ch::text)::intas val) v  
            GROUPBY b ORDERBY b  
        ) s) as boxes  
    FROM sudoku_puzzles WHEREid = 1
),  
solve AS (  
    SELECT board, rows, cols, boxes, falseas solved FROMinitial
    UNIONALL
    (  
        WITH current_level AS (  
            SELECT * FROM solve WHERENOT solved LIMIT1000
        ),  
        all_candidates AS (  
            SELECT   
                cl.board, cl.rows, cl.cols, cl.boxes,  
                p.pos,  
                -- 修正重点：每一个数组提取都加 ::int，并且用括号包裹位运算  
                ( ( (cl.rows[(p.pos-1)/9 + 1]::int | cl.cols[(p.pos-1)%9 + 1]::int | cl.boxes[((p.pos-1)/27*3 + (p.pos-1)%9/3) + 1]::int) # 511 ) & 511 )::int as available_mask  
            FROM current_level cl  
            CROSSJOIN generate_series(1, 81) p(pos)  
            WHEREsubstring(cl.board, p.pos, 1) = '.'
        ),  
        best_pos AS (  
            SELECTDISTINCTON (board)   
                *,  
                -- 计算 1 的数量  
                length(replace((available_mask::bit(9))::text, '0', '')) as c_count  
            FROM all_candidates  
            ORDERBY board, c_count ASC
        ),  
        next_step AS (  
            SELECT   
                substring(bp.board, 1, bp.pos - 1) || n.val || substring(bp.board, bp.pos + 1) as next_board,  
                bp.rows[:r_idx-1] || ((bp.rows[r_idx]::int | (1 << (n.val-1)))::int) || bp.rows[r_idx+1:] as next_rows,  
                bp.cols[:c_idx-1] || ((bp.cols[c_idx]::int | (1 << (n.val-1)))::int) || bp.cols[c_idx+1:] as next_cols,  
                bp.boxes[:b_idx-1] || ((bp.boxes[b_idx]::int | (1 << (n.val-1)))::int) || bp.boxes[b_idx+1:] as next_boxes  
            FROM best_pos bp  
            CROSSJOIN generate_series(1, 9) n(val)  
            CROSSJOINLATERAL (  
                SELECT ((pos-1)/9) + 1as r_idx,   
                       ((pos-1)%9) + 1as c_idx,   
                       ((pos-1)/27*3 + (pos-1)%9/3) + 1as b_idx  
            ) idx  
            -- 明确限定 bp.available_mask 为 int，并使用 & 检查  
            WHERE ((bp.available_mask::int >> (n.val-1)) & 1) = 1
        )  
        SELECT   
            next_board, next_rows, next_cols, next_boxes,  
            position('.'IN next_board) = 0
        FROM next_step  
    )  
)  
SELECT board FROM solve WHERE solved;  

-- 题目 1: 芬兰数学家 Arto Inkala 设计的 "AI Escargot" (号称当时世界最难)  
-- 题目 2: 2012年设计的号称“新世界最难”的题目 (Everest)  
-- 题目 3: 只有 17 个数字的极简数独 (17-clue puzzles，理论上已知数字最少的唯一解数独)  

INSERTINTO sudoku_puzzles (board) VALUES   
('1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8.2.......1'),  
('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'),  
('000000010400000000020000000000050407008000300001090000300400200050100000000806000');  

-- 注意：如果题目3中有0，请统一替换为 '.'，SQL解法通常识别 '.'  
UPDATE sudoku_puzzles SET board = replace(board, '0', '.') WHEREid = 3;  
  

WITH RECURSIVE  
-- 此处插入之前那个“终极版位运算+MRV”的 solve 递归逻辑...  
-- (为了简洁，这里省略递归主体，请直接衔接之前的递归代码)  
  
SELECT   
    id,  
    regexp_replace(board, '(.{9})', '\1' || chr(10), 'g') AS matrix_view  
FROM solve   
WHERE solved;  
  

CREATE TABLE sudoku_puzzles (  
    id SERIAL PRIMARY KEY,  
    board TEXT NOT NULL  -- 81位字符串，1-9为已知数字，'.' 代表空格  
);  

INSERT INTO sudoku_puzzles (board) VALUES   
('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79');  

-- 题目 1: 芬兰数学家 Arto Inkala 设计的 "AI Escargot" (号称当时世界最难)  
-- 题目 2: 2012年设计的号称“新世界最难”的题目 (Everest)  
-- 题目 3: 只有 17 个数字的极简数独 (17-clue puzzles，理论上已知数字最少的唯一解数独)  

INSERT INTO sudoku_puzzles (board) VALUES   
('1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8.2.......1'),  
('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'),  
('000000010400000000020000000000050407008000300001090000300400200050100000000806000');  


-- 注意：如果题目3中有0，请统一替换为 '.'，SQL解法通常识别 '.'
UPDATE sudoku_puzzles SET board = replace(board, '0', '.') ;  

SELECT regexp_replace(  
    board,  
    '(.{9})',  
    '\1' || chr(10),  
    'g'
) AS matrix_view  
from sudoku_puzzles;  


 matrix_view   
-------------  
 53..7....  +  
 6..195...  +  
 .98....6.  +  
 8...6...3  +  
 4..8.3..1  +  
 7...2...6  +  
 .6....28.  +  
 ...419..5  +  
 ....8..79  +  
   
 1.......2  +  
 .9.4...5.  +  
 ..6...7..  +  
 .5.9.3...  +  
 ....7....  +  
 ...85..4.  +  
 7.....6..  +  
 .3...9.8.  +  
 2.......1  +  
   
 .......1.  +  
 4........  +  
 .2.......  +  
 ....5.4.7  +  
 ..8...3..  +  
 ..1.9....  +  
 3..4..2..  +  
 .5.1.....  +  
 ...8.6...  +  
   
 8........  +  
 ..36.....  +  
 .7..9.2..  +  
 .5...7...  +  
 ....457..  +  
 ...1...3.  +  
 ..1....68  +  
 ..85...1.  +  
 .9....4..  +  
   
(4 rows)  

create or replace view v_cte as   
WITH RECURSIVE  
initial AS (  
    SELECT   
        board,  
        -- 初始化行掩码：确保 SUM 结果被强制转为 int  
        (SELECT array_agg(m) FROM (  
            SELECT COALESCE(SUM(1 << (val - 1)), 0)::int as m  
            FROM generate_series(0, 8) r  
            LEFT JOIN LATERAL (SELECT substring(board, r*9 + i, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSS JOIN LATERAL (SELECT (ch::text)::int as val) v  
            GROUP BY r ORDER BY r  
        ) s) as rows,  
        -- 初始化列掩码  
        (SELECT array_agg(m) FROM (  
            SELECT COALESCE(SUM(1 << (val - 1)), 0)::int as m  
            FROM generate_series(1, 9) c  
            LEFT JOIN LATERAL (SELECT substring(board, (i-1)*9 + c, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSS JOIN LATERAL (SELECT (ch::text)::int as val) v  
            GROUP BY c ORDER BY c  
        ) s) as cols,  
        -- 初始化宫掩码  
        (SELECT array_agg(m) FROM (  
            SELECT COALESCE(SUM(1 << (val - 1)), 0)::int as m  
            FROM generate_series(0, 8) b  
            LEFT JOIN LATERAL (SELECT substring(board, (b/3)*27 + (b%3)*3 + ((i-1)/3)*9 + ((i-1)%3) + 1, 1) as ch FROM generate_series(1, 9) i) s ON ch <> '.'
            CROSS JOIN LATERAL (SELECT (ch::text)::int as val) v  
            GROUP BY b ORDER BY b  
        ) s) as boxes  
    FROM sudoku_puzzles WHERE id = 4  -- 取一条骨灰级数独开始计算  
),  
solve AS (  
    SELECT board, rows, cols, boxes, false as solved FROM initial  
    UNION ALL  
    (  
        WITH current_level AS (  
            SELECT * FROM solve WHERE NOT solved LIMIT 1000  
        ),  
        all_candidates AS (  
            SELECT   
                cl.board, cl.rows, cl.cols, cl.boxes,  
                p.pos,  
                -- 修正重点：每一个数组提取都加 ::int，并且用括号包裹位运算  
                ( ( (cl.rows[(p.pos-1)/9 + 1]::int | cl.cols[(p.pos-1)%9 + 1]::int | cl.boxes[((p.pos-1)/27*3 + (p.pos-1)%9/3) + 1]::int) # 511 ) & 511 )::int as available_mask  
            FROM current_level cl  
            CROSS JOIN generate_series(1, 81) p(pos)  
            WHERE substring(cl.board, p.pos, 1) = '.'
        ),  
        best_pos AS (  
            SELECT DISTINCT ON (board)   
                *,  
                -- 计算 1 的数量  
                length(replace((available_mask::bit(9))::text, '0', '')) as c_count  
            FROM all_candidates  
            ORDER BY board, c_count ASC  
        ),  
        next_step AS (  
            SELECT   
                substring(bp.board, 1, bp.pos - 1) || n.val || substring(bp.board, bp.pos + 1) as next_board,  
                bp.rows[:r_idx-1] || ((bp.rows[r_idx]::int | (1 << (n.val-1)))::int) || bp.rows[r_idx+1:] as next_rows,  
                bp.cols[:c_idx-1] || ((bp.cols[c_idx]::int | (1 << (n.val-1)))::int) || bp.cols[c_idx+1:] as next_cols,  
                bp.boxes[:b_idx-1] || ((bp.boxes[b_idx]::int | (1 << (n.val-1)))::int) || bp.boxes[b_idx+1:] as next_boxes  
            FROM best_pos bp  
            CROSS JOIN generate_series(1, 9) n(val)  
            CROSS JOIN LATERAL (  
                SELECT ((pos-1)/9) + 1 as r_idx,   
                       ((pos-1)%9) + 1 as c_idx,   
                       ((pos-1)/27*3 + (pos-1)%9/3) + 1 as b_idx  
            ) idx  
            -- 明确限定 bp.available_mask 为 int，并使用 & 检查  
            WHERE ((bp.available_mask::int >> (n.val-1)) & 1) = 1  
        )  
        SELECT   
            next_board, next_rows, next_cols, next_boxes,  
            position('.' IN next_board) = 0  
        FROM next_step  
    )  
)  
SELECT board FROM solve WHERE solved;  

SELECT regexp_replace(  
    board,  
    '(.{9})',  
    '\1' || chr(10),  
    'g'  
) AS matrix_view  
from v_cte;  

 matrix_view   
-------------  
 693784512  +  
 487512936  +  
 125963874  +  
 932651487  +  
 568247391  +  
 741398625  +  
 319475268  +  
 856129743  +  
 274836159  +  
   
(1 row)  

Time: 786.542 ms