SQL を使って数独を解くやり方が CODEZINE の「動的SQLによる数独の超高速解法」に載っています。

なぜわざわざ SQL で解くか、それがアプリで SQL を書いているひとにどういう関係があるのか、と思われるかもしれませんね?!

数独というのは、ごぞんじかもしれませんが、パズルです。

つまり、”問題解決”であり、条件にあわせてきちんと処理していけば答えが出るものです。

解(”要件”)はどういうものかを定義し、それを得るために必要になる処理(”手続き”)を定義し、その手続きをプログラミングすることができる、というわけで、アプリをつくることの比喩として考えることができるんですね。

以前「SQL はRPG/400 の究極のかたち?!」などで、SQL では”要件”をそのまま書くだけで”手続き”の記述は必要ない、ということを紹介しました。

この SQL の性質が数独の解決にも有効である、ということが、まさしくこの「動的SQLによる数独の超高速解法」という記事のテーマなんです。

数独のようなパズルでも、結果としてほしいものを記述するだけでいい、という SQL の特徴が活かせるわけです。

RPG や Java などのプログラムで数独を解こうとすると、「それを得るために必要になる処理の定義」と「その手続きのプログラミング」がどうしても必要になります。

それがまったく不要になる、ということなんですね!

解決したいものがあれば、まずは「要件」の定義はいずれにしても必要なものです。

その上で、どうしたら解決できるかを考えるのと、プログラム可能なくらいにその手順を詰め、さらにそれをプログラミングするという作業があるわけですが、SQL の場合はこれがまるまる必要ない、ということになります。

つまり、最小限必要なものである「要件」の定義を記述してやればいいだけ、ということなんですね。手続きを考えてプログラミングしなければいけないことを考えれば、その分だけ生産性がよい、ということになるわけです。

カンのいい方は「でも実行時間はどうなの?」と思われるでしょう。

そうですね。「手間はかからないが、実行に時間がかかる…というんじゃダメだねぇ」との心配はごもっともです。

それが実際にやってみたのが、冒頭にご紹介した「動的SQLによる数独の超高速解法」なんです。

記事にも

コンピュータが考える実現方法の効率が気になるかもしれませんが、第2部で紹介した手続き的なコードでは30秒ほど、Pinskiさんのコードでは200秒ほどかかる問題を、本手法では約1秒で解くことができました(筆者の作業環境で測定しました)

とあります。

この引用の「第2部で紹介した手続き的なコード」も「Pinskiさんのコード」も SQL を利用したものなので”手続き型”のプログラムとの直接比較ではなりませんが、「難問」といわれている問題を「約1秒」で解けているので、効率が悪いということはないでしょう。

SQL というものの有用性を再認識できる記事になっていますので、ぜひ見てみてください。

ちなみに、ほぼ同様の内容が「SQLによる数独の解法とクエリオプティマイザの有効性」でよりまとまったかたちで読めるようになっています。

そこでは

「SQL は非手続き型の言語であるため,この解法には,数独の特定の問題におけるルールつまり空白に入る数に関する制約条件のみを記述すればよく,数独を解くための具体的な手続きを記述する必要はないという利点がある」

とまとめられていますが、まったくそのとおりですね!

この論文では「DB2 では解も実行プランも得られなかった」とありますが(この論文での DB2 は 9.7FP1 でした。ちなみに DB2 Express-C 10 でもやはり実行はできませんでした…)、DB2 for i では V5R4/V7R1 ともに実行できました(ほっ)。

↓ が実行したときの画面です。(V7R1)

image003

冒頭にご紹介した記事のダウンロード用のコードは MySQL 用の構文になっているので、テーブルの作成とデータの入力はプログラムからは省略したうえで実行しています。

テーブル作成とデータの入力は ↓ の SQL で準備できるので、よかったら実行してみてください。

CREATE TABLE nums (n INT NOT NULL PRIMARY KEY);

INSERT INTO nums VALUES (1);
INSERT INTO nums VALUES (2);
INSERT INTO nums VALUES (3);
INSERT INTO nums VALUES (4);
INSERT INTO nums VALUES (5);
INSERT INTO nums VALUES (6);
INSERT INTO nums VALUES (7);
INSERT INTO nums VALUES (8);
INSERT INTO nums VALUES (9);