はじめに
SQLを使って数独（ナンプレ）を解く方法を紹介します。
データベースを操作するための言語であるSQLを別の用途に使おうとする理由は、SQLが宣言的な記述が可能な言語の中で最も普及していると思われるからです（宣言的言語と言えばPrologを思い浮かべる方も多いかもしれませんが、残念なことにPrologは、SQLほどには普及していません）。
まず、宣言的な記述について説明しましょう。タクシーに乗ることを想像してください。「渋谷に行ってください」というように、欲しい結果を書くのが宣言的な記述です。具体的な道筋は運転手が考えてくれます。それに対して「まずA通りを北に行って、B交差点を左折して・・・」というように、具体的な道筋を示すのは手続き的記述です。プログラミング言語の場合も同様です。SQLやPrologにおいては、欲しい結果をプログラマが書けば、具体的な実現方法はコンピュータが考えてくれます。C言語やJava、Rubyといった今日汎用的に使われている言語の多くは手続き型言語です。
SQLのSELECT文を思い出してみてください。SELECT文は「欲しいものを書く」の典型例です。同じ事を手続き型言語で行うためには、ループの中でデータを読みながら条件を調べるというような操作をすべてプログラマが書かなければなりません。
プログラミング言語の抽象化にはいろいろな方向があります。例えば、C言語からJava、JavaからRubyという流れは手続きの抽象化と言っていいでしょう。これとは別の方向に、手続き型から宣言型へという抽象化もあるのです。抽象度の高い言語を好まれる方は、ぜひこちらの方向も試してもらいたいと思います。
ここではSQLで数独を解くことを通じて、宣言的言語を紹介したいと思います。全体は以下の3編からなります。
- SQLによる数独の解法（本稿）
- SQLによる数独の高速解法
- 動的SQL数独の超高速解法
宣言的記述の特徴が際だつように、まず第1、2部で手続き的な実装を紹介します。手続き型と言っても、せっかくSQLを使うので、個々のステップはなるべく宣言的になるようにしています。第3部で宣言的な実装を紹介します。2つの手法を比較することによって、宣言的というのがどういうことなのかが明らかになることを期待しています。
対象読者
- 計算機でパズルを解くことに興味のある方
- 数独を知っている方（数独自体についての説明はしません）
- ストアド・プロシージャについて学びたい（ストアド・プロシージャ自体については説明しませんが、雰囲気は分かると思います）
- データベース管理システムで「データの管理」を超えたことをしてみたい方
SQLにあまり慣れていない方へ
SQLは対話的に実行することができます。そのため、「小さいSQL文で実験し、うまくいったらそれを別のSQL文に組み込む」という方法で、大きいSQL文を組み立てていくことができます。本稿では追加したSQL文を太字で表示することで、はじめに作った小さいSQL文が、形をほとんど変えずに、より大きなSQL文の一部になることが分かるようになっています。
必要な環境
本文のコードをそのまま実行するにはMySQL 5が必要です。コードだけを「mysql1.sql」にまとめてあります（MySQL 5.0.37で動作を確認しました）。ファイルも最後のほうで盤面を設定していますから、そこを書き換えれば、別の問題を解くことができます（すべての数独の問題を解けるわけではありません）。
ストアド・プロシージャをサポートするRDBMSなら、本稿のアイディアを実装できるはずですが、ストアド・プロシージャの書き方はRBDMSによって大きく異なるので、書き直すにはある程度の手間がかかることを覚悟しなければなりません。
数独について
パズルをコンピュータで解く際には、力任せにやろうとしても時間がかかるだけで、人間がアルゴリズムを工夫することが重要だというのが常識です。ただし、このことは数独には必ずしもあてはまりません。数独は、コンピュータで解くパズルとしてはとても簡単なものだからです。本稿で紹介する方法も、筆者が特別にアルゴリズムを工夫したということはありません。
とはいえ、本稿で用いた方法は、「縦・横・ブロックに同じ数が入らないように各マス目に数字を割り当てる」という数独のルールを、そのままプログラミング言語に置き換えたわけではありません（第3部はそれに近いです）。ルールをもとに、筆者は次のような戦略を考えました。
- 各マス目に入る数字の候補を管理する
- 数字の候補が一つしか無いマス目には、その数字を入れる（解法1）
- ある数字Xの入り得る場所が、ある行（あるいは列・ブロック）に一つしかない場合、そこにXを入れる（解法2）
- 解法1、2で数字が決まらない場合は、数字を仮定して作業を進め、矛盾が生じたら仮定を棄却する（第2部で実装）
これらは、数独を自分で解いたことのある人にとっては、自明と言っていい戦略でしょう。つまり、高速化のために、アルゴリズムを工夫しているわけではないのです。
本稿の概要
本稿で紹介する手法の構成要素を簡単に紹介しておきます。
| 名前 | 用途 |
| nums | 整数を入れておく（通常は1から9が入っている） |
| problems | 数独の盤面を格納する |
| candidates | マス目に入り得る数字を管理する |
| 名前 | 用途 |
| initialize | 盤面を入力する |
| display | 盤面を出力する |
| makeNumSeq | テーブル「nums」に1からn（引数）までの整数を格納する |
| makeCandidates | 入り得る数字の候補を求める |
| updateProblem | 候補の中から数字を決定する |
| simpleDeduction | makeCandidatesとupdateProblemを繰り返す |
準備
プロシージャ内の「;」と、現セッションの命令の終端（デリミタ）を区別するために、後者を変更します（「DELIMITER ;」で元に戻ります）。
DELIMITER //
連続データ
次のような、作業に使う整数を入れておくためのテーブル「nums」を作ります。
| n |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
DROP TABLE IF EXISTS nums// CREATE TABLE nums (n INT NOT NULL PRIMARY KEY)//
テーブル「nums」に1からnまでの整数を格納するストアド・プロシージャ:makeNumSeqを実装します。（これは本題とは直接関係ありませんが、ストアド・プロシージャ:の簡単な例なので、慣れていない場合はゆっくり読んでください。）
すでにmakeNumSeqがあるなら、それをまず削除します（これは書き直しの際に必要です）。
DROP PROCEDURE IF EXISTS makeNumSeq//
プロシージャの本体です。ここでやっていることは単純なので、とくに説明の必要はないでしょう。ただし、これは手続き型言語の書き方で、ここにはSQLらしさはありません。このように、ストアド・プロシージャは手続き型で書くこともできるので、いつもSQLらしく書こうとこだわるのではなく、問題に応じて最も簡潔だと思う方法を採りましょう。
CREATE PROCEDURE makeNumSeq(maxNum INT) BEGIN DECLARE i INT DEFAULT 1; DELETE FROM nums; WHILE i<=maxNum DO INSERT INTO nums (n) VALUES (i); SET i=i+1; END WHILE; END;//
ここで「CALL makeNumSeq(5)//」などとすれば、テーブル「nums」の中身は先に示したとおりになります。
