SQL编程大赛第3名郭其:逆天思路!三级分层策略,巧妙破解 CTE 空间爆炸

WITH RECURSIVEseq AS MATERIALIZED(SELECT pos, ((pos - 1) / 9) * 9 AS r_off, ((pos - 1) % 9) * 9 AS c_off, (((pos - 1) / 27) * 3 + ((pos - 1) % 9) / 3) * 9 AS b_off FROM generate_series(1, 81) AS pos),--行列宫位置表sudoku AS MATERIALIZED(SELECT id, REPLACE(REPLACE(s9.puzzle, '\n', ''), '\r', '') AS puzzle FROM sudoku9_9 s9),--字符串处理，本机windows换行符不一样，请帮酌情处理。bits AS (SELECT v AS cand_val, (b'000000001' << (v - 1))::bit(9) AS m9 FROM generate_series(1, 9) AS v),cand AS MATERIALIZED(SELECT n::bit(9) AS mask_9, b.cand_val FROM generate_series(0, 511) AS n CROSS JOIN bits b WHERE (n::bit(9) & b.m9) = b'000000000'),--创建二进制对应候选数字表，减少递归中的计算，转计算为joininitial_fast AS (    SELECT s.id, s.puzzle AS board,        (SELECT string_agg(row_mask::text, '' ORDER BY r_off)::bit(81) FROM (SELECT sq.r_off, bit_or(CASE WHEN val = '?' THEN b'000000000' ELSE (b'000000001' << (val::int - 1)) END) as row_mask FROM (SELECT sq.pos, sq.r_off, substr(s.puzzle, sq.pos, 1) as val FROM seq sq) sq GROUP BY sq.r_off) t) AS r_mask,        (SELECT string_agg(col_mask::text, '' ORDER BY c_off)::bit(81) FROM (SELECT sq.c_off, bit_or(CASE WHEN val = '?' THEN b'000000000' ELSE (b'000000001' << (val::int - 1)) END) as col_mask FROM (SELECT sq.pos, sq.c_off, substr(s.puzzle, sq.pos, 1) as val FROM seq sq) sq GROUP BY sq.c_off) t) AS c_mask,        (SELECT string_agg(box_mask::text, '' ORDER BY b_off)::bit(81) FROM (SELECT sq.b_off, bit_or(CASE WHEN val = '?' THEN b'000000000' ELSE (b'000000001' << (val::int - 1)) END) as box_mask FROM (SELECT sq.pos, sq.b_off, substr(s.puzzle, sq.pos, 1) as val FROM seq sq) sq GROUP BY sq.b_off) t) AS b_mask,        (translate(s.puzzle, '123456789?', '1111111110'))::bit(81) AS f_mask    FROM sudoku s),--初始化掩码，比较难看，十进制好看，但速度慢-- 1. 裸唯一传播 (主逻辑第一步),预制菜。propagate AS MATERIALIZED(    SELECT id, board, r_mask, c_mask, b_mask, f_mask FROM initial_fast    UNION ALL    SELECT cs.id, overlay(cs.board placing v.cand_val::text from nc.pos),           set_bit(cs.r_mask, (nc.r_off + (9 - v.cand_val))::int, 1)::bit(81),           set_bit(cs.c_mask, (nc.c_off + (9 - v.cand_val))::int, 1)::bit(81),           set_bit(cs.b_mask, (nc.b_off + (9 - v.cand_val))::int, 1)::bit(81),           set_bit(cs.f_mask, (nc.pos - 1)::int, 1)::bit(81)    FROM propagate cs    INNER JOIN LATERAL (        SELECT s.pos, s.r_off, s.c_off, s.b_off, (substring(cs.r_mask from s.r_off + 1 for 9) | substring(cs.c_mask from s.c_off + 1 for 9) | substring(cs.b_mask from s.b_off + 1 for 9)) AS u9        FROM seq s WHERE get_bit(cs.f_mask, s.pos - 1) = 0        AND bit_count(substring(cs.r_mask from s.r_off + 1 for 9) | substring(cs.c_mask from s.c_off + 1 for 9) | substring(cs.b_mask from s.b_off + 1 for 9)) = 8 LIMIT 1    ) nc ON TRUE INNER JOIN cand v ON v.mask_9 = nc.u9 WHERE bit_count(cs.f_mask) < 81),pre_solved AS (SELECT DISTINCT ON (id) * FROM propagate ORDER BY id, bit_count(f_mask) DESC),-- 2. Solver 主逻辑：基于之前的强力版本，维持 rank=自定义 保证 99.9% 的速度，全力冲刺，MRV算法，并激进删减分支，丢的数据交给下一层去解决，这层只为快。solver AS (    SELECT id, board, r_mask, c_mask, b_mask, f_mask FROM pre_solved     UNION ALL    SELECT res.id, res.board, res.r_mask, res.c_mask, res.b_mask, res.f_mask FROM (        SELECT cs.id, overlay(cs.board placing v.cand_val::text from nc.pos) AS board,               set_bit(cs.r_mask, (nc.r_off + (9 - v.cand_val))::int, 1)::bit(81) AS r_mask,               set_bit(cs.c_mask, (nc.c_off + (9 - v.cand_val))::int, 1)::bit(81) AS c_mask,               set_bit(cs.b_mask, (nc.b_off + (9 - v.cand_val))::int, 1)::bit(81) AS b_mask,               set_bit(cs.f_mask, (nc.pos - 1)::int, 1)::bit(81) AS f_mask,               row_number() OVER (PARTITION BY cs.id, cs.f_mask ORDER BY (bit_count(nc.u9) + nc.freq_weight) DESC, v.cand_val ASC) as rank        FROM solver cs        INNER JOIN LATERAL (            SELECT s.pos, s.r_off, s.c_off, s.b_off, (u_row | u_col | u_box) AS u9, (bit_count(u_row) + bit_count(u_col) + bit_count(u_box)) AS freq_weight            FROM (SELECT sq.pos, sq.r_off, sq.c_off, sq.b_off, substring(cs.r_mask from sq.r_off + 1 for 9) AS u_row, substring(cs.c_mask from sq.c_off + 1 for 9) AS u_col, substring(cs.b_mask from sq.b_off + 1 for 9) AS u_box FROM seq sq WHERE get_bit(cs.f_mask, sq.pos - 1) = 0) s            ORDER BY bit_count(u_row | u_col | u_box) DESC LIMIT 1        ) nc ON TRUE        INNER JOIN cand v ON v.mask_9 = nc.u9 WHERE bit_count(cs.f_mask) < 81    ) res WHERE res.rank <=2),-- 3. 终极无限制保险层：没有任何 rank 限制，死磕到底，既然快了，肯定要丢数据，太快收不住，得有人兜底，只按mrv，不删减任何分支final_insurance AS (    -- 精准拦截漏网之鱼：只进入 Solver 没解出来的 ID    SELECT p.id, p.board, p.r_mask, p.c_mask, p.b_mask, p.f_mask FROM pre_solved p    WHERE NOT EXISTS (SELECT 1 FROM solver s WHERE s.id = p.id AND bit_count(s.f_mask) = 81)    UNION ALL    SELECT res.id, res.board, res.r_mask, res.c_mask, res.b_mask, res.f_mask FROM (        SELECT cs.id, overlay(cs.board placing v.cand_val::text from nc.pos) AS board,               set_bit(cs.r_mask, (nc.r_off + (9 - v.cand_val))::int, 1)::bit(81) AS r_mask,               set_bit(cs.c_mask, (nc.c_off + (9 - v.cand_val))::int, 1)::bit(81) AS c_mask,               set_bit(cs.b_mask, (nc.b_off + (9 - v.cand_val))::int, 1)::bit(81) AS b_mask,               set_bit(cs.f_mask, (nc.pos - 1)::int, 1)::bit(81) AS f_mask        FROM final_insurance cs        INNER JOIN LATERAL (            SELECT s.pos, s.r_off, s.c_off, s.b_off,                    (substring(cs.r_mask from s.r_off + 1 for 9) |                     substring(cs.c_mask from s.c_off + 1 for 9) |                     substring(cs.b_mask from s.b_off + 1 for 9)) AS u9            FROM seq s WHERE get_bit(cs.f_mask, s.pos - 1) = 0            ORDER BY bit_count(substring(cs.r_mask from s.r_off + 1 for 9) |                                substring(cs.c_mask from s.c_off + 1 for 9) |                                substring(cs.b_mask from s.b_off + 1 for 9)) DESC LIMIT 1        ) nc ON TRUE        INNER JOIN cand v ON v.mask_9 = nc.u9         WHERE bit_count(cs.f_mask) < 81    ) res     -- 保险层不再过滤 rank，让递归自己尝试所有可能性直到解出)-- 4. 汇总select t.id,s9.puzzle,regexp_replace(t.board, '(.{9})', '\1' || chr(10), 'g') as result from (SELECT DISTINCT ON (id) id, board FROM (    SELECT id, board FROM solver WHERE bit_count(f_mask) = 81    UNION ALL    SELECT id, board FROM final_insurance WHERE bit_count(f_mask) = 81) final ORDER BY id) t  inner join sudoku9_9 s9 on t.id=s9.id