SQLを使ってナンプレを解かせてみようとした話

何を思ったのか、勉強がてらSQLでナンプレを解けないか試してみることにした。

準備

・テーブルを作成する。(testとする)
・項目はitem1、item2・・・item9とする。
・各項目に、1〜9の数字が重複しないようにデータを作成する。(362880件)

図：テストテーブル

理屈としては、このテーブルに格納されている行を9行うまく組み合わせたものが答えになる（はず）。ので、そのためのSQLを考えた。

SQLの検討

入力として、解きたいナンプレの課題を与えられた時、SQLを行ごとに考えてみた。
まず1行目を次のように表す。

select * from
(select * from test
 where item1 = *
   and item2 = *
　　・
　　・
　　・
   and item9 = *) row1

where句の* は、与えられた課題ね。
同様に、row2、row3、・・・row9までをselectしたテーブルを結合する。

select * from
(select * from test
 where item1 = *
   and item2 = *
　　・
　　・
　　・
   and item9 = *) row1
,
(select * from test
 where item1 = *
   and item2 = *
　　・
　　・
　　・
   and item9 = *) row2
,
　　・
　　・
　　・
(select * from test
 where item1 = *
   and item2 = *
　　・
　　・
　　・
   and item9 = *) row9

これだけだと、取得件数が天文学的数値となり、完全にクエリがフリーズするので、
ナンプレの要件
①各列の値は重複しない
②各ブロック(例1〜3行、1〜3列)の値は重複しない
を条件句に追加する。

上記①について、1列目の条件を書くとこんな感じ。これが9列分必要。

where
  -- 1列目の値は重複しない
      row1.item1 <> row2.item1
  and row1.item1 <> row3.item1
  ・
　・
　・
　and row1.item1 <> row9.item1
　  --2行目の1列目の値は重複しない　　
  and row2.item1 <> row3.item1
  and row2.item1 <> row4.item1
  ・
　・
　・
　and row2.item1 <> row9.item1
　・
　・
　・
　 --8行目の1列目は重複しない
  and row8.item1 <> row9.item1

②については、イメージこんな感じ。
これを9ブロックに属する各値について追加する。

--左上のブロックの1列目は、2行目の2、3列目、3行目の2、3列目と重複しない
and row1.item1 <> row2.item2
and row1.item1 <> row2.item3
and row1.item1 <> row3.item2
and row1.item1 <> row3.item3

こうして作成されたSQLを実行すると、解がもとまるはず…！

試しに愛用しているiPhoneアプリのむずかしい問題を解かせてみた。

カンマ区切りのテキストファイルで入出力できるようにし、プログラム実行。
数分後、回答が出力された！

しかし、更に高難易度の問題を読み込ませようとすると、フリーズしてしまった。

ChatGPTさん曰く、SQLは数独のようなパズルを解くために最適化されていないため、非常に複雑なクエリになります。プログラミング言語を使用してアルゴリズムを実装する方が効率的な場合が多いです、とのこと。ごもっともである。

誤りや、もっといい方法があればご教示頂けると幸いです。