SQL编程大赛第2名程宁:递归 CTE+MPV 算法,三大减枝策略太牛了

-- PostgreSQL数独求解：减枝策略：两轮计算、显隐唯一数填充、候选数MPV--EXPLAIN (ANALYZE, TIMING ON) WITH RECURSIVE-- 生成1-9有效数字d(d) AS MATERIALIZED(SELECT generate_series(1, 9)),-- 生成81个位置的行/列/宫编号（pos:1-81, r:1-9, c:1-9, bx:1-9）pi(pos, r, c, bx) AS MATERIALIZED(    SELECT         pos,        ((pos - 1) / 9) + 1 AS r,        ((pos - 1) % 9) + 1 AS c,        ((pos - 1) / 9) / 3 * 3 + ((pos - 1) % 9) / 3 + 1 AS bx    FROM generate_series(1, 81) AS pos),-- 预处理谜题：去空白、?转0、转为整数数组cp(id, pz, bs) AS (    SELECT         id,        puzzle,        regexp_split_to_array(            regexp_replace(regexp_replace(puzzle, '[\r\n\s]', '', 'g'), '\?', '0', 'g'),             ''        )::int[] AS bs    FROM sudoku9_9),-- 第一轮递归：优先唯一候选数填充，无则猜测最少候选位置s1(id, bs, i ) AS (    SELECT id, bs, 0 AS i  FROM cp    UNION ALL    SELECT c.id, n.bs, c.i + 1 AS i    FROM s1 c    CROSS JOIN LATERAL (        WITH         eb(pos, r, c, bx, v) AS (SELECT pi.pos, pi.r, pi.c, pi.bx, c.bs[pi.pos] FROM pi),        -- 计算空白位置合法候选数        cd(pos, r, c, bx, d) AS (            SELECT e.pos, e.r, e.c, e.bx, d.d            FROM eb e CROSS JOIN d d            WHERE e.v = 0              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.r = e.r AND e2.v = d.d)              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.c = e.c AND e2.v = d.d)              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.bx = e.bx AND e2.v = d.d)        ),        -- 筛选唯一可填位置（位置/行/列/宫维度）        af(pos,r, c, bx, d) AS (            SELECT pos,r, c, bx, MIN(d) FROM cd GROUP BY pos,r, c, bx HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),r,min(c),min(bx), d FROM cd GROUP BY r, d HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),min(r),c,min(bx), d FROM cd GROUP BY c, d HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),min(r),min(c),bx, d FROM cd GROUP BY bx, d HAVING COUNT(1) = 1        ),        -- 检查填充是否存在重复（无效解）        error_check(is_invalid) AS (            SELECT EXISTS (                SELECT 1 FROM af GROUP BY r, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY c, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY bx, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY pos,d HAVING COUNT(*) > 1            ) AS is_invalid        ),        -- 应用填充并标记是否有有效填充        adf(bs, hf) AS (            SELECT                 (SELECT array_agg(coalesce(af.d, c.bs[pi.pos]) order by pi.pos) FROM pi LEFT JOIN af ON pi.pos = af.pos) AS bs,                EXISTS (SELECT 1 FROM af) AS hf        )        -- 有唯一候选则填充，无效则返回标记数组，无则猜测填充        SELECT bs FROM adf,error_check WHERE hf AND NOT is_invalid        UNION ALL        SELECT g.bs        FROM adf a,error_check        CROSS JOIN LATERAL (SELECT pos FROM (SELECT pos FROM cd GROUP BY pos ORDER BY COUNT(1), pos desc LIMIT 1) AS p) bg        CROSS JOIN LATERAL (SELECT d FROM cd,        	(select v,count(1) cnt from eb group by v ) ceb        	   WHERE pos = bg.pos and d=ceb.v order by ceb.cnt desc LIMIT 1) gv --该空格已经出现次数最多数字        CROSS JOIN LATERAL (SELECT c.bs[1 : (bg.pos - 1)] || ARRAY[gv.d] || c.bs[(bg.pos + 1) : 81] AS bs) g        WHERE NOT a.hf AND NOT is_invalid    ) n    WHERE c.i < 81 AND c.bs @> ARRAY[0]),-- 第一轮求解结果（已完成的数独）f1(id, pz, bs) AS (    SELECT s.id, cp.pz, s.bs    FROM s1 s JOIN cp ON s.id = cp.id    WHERE NOT s.bs @> ARRAY[0] ),-- 第二轮递归：处理第一轮未解决的谜题（原理同S1）s2(id, bs, i) AS (    SELECT cp.id, cp.bs, 0 AS i    FROM cp LEFT JOIN f1 ON cp.id = f1.id    WHERE f1.id IS NULL    UNION ALL    SELECT c.id, n.bs, c.i + 1 AS i    FROM s2 c    CROSS JOIN LATERAL (        WITH         eb(pos, r, c, bx, v) AS (SELECT pi.pos, pi.r, pi.c, pi.bx, c.bs[pi.pos] FROM pi),        cd(pos, r, c, bx, d) AS (            SELECT e.pos, e.r, e.c, e.bx, d.d            FROM eb e CROSS JOIN d d            WHERE e.v = 0              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.r = e.r AND e2.v = d.d)              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.c = e.c AND e2.v = d.d)              AND NOT EXISTS (SELECT 1 FROM eb e2 WHERE e2.bx = e.bx AND e2.v = d.d)        ),        af(pos,r, c, bx, d) AS (            SELECT pos,r, c, bx, MIN(d) FROM cd GROUP BY pos,r, c, bx HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),r,min(c),min(bx), d FROM cd GROUP BY r, d HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),min(r),c,min(bx), d FROM cd GROUP BY c, d HAVING COUNT(1) = 1            UNION            SELECT MIN(pos),min(r),min(c),bx, d FROM cd GROUP BY bx, d HAVING COUNT(1) = 1        ),        error_check(is_invalid) AS (            SELECT EXISTS (                SELECT 1 FROM af GROUP BY r, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY c, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY bx, d HAVING COUNT(*) > 1                UNION ALL SELECT 1 FROM af GROUP BY pos,d HAVING COUNT(*) > 1            ) AS is_invalid        ),        adf(bs, hf) AS (            SELECT                 (SELECT array_agg(coalesce(af.d, c.bs[pi.pos]) order by pi.pos) FROM pi LEFT JOIN af ON pi.pos = af.pos) AS bs,                EXISTS (SELECT 1 FROM af) AS hf        )        SELECT bs FROM adf,error_check WHERE hf AND NOT is_invalid        UNION ALL        SELECT g.bs        FROM adf a,error_check        CROSS JOIN LATERAL (SELECT pos FROM (SELECT pos FROM cd GROUP BY pos ORDER BY COUNT(1), pos desc LIMIT 1) AS p) bg        CROSS JOIN LATERAL (SELECT d FROM cd WHERE pos = bg.pos) gv        CROSS JOIN LATERAL (SELECT c.bs[1 : (bg.pos - 1)] || ARRAY[gv.d] || c.bs[(bg.pos + 1) : 81] AS bs) g        WHERE NOT a.hf AND NOT is_invalid    ) n    WHERE c.i < 81 AND c.bs @> ARRAY[0]),-- 合并两轮结果：取每个谜题的最新完成解f2(id, pz, bs) AS (      SELECT DISTINCT ON (s.id)         s.id, cp.pz, s.bs    FROM s2 s     JOIN cp ON s.id = cp.id    WHERE NOT s.bs @> ARRAY[0]),f(id, pz, bs) AS (  select id,pz,bs from f1union all select id,pz,bs from f2)-- 格式化输出：每行9个数字，换行分隔SELECT     id,    pz AS puzzle,    array_to_string(        array(SELECT CASE WHEN pos % 9 = 1 AND pos > 1 THEN E'\n' ELSE '' END || value::text               FROM unnest(bs) WITH ORDINALITY AS elem(value, pos)),        ''    ) AS resultFROM f;