SQLだけで数独を解く。

Oracle RDBMS 11gR2 - Solving a Sudoku using Recursive Subquery Factoring - AMIS Oracle and Java Blog
Oracleの公演資料を見ていたらOracleだけで数独を解けると書いてあったのだがなぜ解けるのか分からなかったので解析してみた。

対象のSQLなんだけども、こんなSQLで解けてしまうらしい。

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句で副問合せを宣言。後半でここから「ind=0」のものをSELECTしているだけなのでまずはこの副問合せを分析する。
副問合せの先頭で

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 )

としている。
ここはこれから解く数独のMapとInstrでその中に最初に出てくるスペースの位置を取得している。
そしてこの結果と以下の結果をUnionAllする

  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 to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z

Z副問合せは階層問合せを9段階行っている。なのでこの問合せ結果は

SQL> select to_char( rownum ) z
  2           from dual
  3           connect by rownum <= 9
  4  /

Z
----------------------------------------
1
2
3
4
5
6
7
8
9

9行が選択されました。

な感じ。
そしてこれとX自身の直積に対して以下の条件を除外していく

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 )

読み取ると、、ABCでないものを探している。
A:「Indから1引いたものを9で割り、切捨てしたものに9をかけたものに行番号を足した」ポジションにある文字列でない
B:「Indから1引いたものを9で割った余りから8を引き、行番号に9かけた」ポジションにある文字列でない
C:「Indから1引いたものを3で割り、切捨てしたものを3でわった余りに3をかけた」ポジション+
  「Indから1引いたものを27で割り、切捨てしたものに27をかけたものに行番号を足した」ポジション+
  「行番号から1引いたものを3で割り、切り捨てたしものに6をかけた」ポジション
これを1つの基準Indから9回行う。(階層問合せ分)
するとどうなるかというと、、
分かりやすいように図示すると、、

となる。つまり数独における競合してはいけない箇所に存在しない数字を拾ってきているということになる。

そして以下のSQLで次の空白の検索に入る。

select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) , instr( s, ' ', ind + 1 )

つまり「先頭の空白から1つづつ入る可能性のある文字を全部入れて行き、最終的にind=0となるつまり全ての文字が埋まったものを回答としている。*1」ということでした。
SQLでこんなこと出来るんだとかなり関心させられました。

やっぱOracleはおもしろいな〜

*1:つまり、解けない問題を入れた場合無限ループで帰ってこないのでCPU振り切ったりしないように気をつけましょう。