SQLによる数独の解法


SQLを使って数独を解く方法の解説記事を書きました。3部構成のうちの第1部がCodeZineで公開されています

  1. SQLによる数独の解法
  2. SQLによる数独の高速解法(9/11に公開)
  3. 動的SQL数独の超高速解法(9/18に公開)

ナンプレ VOW

この記事を書くきっかけになったのは、Nintendo DSのゲーム「ナンプレ VOW」です。巷で売られている数独の問題はかなり簡単で、あまり頭を使わずに解けるのですが、解くときの爽快感と、VOWのおもしろさのために、つい何時間かはまってしまいました

ちなみに、少し頭を使わないと解けない問題は商品にならないそうです。難問を集めたはずの『激辛数独1』にさえ、次のような記述があります(試行錯誤が推理に含まれないのか、などということは別にしても私には納得できないのですが)

本書のすべての問題は、試行錯誤(このマスがもし○ならば、こうなってこうなってダメなので△我はいる。というような解き方)をすることなく、推理力を駆使して解けるようになっています

はまってしまったパズルゲームから抜け出す手段として、「パズルを解くプログラムを書く」というものがあります。「コンピュータで簡単に解けるようなパズルで時間を浪費するな」と自分を説得するのです(私にも「機械を差別する心」があるようです)

プログラムは簡単に書けるのでそれで終わりだったはずなのですが(せいぜい「数独ウォッチ」につっこみを入れるくらい)、ふと読んだこんな文章にひっかかりました

ここで示した解法プログラムは、まずまず高速です。図1の「Ai Escargot」パズルを2.4GHzのCPUと1GBのRAMを搭載したマシンで解いたところ、5分20秒で解答が導かれました。(高パフォーマンスなストアドプロシージャの設計

これはSQLのストアド・プロシジャの書き方を解説した記事なのですが、例題として取り上げた数独の問題を解くのに、5分20秒もかかったというのです

一度プログラムを書いているので、今のコンピュータなら数独を解くのにそんな時間はかからないということはすぐにわかります。読んだ人が「SQLダメじゃん」と思ってしまわないかも心配でした(はい、SQL好きです)。そこで、「こうやって書けば速いんじゃないかな」という方法を紹介することにしたのです

どのくらい速くなるかは第3部でのお楽しみということで

(CodeZineがMS系フォントをスタイル指定するのをやめますように)

論文:矢吹太朗, 佐久田博司. SQLによる数独の解法とクエリオプティマイザの有効性. 日本データベース学会論文誌. Vol.9, No.2, pp.13–18, 2010.

上記論文ではDB2では実行できないと報告していますが、「DB2 for IBM i でも数独が解ける!?」によれば、より新しいバージョンでは大丈夫だそうです。

参考:数独の平凡な解法(C言語Mathematica

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です