高速化
バックトラックを実装したので、すべての数独の問題を解くことができるようになりました。しかしながら、実装をかなり単純なものにしていたため、かなりの無駄があるのも事実です。本稿の最後でAlEscargotを解きますが、この段階の実装では1分ほどかかってしまいます（それでもCALCULATE_GS_V3よりは速いのですが）。そこで、アルゴリズムを少し改良しましょう（「はじめに」で述べたように、本稿ではアルゴリズムを工夫することにはあまりこだわりません）。
プロシージャ:makeCandidatesの改良
空白だったところに数字が入ると、他の空白部分に入る数字の候補（つまりテーブル「candidates」の内容）も変わります。これまでは、テーブル「candidates」を更新する際、すべてを削除してから新たにデータを挿入していました。これは明らかに無駄です。ルールに反する数字を削除するだけで十分です（追加した部分を太字で示しています）。
DROP PROCEDURE IF EXISTS makeCandidates// CREATE PROCEDURE makeCandidates(theId INT) BEGIN DECLARE f INT; -- 既に候補が求められているかどうかをチェック SELECT COUNT(*) INTO f FROM candidates WHERE id=theId; IF f=0 THEN -- 求められていない場合は前と同じ INSERT INTO candidates SELECT theId AS id,a.n AS row,b.n AS col,c.n AS val FROM nums a,nums b,nums c WHERE EXISTS ( SELECT * FROM problems WHERE id=theId AND val=0 AND row=a.n AND col=b.n) AND NOT EXISTS ( SELECT * FROM problems WHERE id=theId AND val=c.n AND (row=a.n OR col=b.n OR ((row-1) DIV @m=(a.n-1) DIV @m AND (col-1) DIV @m=(b.n-1) DIV @m))); ELSE -- 求められているなら、新たに無効になった候補を削除 DELETE FROM candidates WHERE id=theId AND EXISTS ( SELECT * FROM problems b WHERE id=theId AND ((b.val!=0 AND b.row=candidates.row AND b.col=candidates.col) OR (b.val=candidates.val AND (b.row=candidates.row OR b.col=candidates.col OR ((b.row-1) DIV @m=(candidates.row-1) DIV @m AND (b.col-1) DIV @m=(candidates.col-1) DIV @m))))); END IF; END;//
ファンクション:copyProblemの改良
ある盤面で数字を決定できるマス目がなくなったら、その盤面をコピーして、空白に入る数字を仮定して先に進みます。盤面をコピーしても、新しい盤面の空白に入る数字の候補は一から新たに求めていました。これは無駄です。古い盤面についての数字の候補は、新しい盤面でも大体使えるはずです。そこで、盤面をコピーする際に、候補の数字もコピーするようにしましょう。
DROP FUNCTION IF EXISTS copyProblem// CREATE FUNCTION copyProblem(theId INT,r INT,c INT,v INT) RETURNS INT MODIFIES SQL DATA BEGIN DECLARE newId INT; SELECT MAX(id)+1 INTO newId FROM problems; INSERT INTO problems SELECT newId AS id,row,col,val FROM problems WHERE id=theId; UPDATE problems SET val=v WHERE id=newId AND row=r AND col=c; INSERT INTO candidates SELECT newId AS id,row,col,val FROM candidates WHERE id=theId; RETURN 1; END;//
AlEscargot
いよいよAlEscargotに挑戦しましょう。「はじめに」で紹介したように、これはかなりの難問で、『高パフォーマンスなストアドプロシージャの設計』の著者Pinskiさんは、この問題を（筆者の環境で）約200秒かけて解くコードを「まずまず高速」だと評されています。
CALL initialize(CONCAT( '1 7 9 ', ' 3 2 8', ' 96 5 ', ' 53 9 ', ' 1 8 2', '6 4 ', '3 1 ', ' 4 7', ' 7 3 '))// CALL solve()//
1 6 2 8 5 7 4 9 3 5 3 4 1 2 9 6 7 8 7 8 9 6 4 3 5 2 1 4 7 5 3 1 2 9 8 6 9 1 3 5 8 6 7 4 2 6 2 8 7 9 4 1 3 5 3 5 6 4 7 8 2 1 9 2 4 1 9 3 5 8 6 7 8 9 7 2 6 1 3 5 4 1 row in set (33.77 sec) Query OK, 0 rows affected, 1302 warnings (39.02 sec)
このように、本稿で紹介したコードは、AlEscargotを40秒程度で解くことができます。
PinskiさんのコードはSQL Server用のものなので、正しく比較するために、本稿で紹介したコードをSQL Server用に書き直して実験したところ（「sqlserver.sql」にまとめてあります）、AlEscargotを約25秒で解くことができました。
おわりに
SQLを用いて数独を解く方法を紹介しました。
「宣言的に書く。つまり何が欲しいのかを書くのであって、どのように得るかを書くのではない」というのがSQLの基本です。ここで紹介した方法は、個々のステップは宣言的でfor文のような繰り返しの制御文はほとんどありませんが、全体としては手続き的、つまりプログラマが数独の解法を細かく指示する形になっています。
CALCULATE_GS_V3と比べれば、コードのサイズが約1/3、速度が約6倍になったわけですが、それでも「たかが数独のためにずいぶん大がかりな作業が必要だな」とか「速くなったと言っても30秒もかかるのか」という感想を持つ方もおられるでしょう。第3部ではこれらの不満を解消するために、全体の宣言的な記述を試みます。本稿と比較することによって、宣言的に書くということがどういうことなのかが明らかになるでしょう。
参考資料
- MySQLがストアド・プロシージャをサポートしたのは最近（バージョン5以降）のことなので、資料はあまり多くありません。まずはウェブ上のリファレンス・マニュアルを参照してください。
- SQLによるプログラミングの基本については、拙著『初級プログラマのためのWebアプリケーション構築入門 - 実践で学ぶJava,XHTML,SQL』（森北出版、2007年）を参照してください。
- 単なるデータの保管場所としてではないリレーショナル・データベースの使い方については、Antbony Molinaro著, 木下哲也ほか訳『SQLクックブック』（オライリージャパン 2007）が参考になります。
- ジョー・セルコ著, 秋田昌幸訳『プログラマのためのSQL』（ピアソン・エデュケーション 2001）は、SQLについての発展的な話題を数多く扱っています。同著者のJoe Celko's SQL Puzzles and Answers (Morgan Kaufmann, 2nd edition, 2007)で紹介されている数独の解法は、第1部の「解法1」と同等なので、難しい問題は解けません。
