SQL编程大赛第1名郑凌云:太逆天了!用 SQL 模拟栈结构做深度优先搜索,97.5 分夺冠!

with recursive coordinates as materialized (  select    row * 9 + col + 1 as id,    row,    col,    row / 3 * 3 + col / 3 as box  from    generate_series(0, 8) as rs(row),    generate_series(0, 8) as cs(col)), propagations as materialized (  select    sources.id as coordinate_id,    bit_or(bitshiftright(set_bit(0::bit(729), 0, 1), (targets.id - 1) * 9)) as targets  from    coordinates as sources  inner join    coordinates as targets  on    sources.row = targets.row    or sources.col = targets.col    or sources.box = targets.box  group by    sources.id), cells as materialized (  select    id,    coordinate_id::int as coordinate_id,    digit  from    sudoku9_9 as sudoku,    unnest(string_to_array(replace(replace(puzzle, E'\n', ''), '?', '0'), null)::int[]) with ordinality as _(digit, coordinate_id)), almosts as materialized (  select    cells.id,    bitnot(bit_or(bitshiftright(propagations.targets, cells.digit - 1))) as candidates  from    cells  inner join    propagations  on    cells.coordinate_id = propagations.coordinate_id    and cells.digit != 0  group by    cells.id), constraints as materialized (  select    cells.id,    cells.coordinate_id,    set_bit(set_bit(set_bit(overlay(b'000000000000000000000000000000000000' placing substring(almosts.candidates from (cells.coordinate_id - 1) * 9 + 1 for 9) from 1 for 9), coordinates.row + 9, 1), coordinates.col + 18, 1), coordinates.box + 27, 1) as candidates  from    cells  inner join    almosts  on    cells.id = almosts.id    and cells.digit = 0  inner join    coordinates  on    cells.coordinate_id = coordinates.id), puzzles as (  select    constraints.id,    count(distinct constraints.coordinate_id) as size,    '{}'::int[] as solution,    array_agg(set_bit(set_bit(set_bit(constraints.candidates, coordinates.row + 9, 1), coordinates.col + 18, 1), coordinates.box + 27, 1) order by bit_count(constraints.candidates)) as candidates  from    constraints  inner join    coordinates  on    constraints.coordinate_id = coordinates.id  group by    constraints.id  union all  select    id,    size,    array_append(      solution,      case        when get_bit(candidates[1], 9) = 1 then 100        when get_bit(candidates[1], 10) = 1 then 200        when get_bit(candidates[1], 11) = 1 then 300        when get_bit(candidates[1], 12) = 1 then 400        when get_bit(candidates[1], 13) = 1 then 500        when get_bit(candidates[1], 14) = 1 then 600        when get_bit(candidates[1], 15) = 1 then 700        when get_bit(candidates[1], 16) = 1 then 800        else 900      end      + case        when get_bit(candidates[1], 18) = 1 then 10        when get_bit(candidates[1], 19) = 1 then 20        when get_bit(candidates[1], 20) = 1 then 30        when get_bit(candidates[1], 21) = 1 then 40        when get_bit(candidates[1], 22) = 1 then 50        when get_bit(candidates[1], 23) = 1 then 60        when get_bit(candidates[1], 24) = 1 then 70        when get_bit(candidates[1], 25) = 1 then 80        else 90      end      + digit + 1    ) as solution,    array(      select        case          when            get_bit(candidate, digit) = 1            and bit_count(candidates[1] & candidate & b'000000000111111111111111111111111111') > 0          then            set_bit(candidate, digit, 0)          else            candidate        end as candidate      from        unnest(candidates[2:]) as _(candidate)      order by        bit_count(candidate)    ) as candidates  from    puzzles,    (values (0), (1), (2), (3), (4), (5), (6), (7), (8)) as _(digit)  where    cardinality(candidates) > 0    and bit_count(candidates[1]) > 3    and get_bit(candidates[1], digit) = 1), solutions as (  select   distinct on (id)    id,    array(      select        candidate % 10      from        unnest(solution) as _(candidate)      order by        candidate    ) as solution  from    puzzles  where    cardinality(solution) = size)select  sudoku.id,  sudoku.puzzle,  format(replace(sudoku.puzzle, '?', '%s'), variadic solutions.solution) as resultfrom  sudoku9_9 as sudokuinner join  solutionson  sudoku.id = solutions.id