--示例生成中间表create  table dwd_sudoku_step1 asWITH RECURSIVE-- 1. 数据源 & 强壮解析 (Robust Parsing)src AS (    SELECT        id,        puzzle,        -- 【关键修复】：        -- 1. regexp_replace: 先暴力剔除所有非数字、非点、非问号的字符 (包括空格、换行、制表符等)        -- 2. translate: 再将 '.' 和 '?' 统一转为 '0'        -- 3. 结果: 得到纯净的 81 位数字字符串，绝对不会错位        string_to_array(            translate(                regexp_replace(puzzle, '[^0-9.?]', '', 'g'),                '.?', '00'            ),            NULL        )::smallint[] AS board    FROM sudoku9_9 --题面)-- 2. 棋盘单元格坐标构建    SELECT        id, val, i,   --id,原值,81位字符串序号        (i-1)/9 as r,   --行        (i-1)%9 as c,   --列        ((i-1)/27)*3 + ((i-1)%9)/3 as bx  --宫    FROM src, unnest(board) WITH ORDINALITY as t(val, i)  --数组展开为行;where id=1;

--以第一行为例--棋盘数字转为二进制掩码SELECT    a.id           AS "ID",            --id    a.r + 1        AS "Row",          -- 行号    a.val         AS "Digit",         -- 数独数字    (1 << (a.val-1))          AS "Decimal", -- 十进制位状态    (1 << (a.val-1))::bit(9)  AS "Binary"   -- 二进制位状态FROM dwd_sudoku_step1 aWHERE a.id=1 AND a.val>0 AND a.r=0;--掩码 OR (|) 运算聚合SELECT    a.id           AS "ID",            --id    a.r + 1        AS "Row",          -- 行号    array_agg(a.val)        AS "Digit",         -- 数独数字    bit_or(1 << (a.val-1))          AS "Decimal", -- 十进制位状态    bit_or(1 << (a.val-1))::bit(9)  AS "Binary"   -- 二进制位状态FROM dwd_sudoku_step1 aWHERE a.id=1 AND a.val>0 AND a.r=0group by 1,2;

-- 3. 批量初始化掩码 (Filter 聚合)masks_calc AS (----使用“位掩码”技术。通过位运算（Bitwise OR）将每一行、列、宫中已有的数字记录在一个二进制数中    SELECT id, array_agg(COALESCE(m, 0)::smallint ORDER BY idx) as ms    FROM (        SELECT id, r+1 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, r        UNION ALL        SELECT id, c+10 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, c        UNION ALL        SELECT id, bx+19 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, bx    ) t    GROUP BY id),

-- 遍历提取 (Iteration)-- 【核心特性】全量解析，结果完整-- 【适用场景】调试展示、回溯法分支生成 (需要所有可能性)WITH test_calc AS (    SELECT (511 & ~ (115|505|507)) as cand_m    union all    SELECT (511 & ~ (115|370|371)) as cand_m)SELECT    cand_m,    cand_m::bit(9) cand_m_bit,    (        SELECT string_agg(num::text, ',')        FROM generate_series(1, 9) num        WHERE (cand_m & (1 << (num - 1))) > 0 -- 挨个检查1-9是否在掩码里    ) as candidates_list,    bit_count(cand_m::bit(9)) bit_count   --掩码为1的数量FROM test_calc;

-- 单值提取 (Bit Hack)，适用于只有唯一值时快速提取-- 【核心特性】极速计算，无循环-- 【适用场景】贪心阶段 (WHERE bit_count=1)，确保只有唯一解时使用WITH test_calc AS (    SELECT (511 & ~ (115|505|507)) as cand_m    union all    SELECT (511 & ~ (115|370|371)) as cand_m)select    a.cand_m,                          --十进制表达    a.cand_m::bit(9)  as cand_m_bit,   --二进制表达    -- 【关键逻辑】利用 x & -x 提取最低位的 1 (Lowbit)    -- 如果有多个候选数，这里会丢失高位数据，只返回最小的那个数字，需要限制仅存在唯一候选情况下使用，即掩码为1的数量=1    (bit_count(((a.cand_m & -a.cand_m) - 1)::bit(32)) + 1)::smallint candidates_list,  --可选数字    bit_count(cand_m::bit(9)) bit_countfrom test_calc a;

where bit_count(cand_m::bit(9))=1

    ---待填格子位置索引：筛选出所有值为 0 的格子索引，打包为一个数组empty_calc AS (    SELECT id, array_agg(i::smallint ORDER BY i) as emp    FROM cells WHERE val = 0 GROUP BY id),

-- 4. 组装初始状态--递归前数据准备prep AS (    SELECT        s.id, s.board,  --[零件1] 原始棋盘        -- [零件2] 约束掩码 (27个整数)        -- 这里包含了 9行+9列+9宫 的初始状态        COALESCE(m.ms, '{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}'::smallint[]) as ms,        -- [零件3] 待办空位数组 (递归的任务列表)        COALESCE(e.emp, '{}'::smallint[]) as emp    FROM src s     -- 将三个独立的数据流合并为一行    LEFT JOIN masks_calc m ON s.id = m.id    LEFT JOIN empty_calc e ON s.id = e.id),

-- 5. 第一阶段：贪心极速流 (确定性求解)solve_easy(id, board, ms, emp) AS (    SELECT id, board, ms, emp FROM prep    UNION ALL    SELECT        s.id,        -- 1. 更新棋盘：把原来的 0 替换成新的数字        s.board[:cell.p-1] || c.val::smallint || s.board[cell.p+1:],        -- 2. 更新掩码：把新数字加入到对应的行、列、宫的黑名单里        s.ms[:cell.r] || (s.ms[cell.r+1] | c.bit_m)::smallint || s.ms[cell.r+2:9+cell.c] || (s.ms[10+cell.c] | c.bit_m)::smallint || s.ms[11+cell.c:18+cell.bx] || (s.ms[19+cell.bx] | c.bit_m)::smallint || s.ms[19+cell.bx+1:27],        ---- 3.移除已处理空格：从空位列表里移除当前位置        array_remove(s.emp, cell.p)    FROM solve_easy s    INNER JOIN LATERAL (        SELECT p, (p-1)/9 as r, (p-1)%9 as c, (p-1)/27*3+(p-1)%9/3 as bx, cand_m        FROM unnest(s.emp) p   -- 展开所有空位(emp)        CROSS JOIN LATERAL (   -- 计算候选掩码：全集(511) 剔除(AND NOT) 行列宫已有的数字            SELECT 511 & ~(s.ms[(p-1)/9+1]::int | s.ms[(p-1)%9+10]::int | s.ms[(p-1)/27*3+(p-1)%9/3+19]::int) as cand_m        ) t        WHERE bit_count(cand_m::bit(9)) = 1     -- 【关键！】只要那些只有 1 个可能性的        LIMIT 1                                 -- 每次只抓一个，保持稳健    ) cell ON true    CROSS JOIN LATERAL (        -- 把二进制掩码转回 1-9 的十进制整数        SELECT (bit_count(((cell.cand_m & -cell.cand_m) - 1)::bit(32)) + 1)::smallint as val,               (cell.cand_m & -cell.cand_m)::int as bit_m    ) c),

-- 6. 逻辑分流finished_easy AS (    -- [快速通道] 只要任务清单空了，直接结算，释放内存    SELECT id, board FROM solve_easy WHERE cardinality(emp) = 0),stuck_hard_input AS (    -- [优胜劣汰] 筛选出卡住的难题    SELECT DISTINCT ON (id) id, board, ms, emp    FROM solve_easy    WHERE id NOT IN (SELECT id FROM finished_easy)    -- [关键策略] 如果有多个中间状态，取剩余空位最少的那一个继续算    ORDER BY id, cardinality(emp) ASC),

-- 7. 第二阶段：回溯补刀 (MRV 策略)solve_hard(id, board, ms, emp) AS (    SELECT id, board, ms, emp FROM stuck_hard_input  -- 接力棒：处理剩余的难题    UNION ALL    SELECT        s.id,        s.board[:cell.p-1] || v.val::smallint || s.board[cell.p+1:],        s.ms[:cell.r] || (s.ms[cell.r+1] | v.bit_m)::smallint || s.ms[cell.r+2:9+cell.c] || (s.ms[10+cell.c] | v.bit_m)::smallint || s.ms[11+cell.c:18+cell.bx] || (s.ms[19+cell.bx] | v.bit_m)::smallint || s.ms[19+cell.bx+1:27],        array_remove(s.emp, cell.p)    FROM solve_hard s    JOIN LATERAL (        SELECT p, (p-1)/9 as r, (p-1)%9 as c, (p-1)/27*3+(p-1)%9/3 as bx, cand_m        FROM unnest(s.emp) p        CROSS JOIN LATERAL (            SELECT 511 & ~(s.ms[(p-1)/9+1]::int | s.ms[(p-1)%9+10]::int | s.ms[(p-1)/27*3+(p-1)%9/3+19]::int) as cand_m        ) t        -- 【关键差异】不再寻找唯一解，而是寻找"可能性最少"的格子        ORDER BY bit_count(cand_m::bit(9)) ASC        LIMIT 1    ) cell ON true    JOIN LATERAL (        -- 【关键差异】展开所有可能的候选数        SELECT d+1 as val, 1<<d as bit_m        FROM generate_series(0,8) d WHERE (cell.cand_m & (1<<d)) <> 0    ) v ON true)

-- 8. 最终合并输出SELECT    f.id,    s.puzzle,   -- [延迟物化] 此时才去读取原始题面字符串，而非在复杂递归中带着消耗资源    -- f.board,  --结果数组，方便验证数据，最终输出时注释掉    -- 格式化输出: 数组转字符串，每9位换行    trim(both E'\n' FROM regexp_replace(array_to_string(f.board, ''), '(.{9})', '\1' || E'\n', 'g')) as resultFROM (    SELECT id, board FROM finished_easy    UNION ALL    -- [去重] 再次确保每题只留一个解    SELECT DISTINCT ON (id) id, board FROM solve_hard WHERE cardinality(emp) = 0 ORDER BY id) fJOIN src s ON f.id = s.id;

--用一条 SQL 解数独问题--数据库：PostgreSQL--提交人：周仟荣1WITH RECURSIVE-- 1. 数据源 & 强壮解析 (Robust Parsing)src AS (    SELECT        id,        puzzle,        -- 1. regexp_replace: 剔除所有非数字、非点、非问号的字符 (包括空格、换行、制表符等)        -- 2. translate: 再将 '.' 和 '?' 统一转为 '0'        -- 3. 结果: 得到纯净的 81 位数字字符串        string_to_array(            translate(                regexp_replace(puzzle, '[^0-9.?]', '', 'g'),                '.?', '00'            ),            NULL        )::smallint[] AS board    FROM sudoku9_9 -- 题面),-- 2. 拆解单元格坐标cells AS (    SELECT        id, val, i,   --id,原值,81位字符串序号        (i-1)/9 as r,   --行        (i-1)%9 as c,   --列        ((i-1)/27)*3 + ((i-1)%9)/3 as bx  --宫    FROM src, unnest(board) WITH ORDINALITY as t(val, i)   --数组展开为行),-- 3. 批量初始化掩码 (Filter 聚合)masks_calc AS (----使用“位掩码”技术。通过位运算（Bitwise OR）将每一行、列、宫中已有的数字记录在一个二进制数中    SELECT id, array_agg(COALESCE(m, 0)::smallint ORDER BY idx) as ms    FROM (        SELECT id, r+1 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, r        UNION ALL        SELECT id, c+10 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, c        UNION ALL        SELECT id, bx+19 as idx, bit_or(1 << (val-1)) FILTER (WHERE val>0) as m FROM cells GROUP BY id, bx    ) t    GROUP BY id),    ---待填格子位置索引：筛选出所有值为 0 的格子索引，打包为一个数组empty_calc AS (    SELECT id, array_agg(i::smallint ORDER BY i) as emp    FROM cells WHERE val = 0 GROUP BY id),-- 4. 组装初始状态--递归前数据准备prep AS (    SELECT        s.id, s.board,  --[零件1] 原始棋盘        -- [零件2] 约束掩码 (27个整数)        -- 这里包含了 9行+9列+9宫 的初始状态        COALESCE(m.ms, '{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}'::smallint[]) as ms,        -- [零件3] 待办空位数组 (递归的任务列表)        COALESCE(e.emp, '{}'::smallint[]) as emp    FROM src s     -- 将三个独立的数据流合并为一行    LEFT JOIN masks_calc m ON s.id = m.id    LEFT JOIN empty_calc e ON s.id = e.id),-- 5. 第一阶段：贪心极速流 (确定性求解)solve_easy(id, board, ms, emp) AS (    SELECT id, board, ms, emp FROM prep    UNION ALL    SELECT        s.id,        -- 1. 更新棋盘：把原来的 0 替换成新的数字        s.board[:cell.p-1] || c.val::smallint || s.board[cell.p+1:],        -- 2. 更新掩码：把新数字加入到对应的行、列、宫的黑名单里        s.ms[:cell.r] || (s.ms[cell.r+1] | c.bit_m)::smallint || s.ms[cell.r+2:9+cell.c] || (s.ms[10+cell.c] | c.bit_m)::smallint || s.ms[11+cell.c:18+cell.bx] || (s.ms[19+cell.bx] | c.bit_m)::smallint || s.ms[19+cell.bx+1:27],        ---- 3.移除已处理空格：从空位列表里移除当前位置        array_remove(s.emp, cell.p)    FROM solve_easy s    INNER JOIN LATERAL (        SELECT p, (p-1)/9 as r, (p-1)%9 as c, (p-1)/27*3+(p-1)%9/3 as bx, cand_m        FROM unnest(s.emp) p   -- 展开所有空位(emp)        CROSS JOIN LATERAL (   -- 计算候选掩码：全集(511) 剔除(AND NOT) 行列宫已有的数字            SELECT 511 & ~(s.ms[(p-1)/9+1]::int | s.ms[(p-1)%9+10]::int | s.ms[(p-1)/27*3+(p-1)%9/3+19]::int) as cand_m        ) t        WHERE bit_count(cand_m::bit(9)) = 1     -- 【关键！】只要那些只有 1 个可能性的        LIMIT 1                                 -- 每次只抓一个，保持稳健    ) cell ON true    CROSS JOIN LATERAL (        -- 把二进制掩码转回 1-9 的十进制整数        SELECT (bit_count(((cell.cand_m & -cell.cand_m) - 1)::bit(32)) + 1)::smallint as val,               (cell.cand_m & -cell.cand_m)::int as bit_m    ) c),-- 6. 逻辑分流finished_easy AS (    -- [快速通道] 只要任务清单空了，直接结算，释放内存    SELECT id, board FROM solve_easy WHERE cardinality(emp) = 0),stuck_hard_input AS (    -- [优胜劣汰] 筛选出卡住的难题    SELECT DISTINCT ON (id) id, board, ms, emp    FROM solve_easy    WHERE id NOT IN (SELECT id FROM finished_easy)    -- [关键策略] 如果有多个中间状态，取剩余空位最少的那一个继续算    ORDER BY id, cardinality(emp) ASC),-- 7. 第二阶段：回溯补刀 (MRV 策略)solve_hard(id, board, ms, emp) AS (    SELECT id, board, ms, emp FROM stuck_hard_input  -- 接力棒：处理剩余的难题    UNION ALL    SELECT        s.id,        s.board[:cell.p-1] || v.val::smallint || s.board[cell.p+1:],        s.ms[:cell.r] || (s.ms[cell.r+1] | v.bit_m)::smallint || s.ms[cell.r+2:9+cell.c] || (s.ms[10+cell.c] | v.bit_m)::smallint || s.ms[11+cell.c:18+cell.bx] || (s.ms[19+cell.bx] | v.bit_m)::smallint || s.ms[19+cell.bx+1:27],        array_remove(s.emp, cell.p)    FROM solve_hard s    JOIN LATERAL (        SELECT p, (p-1)/9 as r, (p-1)%9 as c, (p-1)/27*3+(p-1)%9/3 as bx, cand_m        FROM unnest(s.emp) p        CROSS JOIN LATERAL (            SELECT 511 & ~(s.ms[(p-1)/9+1]::int | s.ms[(p-1)%9+10]::int | s.ms[(p-1)/27*3+(p-1)%9/3+19]::int) as cand_m        ) t        -- 【关键差异】不再寻找唯一解，而是寻找"可能性最少"的格子        ORDER BY bit_count(cand_m::bit(9)) ASC        LIMIT 1    ) cell ON true    JOIN LATERAL (        -- 【关键差异】展开所有可能的候选数        SELECT d+1 as val, 1<<d as bit_m        FROM generate_series(0,8) d WHERE (cell.cand_m & (1<<d)) <> 0    ) v ON true)-- 8. 最终合并输出SELECT    f.id,    s.puzzle,   -- [延迟物化] 此时才去读取原始题面字符串，而非在复杂递归中带着消耗资源    -- f.board,  --结果数组，方便验证数据，最终输出时注释掉    -- 格式化输出: 数组转字符串，每9位换行    trim(both E'\n' FROM regexp_replace(array_to_string(f.board, ''), '(.{9})', '\1' || E'\n', 'g')) as resultFROM (    SELECT id, board FROM finished_easy    UNION ALL    -- [去重] 再次确保每题只留一个解    SELECT DISTINCT ON (id) id, board FROM solve_hard WHERE cardinality(emp) = 0 ORDER BY id) fJOIN src s ON f.id = s.id;