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

WITH RECURSIVEbs_t AS MATERIALIZED (SELECT id, convert_to(replace(puzzle, E'\n', ''), 'UTF8') AS bsFROM sudoku9_9),init_t AS (SELECT id, row_can, col_can, box_can, todo, bs AS doneFROM bs_tCROSS JOIN LATERAL (WITH board_t AS (SELECTarray_agg(mask ORDER BY i) AS bd,COALESCE(array_agg(((i / 9 + 1) << 8) | ((i % 9 + 1) << 4) | (i / 27 * 3 + i % 9 / 3 + 1))FILTER (WHERE mask = 0), ARRAY[]::int[]) AS todoFROM (SELECT i, (1 << (get_byte(bs, i) - 49)) & 0x1FF AS maskFROM generate_series(0, 80) AS g(i)			) AS bd_t		)SELECTARRAY[0x1FF # (bd[1]  | bd[2]  | bd[3]  | bd[4]  | bd[5]  | bd[6]  | bd[7]  | bd[8]  | bd[9]),0x1FF # (bd[10] | bd[11] | bd[12] | bd[13] | bd[14] | bd[15] | bd[16] | bd[17] | bd[18]),0x1FF # (bd[19] | bd[20] | bd[21] | bd[22] | bd[23] | bd[24] | bd[25] | bd[26] | bd[27]),0x1FF # (bd[28] | bd[29] | bd[30] | bd[31] | bd[32] | bd[33] | bd[34] | bd[35] | bd[36]),0x1FF # (bd[37] | bd[38] | bd[39] | bd[40] | bd[41] | bd[42] | bd[43] | bd[44] | bd[45]),0x1FF # (bd[46] | bd[47] | bd[48] | bd[49] | bd[50] | bd[51] | bd[52] | bd[53] | bd[54]),0x1FF # (bd[55] | bd[56] | bd[57] | bd[58] | bd[59] | bd[60] | bd[61] | bd[62] | bd[63]),0x1FF # (bd[64] | bd[65] | bd[66] | bd[67] | bd[68] | bd[69] | bd[70] | bd[71] | bd[72]),0x1FF # (bd[73] | bd[74] | bd[75] | bd[76] | bd[77] | bd[78] | bd[79] | bd[80] | bd[81])			]::int[] AS row_can,
ARRAY[0x1FF # (bd[1]  | bd[10] | bd[19] | bd[28] | bd[37] | bd[46] | bd[55] | bd[64] | bd[73]),0x1FF # (bd[2]  | bd[11] | bd[20] | bd[29] | bd[38] | bd[47] | bd[56] | bd[65] | bd[74]),0x1FF # (bd[3]  | bd[12] | bd[21] | bd[30] | bd[39] | bd[48] | bd[57] | bd[66] | bd[75]),0x1FF # (bd[4]  | bd[13] | bd[22] | bd[31] | bd[40] | bd[49] | bd[58] | bd[67] | bd[76]),0x1FF # (bd[5]  | bd[14] | bd[23] | bd[32] | bd[41] | bd[50] | bd[59] | bd[68] | bd[77]),0x1FF # (bd[6]  | bd[15] | bd[24] | bd[33] | bd[42] | bd[51] | bd[60] | bd[69] | bd[78]),0x1FF # (bd[7]  | bd[16] | bd[25] | bd[34] | bd[43] | bd[52] | bd[61] | bd[70] | bd[79]),0x1FF # (bd[8]  | bd[17] | bd[26] | bd[35] | bd[44] | bd[53] | bd[62] | bd[71] | bd[80]),0x1FF # (bd[9]  | bd[18] | bd[27] | bd[36] | bd[45] | bd[54] | bd[63] | bd[72] | bd[81])			]::int[] AS col_can,
ARRAY[0x1FF # (bd[1]  | bd[2]  | bd[3]  | bd[10] | bd[11] | bd[12] | bd[19] | bd[20] | bd[21]),0x1FF # (bd[4]  | bd[5]  | bd[6]  | bd[13] | bd[14] | bd[15] | bd[22] | bd[23] | bd[24]),0x1FF # (bd[7]  | bd[8]  | bd[9]  | bd[16] | bd[17] | bd[18] | bd[25] | bd[26] | bd[27]),0x1FF # (bd[28] | bd[29] | bd[30] | bd[37] | bd[38] | bd[39] | bd[46] | bd[47] | bd[48]),0x1FF # (bd[31] | bd[32] | bd[33] | bd[40] | bd[41] | bd[42] | bd[49] | bd[50] | bd[51]),0x1FF # (bd[34] | bd[35] | bd[36] | bd[43] | bd[44] | bd[45] | bd[52] | bd[53] | bd[54]),0x1FF # (bd[55] | bd[56] | bd[57] | bd[64] | bd[65] | bd[66] | bd[73] | bd[74] | bd[75]),0x1FF # (bd[58] | bd[59] | bd[60] | bd[67] | bd[68] | bd[69] | bd[76] | bd[77] | bd[78]),0x1FF # (bd[61] | bd[62] | bd[63] | bd[70] | bd[71] | bd[72] | bd[79] | bd[80] | bd[81])			]::int[] AS box_can,
			todoFROM board_t	) AS rcb_t),
infer_t AS (SELECT id, row_can, col_can, box_can, todo, done, TRUE AS expandFROM init_t
UNION ALL
SELECT		id,CASEWHEN expand_ IS NOT NULLTHEN row_can[:r - 1] || (row_can[r] # candidates) || row_can[r + 1:]ELSE row_canEND,CASEWHEN expand_ IS NOT NULLTHEN col_can[:c - 1] || (col_can[c] # candidates) || col_can[c + 1:]ELSE col_canEND,CASEWHEN expand_ IS NOT NULLTHEN box_can[:b - 1] || (box_can[b] # candidates) || box_can[b + 1:]ELSE box_canEND,CASEWHEN expand_ IS NOT NULLTHEN todo[:i - 1] || todo[i + 1:]ELSE todoEND,CASEWHEN expand_ IS NOT NULLTHEN set_byte(done, (r << 3) + r + c - 10, bit_count((candidates - 1)::bit(16))::int + 49)ELSE doneEND,		expand_FROM infer_tLEFT JOIN LATERAL (SELECT i, r, c, b, candidates, TRUE AS expand_FROM generate_subscripts(todo, 1) t(i)CROSS JOIN LATERAL (SELECT todo[i] >> 8 AS r, (todo[i] >> 4) & 0x0F AS c, todo[i] & 0x0F AS b		) AS infer_rcb_tCROSS JOIN LATERAL (SELECT row_can[r] & col_can[c] & box_can[b] AS candidates		) AS infer_can_tWHERE bit_count(candidates::bit(16)) = 1		LIMIT 1	) AS infer_next_t ON TRUEWHERE expand IS NOT NULL),infer_rst_t AS (SELECT id, row_can, col_can, box_can, todo, doneFROM infer_tWHERE expand IS NULL),
search_t AS (SELECT		id,0 AS deep,FALSE AS back,0 AS back_can,		row_can,		col_can,		box_can,		todo,		done,ARRAY[]::int[][] stack,CASE WHEN cardinality(todo) = 0 THEN TRUE ELSE NULL::boolean END AS statusFROM infer_rst_t
UNION ALL
SELECT		id,		deep + 1,CASE WHEN candidate != 0 THEN FALSE ELSE TRUE END,		s_cand,
CASEWHEN candidate != 0THEN row_can[:r - 1] || (row_can[r] # candidate) || row_can[r + 1:]ELSE				row_can[:s_r - 1] ||				(row_can[s_r] # (s_cand & -s_cand)) ||				row_can[s_r + 1:]END,
CASEWHEN candidate != 0THEN col_can[:c - 1] || (col_can[c] # candidate) || col_can[c + 1:]ELSE				col_can[:s_c - 1] ||				(col_can[s_c] # (s_cand & -s_cand)) ||				col_can[s_c + 1:]END,
CASEWHEN candidate != 0THEN box_can[:b - 1] || (box_can[b] # candidate) || box_can[b + 1:]ELSE				box_can[:s_b - 1] ||				(box_can[s_b] # (s_cand & -s_cand)) ||				box_can[s_b + 1:]END,
CASEWHEN candidate != 0THEN todo[:i - 1] || todo[i + 1:]ELSE stack[sp][1] || todoEND,
CASEWHEN candidate != 0THEN set_byte(done, (r << 3) + r + c - 10, bit_count((candidate - 1)::bit(16))::int + 49)ELSE doneEND,
CASEWHEN candidate != 0THEN stack || ARRAY[ARRAY[(r << 8) | (c << 4) | b, candidates]]ELSE stack[:sp - 1]END,
CASEWHEN candidate != 0THEN CASE WHEN cardinality(todo) <= 1 THEN TRUE ELSE NULL ENDWHEN cardinality(stack) = 0 THEN FALSE-- 示例题库中最大检索深度只用459就够了，这里设定超65000才放弃-- 应该完全足够解出所有题目了，正确率比速度更重要，慢就慢点WHEN deep >= 65000 THEN FALSEELSE NULLEND
FROM search_tLEFT JOIN LATERAL (		(-- 先找1比sort limit 1更快SELECT i AS i_, r_, c_, b_, candidates_FROM generate_subscripts(todo, 1) t(i)CROSS JOIN LATERAL (SELECT todo[i] >> 8 AS r_, (todo[i] >> 4) & 0x0F AS c_, todo[i] & 0x0F AS b_			) AS search1_rcb_tCROSS JOIN LATERAL (SELECT row_can[r_] & col_can[c_] & box_can[b_] AS candidates_			) AS search1_can_tWHERE bit_count(candidates_::bit(16)) = 1			LIMIT 1		)UNION ALL		(WITH mrv_t AS (SELECT i AS i_, r_, c_, b_, candidates_, bit_count(candidates_::bit(16)) AS cntFROM generate_subscripts(todo, 1) t(i)CROSS JOIN LATERAL (SELECT todo[i] >> 8 AS r_, (todo[i] >> 4) & 0x0F AS c_, todo[i] & 0x0F AS b_				) AS search2_rcb_tCROSS JOIN LATERAL (SELECT row_can[r_] & col_can[c_] & box_can[b_] AS candidates_				) AS search2_can_t			),-- 找min值比sort limit 1更快			mrv_min_t AS (SELECT min(cnt) AS cnt FROM mrv_t			)SELECT i_, r_, c_, b_, candidates_FROM mrv_tJOIN mrv_min_tON mrv_t.cnt = mrv_min_t.cnt			LIMIT 1		)		LIMIT 1	) AS forward_t ON back = FALSELEFT JOIN LATERAL (SELECT1 AS i_,			todo[1] >> 8 AS r_,			(todo[1] >> 4) & 0x0F AS c_,			todo[1] & 0x0F AS b_,			back_can & (back_can - 1) AS candidates_	) AS backward_t ON back = TRUECROSS JOIN LATERAL (SELECTCOALESCE(backward_t.i_, forward_t.i_) AS i,COALESCE(backward_t.r_, forward_t.r_) AS r,COALESCE(backward_t.c_, forward_t.c_) AS c,COALESCE(backward_t.b_, forward_t.b_) AS b,COALESCE(backward_t.candidates_, forward_t.candidates_) AS candidates,			(COALESCE(backward_t.candidates_, forward_t.candidates_) &-COALESCE(backward_t.candidates_, forward_t.candidates_)) AS candidate,-- 这俩可能为NULL，为NULL时会判定为不可解，所以即使生成了一些NULL中间数据，会丢弃掉。我已确认不影响程序正确性			array_length(stack, 1) AS sp,			stack[array_length(stack, 1)][2] AS s_cand	) AS final_tLEFT JOIN LATERAL (SELECT			stack[sp][1] >> 8 AS s_r,			(stack[sp][1] >> 4) & 0x0F AS s_c,			stack[sp][1] & 0x0F AS s_b	) AS extra_t ON candidate = 0WHERE status IS NULL),search_rst_t AS (SELECT id, done FROM search_t WHERE status = TRUE)
SELECT	t.id AS id,	puzzle,	convert_from(		substr(done, 1,  9) || E'\n' ||		substr(done, 10, 9) || E'\n' ||		substr(done, 19, 9) || E'\n' ||		substr(done, 28, 9) || E'\n' ||		substr(done, 37, 9) || E'\n' ||		substr(done, 46, 9) || E'\n' ||		substr(done, 55, 9) || E'\n' ||		substr(done, 64, 9) || E'\n' ||		substr(done, 73, 9), 'UTF8'	) AS resultFROM sudoku9_9 tLEFT JOIN search_rst_t USING(id);