はじめに
SQLを使って数独（ナンプレ）を解く方法の第3部です。本稿では、数独を宣言的な動的SQLによって高速に解く方法を紹介します。他の2編を読まなくても本稿を理解することはできるようになっていますが、他の2編と本稿を比較することによって、本稿の手法の特徴をよりよく理解できるはずです。
- SQLによる数独の解法
- SQLによる数独の高速解法
- 動的SQLによる数独の超高速解法（本稿）
「宣言的」というのは、「何が欲しいのかだけを書き、どのように得るかは書かない」という意味です。「動的SQL」というのは、実行時にSQL文を生成するという意味です。「高速」というのは、Gene Pinski著 『高パフォーマンスなストアドプロシージャの設計』で公開されているコード（以下、CALCULATE_GS_V3）や、先に紹介した2編の方法と比べてのことです。
実際にどのくらいのパフォーマンスになるかを表にまとめました。Pinskiさんの記事で紹介されている難問「AlEscargot」を解くのにかかる時間です。測定は筆者の環境（Athlon64 X2 3800+、2GB Memory、Windows XP 32-Bit、RDBMSのチューニングは無し）で行いました。
| MySQL | SQL Server | |
| CALCULATE_GS_V3 | 200秒 | |
| 別稿（第2部） | 40秒 | 25秒 |
| 本稿（第3部） | 1秒 | 1秒 |
Pinskiさんの記事は、「SQLで数独を解ける」ことを示したという点で評価できます。しかしながら、そのためのコードと実行時間が共に長大であるため、「SQLは面倒で遅い」という誤解を読者に与えかねません。本稿で紹介する方法で、誤解が払拭されることを期待します。
第1、2部と第3部の手法を簡単にまとめておきましょう。
第1、2部では、手続き的な記述、つまり、どうすれば数独の解が得られるかの具体的な記述によって数独を解いています。手続き的とは言っても、せっかく宣言型言語であるSQLを使うので、手順の各ステップはなるべく宣言的に記述するように心がけています。
第3部（本稿）の方法の本質はたった1行のSELECT文です。このSELECT文には「数独の解とはどういうものか」だけが記述してあり、その解を得るための具体的な方法はコンピュータが考えます。ただし、このSELECT文は人間が手で簡単に書けるようなものではないため、プログラムを使って生成します（プログラムでプログラムを生成するという意味で、本稿はメタ・プログラミングの紹介にもなっています）。SELECT文の生成も宣言的な方法で行うのが理想ですが、本稿では手続き的に行います。
対象読者
- 計算機でパズルを解くことに興味のある方
- 数独を知っている方（数独自体についての説明はしません）
- メタ・プログラミングが好きな方
- SQLのSELECT文の基本を知っている方
- 他のプログラミング言語からリレーショナル・データベース管理システム（RDBMS）を使う方法、あるいは、ストアド・プロシージャの書き方を知っている方
必要な環境
先本稿で紹介するのは、「SQL文を動的に生成し、生成したSQL文を実行する」という方法です。必要な環境は、この方法のどの部分を試したいかによって異なります。
とりあえずできあがったSQL文を実行してみたい場合
適当なRDBMSがあれば可能です。筆者の環境で数秒程度で実行できることを確認したのは以下のRDBMSです（DB2ではうまく動きませんでした）。
- Derby（Java 6に付属しているJava DB）
- MySQL 5.0.37
- Oracle 10g Express Edition
- PostgreSQL 8.2
- SQLite（Google Gearsにも付属しているもの）
- SQL Server 2005
他のプログラミング言語でSQL文を生成したい場合
RDBMSへの接続をサポートしているプログラミング言語なら、本稿で紹介する方法を簡単に実現できます。本稿で紹介する方法をそのまま実行したい場合には以下が必要です。
- Java（バージョン5以上）
- MySQL 5.0
- MySQL用のJDBC (MySQL Connector/J)
ストアド・プロシージャでSQL文を生成したい場合
ストアド・プロシージャをサポートしているRDBMSなら、本稿で紹介する方法を実現できます。本文中のストアド・プロシージャはMySQL 5.0用のものです（本文からコードだけを抜き出して「mysql-meta.sql」にまとめてあります）。SQL Server 2005版「sqlserver-meta.sql」も別に用意しました（SQL Server版は9×9以外の盤面には対応させていません）。
SQLを用いた虫食い型パズルの解法
覆面算
いきなり数独を解くのは大変なので、まずは覆面算で練習しましょう。覆面算とは、数字が文字で隠されたような数式中の、隠された数字を推測する問題です。例を挙げましょう（この例は、佐野昌一「虫喰ひ算大會」から借りました）。
2N8 + 2N2 + 88N + N2N = 2164（例題2）
少し考えると暗算でも分かるのですが、代わりに計算機に考えてもらいましょう。ただし、数式をコードに置き換える作業は人間がやることにします。
C言語なら次のように書けます（nが0でないという条件が本当は必要です）。
#include <stdio.h> int main(){ int n; for(n=0;n<10;++n){ if((208+10*n) + (202+10*n) + (880+n) + (n*100+20+n) == 2164) printf("n = %d\n",n); } }
同じ問題をSQLで解いてみます。まず、準備としてテーブル「nums」に0から9までの数字を入れておきます。
DROP TABLE IF EXISTS nums; CREATE TABLE nums (n INT NOT NULL PRIMARY KEY); INSERT INTO nums VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
次のようなSELECT文によって解が得られます。数字の候補の列挙に必要なC言語版のfor文が、SQL版では無くなっていることに注目してください。
SELECT n FROM nums WHERE (208+10*n) + (202+10*n) + (880+n) + (n*100+20+n) = 2164; +---+ | n | +---+ | 7 | +---+
数字の組み合わせ
もう少し複雑な例で確認しましょう。
AB7 - 7BA = 1AB（第二十四會場の1）
C言語では次のように書けます。
#include <stdio.h> int main(){ int A,B; for(A=0;A<10;++A){ for(B=0;B<10;++B){ if((A*100+B*10+7) - (700+B*10+A) == (100+A*10+B)) printf("A = %d, B = %d\n",A,B); } } }
SQLでは次のとおりです。
SELECT A.n AS A,B.n AS B FROM nums A,nums B WHERE (A.n*100+B.n*10+7) - (700+B.n*10+A.n) = (100+A.n*10+B.n); +---+---+ | A | B | +---+---+ | 9 | 8 | +---+---+
C言語では「探し方」をfor文で指示しなければならないのですが、SQLでは「欲しいもの」をSELECTの後に、その条件をWHEREの後に書くだけです。FROMの後に、「nums A,nums B」のように書くことで、すべての組み合わせを試すことができます（1つのテーブル「nums」を2回使っているので、区別するためにA、Bという名前を付けています）。
覆面算がもっと複雑になったらどうでしょう。不適当な解を早めに除外するための、ケタごとの条件が必要になるのですが、それらはすべてWHERE節にまとめて書くことができます。これは、すべての条件を一番深いfor文の中に書くととても遅くなるC言語との大きな違いです。
この章で説明したことをまとめます。
- SQLでは「何が欲しいか」を書く。C言語の
for文のような「どのように得るか」を書く必要はない。 - 「
FROM nums A,nums B」のような直積によって、数字の組み合わせをつくることができる。
