読者です 読者をやめる 読者になる 読者になる

スパコンで力任せに作った数独の難しい問題をSQLで力任せに解くとどうなるか

http://apollon.issp.u-tokyo.ac.jp/~watanabe/sample/sudoku/index_j.htmlというのがあってハテブで人気になっていたので、SQLで解いてみた。

まずおさらいとして、どうやってSQLだけで数独を解くかってことなんだけど、SQLで解いているのでまさに力技です。先頭の空白から1つづつ入る可能性のある文字を全部入れて行き、最終的に全ての文字が埋まったものを回答としてます。
詳しくはSQLだけで数独を解く。 - 自分の仕事を憎むには人生は余りにも短いを見てください。

SQLとしては以下のようなSQLになります。

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select ' 61  7  3 92  3              853          5 45    8    4      1   16 8  6        ' 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
/

で、解いてみたところ、、、

経過: 00:33:22.98

所要時間33分22秒!!!
普通の問題は数秒で解けるので、相当難しいということがわかります、
ただ、これは総当たりで解いた場合でこの問題は真面目に数独として解くと結構簡単に解けちゃう。
パソコンが人間を超えるのはまだまだかかりそうですね。