2014/08/23
PostgreSQL > 数独を再帰クエリとウィンドウ関数で解く
PostgreSQL > 数独を再帰クエリとウィンドウ関数で解く
一昨日までの R でのグラフィカルな処理とは一変して、PostgreSQL の再帰クエリとウィンドウ関数、あと配列も使ってストアド関数を作った。実行環境は 2014/08/13 の実機を参照。既にウェブ上で再帰クエリで解く例がいくつかあり二番煎じだが、難しい問題もなるべく速く解けるよう、R でやった方法を一部取り入れた。
関数の定義文は後掲。↓ 実際に二問解いた様子。動画の原寸は 700x465 で文字も小さいけど見れる。問題は一昨日と同様 About.com - Puzzles から拝借。
動画 : https://kenpg.up.seesaa.net/image/20140823_sud_1.flv
↓ 一問目・二問目の実行結果。画像を別ウィンドウで開けば原寸になる。所要時間はそれぞれ2秒弱、4秒弱。同じ二問を一昨日の R のスクリプトで解いたら、それぞれ約9.3秒、約2.8秒だった（グラフィカルな数字描き換えや待機時間は無し）。解き方の工夫は R スクリプトの方が多いが、問題との「相性」によるのか今回のストアドの方が速い場合も結構あった。
上で出力されている各行は、試行錯誤の経過を処理順の逆で並べてたもの。つまり先頭行が完成した結果。この行数が多いほど試行錯誤が多く回り道している。難しい問題だと何万行にもなるので、デフォルトでは完成形の一行だけ出力する。経過を表示する場合は第二引数に TRUE を指定。↓ 関数の定義文全体。
以下、処理の概略。↓ まず一昨日 の R スクリプトと同様に全セルの情報を一行ずつの表にまとめる。これが関数本体での c ブロックまでに当たる。列 n が左上 → 右下の順のセル番号、i が行番号、j が列番号、blk がブロック番号、num が確定済の数字。一回の試行錯誤のたびにこの表を作り、最も埋め易そうなセルを探す。
上の表をもとに、各セルに入らない数字（同じ行か列かブロックで既に使われている数字）を配列にまとめる ↓ のが、関数本体での d ブロック。この配列の要素数が多いセルほど、入力候補が少ないので埋め易いと考えて処理していく。
上の二クエリは単純化していて、実際は入力候補のグループごとにまとめて再帰クエリでぐるぐる回す。その際、グループごとに入力候補が最小の行を全て選ぶのにウィンドウ関数の dense_rank を使う。関数本体では e ブロック。文章で書くのは厳しいので、詳細はまたいずれ。
関数の定義文は後掲。↓ 実際に二問解いた様子。動画の原寸は 700x465 で文字も小さいけど見れる。問題は一昨日と同様 About.com - Puzzles から拝借。
動画 : https://kenpg.up.seesaa.net/image/20140823_sud_1.flv
↓ 一問目・二問目の実行結果。画像を別ウィンドウで開けば原寸になる。所要時間はそれぞれ2秒弱、4秒弱。同じ二問を一昨日の R のスクリプトで解いたら、それぞれ約9.3秒、約2.8秒だった（グラフィカルな数字描き換えや待機時間は無し）。解き方の工夫は R スクリプトの方が多いが、問題との「相性」によるのか今回のストアドの方が速い場合も結構あった。
上で出力されている各行は、試行錯誤の経過を処理順の逆で並べてたもの。つまり先頭行が完成した結果。この行数が多いほど試行錯誤が多く回り道している。難しい問題だと何万行にもなるので、デフォルトでは完成形の一行だけ出力する。経過を表示する場合は第二引数に TRUE を指定。↓ 関数の定義文全体。
CREATE OR REPLACE FUNCTION "201408"."23_sudoku_1"(text, bool DEFAULT FALSE)
RETURNS TABLE (cnt1 int, cnt2 int, sud text) LANGUAGE sql IMMUTABLE AS $$
-- 数独を解く
-- 第一引数 問題文字列
-- 第二引数 経過表示フラグ
WITH RECURSIVE r AS (
SELECT 1 cnt1, $1 sud
UNION ALL
(
WITH a AS (
SELECT cnt1, sud, row_number() over() :: int gid
FROM (
SELECT *, rank() over(ORDER BY cnt1 DESC) FROM r
) x WHERE rank = 1
), b AS (
SELECT generate_series(1, 9) num
), c AS (
SELECT gid
, (b1.num - 1) * 9 + b2.num n
, b1.num i, b2.num j
, (b1.num - 1) / 3 * 3 + 1 + (b2.num - 1) / 3 blk
, substr(sud, (b1.num - 1) * 9 + b2.num, 1) num
FROM a, b b1, b b2
), d AS (
SELECT c2.gid, c2.n
, array_agg(DISTINCT c1.num :: int) num_used
FROM c c1, c c2
WHERE c1.num <> ' '
AND c2.num = ' '
AND c1.gid = c2.gid
AND (c1.i = c2.i OR c1.j = c2.j OR c1.blk = c2.blk)
GROUP BY c2.gid, c2.n
), e AS (
SELECT *, dense_rank() over(
PARTITION BY gid
ORDER BY array_length(num_used, 1) DESC, n)
FROM d
)
SELECT cnt1 + 1, overlay(sud placing num :: text FROM n FOR 1)
FROM a, b, e
WHERE a.gid = e.gid
AND dense_rank = 1 AND num <> ALL(num_used)
)
), s AS (
SELECT cnt1, count(*) over() :: int, sud FROM r
)
SELECT * FROM s
WHERE $2 OR strpos(sud, ' ') = 0
ORDER BY 1 DESC ;
$$ ;
以下、処理の概略。↓ まず一昨日 の R スクリプトと同様に全セルの情報を一行ずつの表にまとめる。これが関数本体での c ブロックまでに当たる。列 n が左上 → 右下の順のセル番号、i が行番号、j が列番号、blk がブロック番号、num が確定済の数字。一回の試行錯誤のたびにこの表を作り、最も埋め易そうなセルを探す。
WITH a AS (
SELECT text ' 9 4 327 5 8 32 6187 2 52 591 83 8 6491764 '
|| '2 719 5324328149756' sud
), b AS (
SELECT generate_series(1, 9) num
)
SELECT (b1.num - 1) * 9 + b2.num n
, b1.num i, b2.num j
, (b1.num - 1) / 3 * 3 + 1 + (b2.num - 1) / 3 blk
, substr(sud, (b1.num - 1) * 9 + b2.num, 1) num
FROM a, b b1, b b2 ;
上の表をもとに、各セルに入らない数字（同じ行か列かブロックで既に使われている数字）を配列にまとめる ↓ のが、関数本体での d ブロック。この配列の要素数が多いセルほど、入力候補が少ないので埋め易いと考えて処理していく。
WITH a AS (
SELECT text ' 9 4 327 5 8 32 6187 2 52 591 83 8 6491764 '
|| '2 719 5324328149756' sud
), b AS (
SELECT generate_series(1, 9) num
), c AS (
SELECT (b1.num - 1) * 9 + b2.num n
, b1.num i, b2.num j
, (b1.num - 1) / 3 * 3 + 1 + (b2.num - 1) / 3 blk
, substr(sud, (b1.num - 1) * 9 + b2.num, 1) num
FROM a, b b1, b b2
)
SELECT c2.n, array_agg(DISTINCT c1.num :: int) num_used
FROM c c1, c c2
WHERE c1.num <> ' '
AND c2.num = ' '
AND (c1.i = c2.i OR c1.j = c2.j OR c1.blk = c2.blk)
GROUP BY c2.n ;
上の二クエリは単純化していて、実際は入力候補のグループごとにまとめて再帰クエリでぐるぐる回す。その際、グループごとに入力候補が最小の行を全て選ぶのにウィンドウ関数の dense_rank を使う。関数本体では e ブロック。文章で書くのは厳しいので、詳細はまたいずれ。