Oracleで数独を解く
Oracleで数独が解けるらしいが読んでも意味がわからなかったので細かく調べてみる。
以下は11g以上のoracleで実行可能です。
元記事
問題
この問題を左上から右方向に一行ずつ並べて空白は半角スペースといった感じで一つの文字列にして表現します
'53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79'
答え
with x( s, ind ) as
( select sud, instr( sud, ' ' )
from ( select '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' sud from dual )
union all
select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
, instr( s, ' ', ind + 1 )
from x
, ( select to_char( rownum ) z
from dual
connect by rownum <= 9
) z
where ind > 0
and not exists ( select null
from ( select rownum lp
from dual
connect by rownum <= 9
)
where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
+ trunc( ( ind - 1 ) / 27 ) * 27 + lp
+ trunc( ( lp - 1 ) / 3 ) * 6
, 1 )
)
)
select s
from x
where ind = 0
解説
何がなんやらよくわかりませんがまずwith句から説明を始めましょう
再帰WITH句
SQLで再帰書けるってだけでもちょっと驚きですが以下を引用して説明してみます。
http://www.oracle.com/technetwork/jp/articles/otnj-sql-image7-1525406-ja.html#a
簡単な再帰WITH句を例に出します。
WITH rec(STR) AS (
SELECT CAST('A' AS VARCHAR(20))
FROM dual
UNION ALL
SELECT CONCAT(STR, 'A')
FROM rec
WHERE LENGTH(STR) < 5)
SELECT STR
FROM rec;
まずwith rec(STR)は
recはテーブル名 STRはカラム名です。
次にwith句の中を見て下さい。
UNION ALLで区切られた2つのSELECTクエリがありますが、
それぞれ前者を非再帰項。後者を再帰項と呼びます。
再帰with句は、最初に非再帰項のselectを実行して、
そのselect文の結果を使って再帰項のselectを実行して、
そのselect文の結果を使って再帰項のselectを実行して・・・・
結果が0件になるまで実行され続けます。
この場合最初に非再帰項で'A'という一つのレコードが返されそれを再帰項に渡し、
長さが5を超えるまで'A'を結合してレコードを返してというのを繰り返します。
WITH句がなかなかすごいことがわかると思います。
数独も解ける気がしてきます。
再帰を使って数独を解く
それでは簡単なクエリから順番に肉付けして回答のクエリを組み上げていきます。
数独の解き方
先頭のスペースに1-9の数字を埋めたものを作り、それが数独のルールに合わなければ省く。
これを繰り返しスペースが0になればそれが答えとなります。
1-9の数字表を作る
SELECT rownum z
FROM dual
CONNECT BY rownum <= 9
CONNECT句が使われていますがこれも再起処理（階層問い合わせ）を行えるクエリです。
connect by句はその後に続く条件が満たされる限り行を生成していきます。
これにより9までの値を格納した表を作成することができました
スペースを数字で埋める
再起クエリを作って2個のスペースを1か2で埋めるクエリを作ってみます。
WITH rec(s, ind) AS (
SELECT sud, instr(sud, ' ')
FROM (SELECT '[ ][ ]' sud FROM dual)
UNION ALL
SELECT
(substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
instr(s, ' ', ind + 1)
FROM rec, (
SELECT to_char(rownum) z
FROM dual
CONNECT BY rownum <= 2
) z
where ind > 0
)
SELECT s
FROM rec
先ほど作った数値表の条件を変更して2までの数値表にした上で等価結合し、
(substr(s, 1, ind - 1) || z || substr(s, ind + 1)),これでスペースの前後で区切って数値表の数値と置換しています。
これではスペースが残った物も計算結果に出ているので先ほどのクエリの最後に条件を追加して排除しましょう
WHERE ind = 0;
これで全ての空白マスを1-9で埋めることが出来るようになりました。
不正解の数独を排除する
数独のルールを復習します。
- 横に1-9が揃うこと
- 縦に1-9が揃うこと
- 左上から順に3*3で区切った格子のそれぞれの部屋に1-9までの数字が揃うこと
これを満たす数字でスペースを埋めていけばゴールに辿り着くことになります。
よってWITHの再帰項の部分は先のルールで埋める数字を選択し且つスペースがまだ残っている場合、
結果を返していけば最後にはスペースを含まないルールに反しない文字列が出来上がり、再帰処理が終了します。
ルールに反しない数字で埋める
先ほど1-9の数字で埋める方法がわかりましたがこれを「ルールに反しない数字」で埋めるように書き換えます。
まず横列を検証するルールを作ってみましょう。
先ほどまでに作ったクエリを少し修正して数独の一行目の最後だけ埋まってない文字列を与えてみます。
WITH rec(s, ind) AS (
SELECT
sud,
instr(sud, ' ')
FROM (SELECT '12345678 ' sud
FROM dual)
UNION ALL
SELECT
(substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
instr(s, ' ', ind + 1)
FROM rec, (
SELECT to_char(rownum) z
FROM dual
CONNECT BY rownum <= 9
) z_t
WHERE ind > 0
)
SELECT s
FROM rec
WHERE ind = 0;
これをこのまま実行すると9列の結果がでますがこの内8個は横列の条件が満たせていません。
ではこれを排除するようにNOT EXISTSを使って横列に含まれている数字を除外してみましょう。
WITH rec(s, ind) AS (
SELECT
sud,
instr(sud, ' ')
FROM (SELECT '12345678 ' sud
FROM dual)
UNION ALL
SELECT
(substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
instr(s, ' ', ind + 1)
FROM rec, (
SELECT to_char(rownum) z
FROM dual
CONNECT BY rownum <= 9
) z_t
WHERE ind > 0 AND NOT EXISTS(SELECT NULL
FROM (SELECT rownum lp
FROM dual
CONNECT BY rownum <= 9)
WHERE z = substr(s, lp, 1))
)
SELECT s
FROM rec
WHERE ind = 0;
NOT EXISTSの中にまたCONNECTが現れていますがこれもまた1-9の数字の表を作っています。
そして作った表をsubstrの第二引数に当てることでs(='123456789 ')から一文字ずつ取り出し
存在するものをNOT EXISTSでz_tテーブルから除外しています。
試しに複数の数字を抜いて'1 34 678 'などでも実行してみると条件を満たさない数値は除外されていることがわかります。
あとは本来の数独は複数行あり、更に縦条件と格子条件があるのでそれをこのNOT EXISTS句に盛り込むと最初のクエリにたどり着けます。
まとめ
SELECT文をちょろちょろ書いてWEBアプリ作ってるだけの人間なので、こんなことが出来たのは驚きでした。
SQL奥が深い・・・