ストアド・プロシージャを用いる実装
ストアド・プロシージャで実装しましょう。データベースに盤面を問い合わせ、その結果を使ってSQLを生成するというのはJDBCの場合と同じです。ストアド・プロシージャを使えば、すべてをデータベースの中で済ませることができます。
コードはmysql-meta.sql（MySQL版）とsqlserver-meta.sql（SQL Server版）にまとめてあります。
先にも述べたように、この実装はPinskiさんのCALCULATE_GS_V3との比較のためのものです。分かりやすさという点ではJDBC版をお勧めします。
基本的なデータ構造・問題の入出力
リレーショナル・データベースで数独の問題を管理する方法は第1部の補足で紹介しているので、そちらを参照してください。次のように、テーブル「nums」に1から9までの整数が、テーブル「problems」に数独の問題が格納されているとして話を進めます（idは複数の盤面を区別するためのものですが、本稿では使いません）。
| n |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| 7 |
| 8 |
| 9 |
| id | row | col | val |
| 0 | 1 | 1 | 1 |
| 0 | 1 | 2 | 0 |
| 0 | 1 | 3 | 0 |
| … | … | … | … |
| 0 | 2 | 1 | 0 |
| 0 | 2 | 2 | 3 |
| 0 | 2 | 3 | 0 |
| … | … | … | … |
プロシージャ:eval
まず、文字列として与えられたSQL文を実行するプロシージャ:evalを作成します（SQL Serverなら、「EXEC(SQL文字列)」で実行できるので、このようなプロシージャは不要です）。
DROP PROCEDURE IF EXISTS eval// CREATE PROCEDURE eval(t text) BEGIN SET @stmt=t; PREPARE stmt FROM @stmt; EXECUTE stmt; DEALLOCATE PREPARE stmt; END//
SELECT節
すべてのマス目を取得して、数字が入っているなら「1 AS R1C1,」、入っていないなら「tR1C2 AS R1C2,」のような文字列を生成します。JDBC版では要素を一度コレクションに格納しましたが、ここではSELECT節を直接生成しています。
一般に、カーソルは遅いので使わない方がいいと言われますが、ここでの処理のように、データ全体にわたって行う処理で、一度やればそれで終わりの場合には、使用を躊躇する必要はありません。
DROP FUNCTION IF EXISTS makeSelect// CREATE FUNCTION makeSelect(theId INT) RETURNS TEXT READS SQL DATA BEGIN DECLARE done INT DEFAULT 0; DECLARE stmt TEXT; DECLARE r,c,v INT; DECLARE label VARCHAR(10); DECLARE cur CURSOR FOR SELECT row,col,val FROM problems WHERE id=theId; DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done = 1; SET stmt='SELECT '; OPEN cur; REPEAT FETCH cur INTO r,c,v; IF NOT done THEN SET label=CONCAT('R',r,'C',c); SET stmt=CONCAT(stmt,IF(v!=0,v,CONCAT('t',label,'.n')), ' AS ',label,','); END IF; UNTIL done END REPEAT; CLOSE cur; -- 最後の余計なカンマを削除 RETURN SUBSTRING(stmt,1,LENGTH(stmt)-1); END//
FROM節
数字が入っていないマス目すべてに対し、「nums tR1C2」のような文字列を生成します。ここでもカーソルを使います。
DROP FUNCTION IF EXISTS makeFrom// CREATE FUNCTION makeFrom(theId INT) RETURNS TEXT READS SQL DATA BEGIN DECLARE done INT DEFAULT 0; DECLARE stmt TEXT; DECLARE r,c INT; DECLARE cur CURSOR FOR SELECT row,col FROM problems WHERE id=theId AND val=0 ORDER BY row,col; DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done = 1; SET stmt=' FROM '; OPEN cur; REPEAT FETCH cur INTO r,c; IF NOT done THEN SET stmt=CONCAT(stmt,'nums tR',r,'C',c,','); END IF; UNTIL done END REPEAT; CLOSE cur; -- 最後の余計なカンマを削除 RETURN SUBSTRING(stmt,1,LENGTH(stmt)-1); END//
WHERE節
JDBC版と同様、条件句を格納するためのテーブルを作成します。
DROP TABLE IF EXISTS whereItems// CREATE TABLE whereItems (item VARCHAR(20))//
2つのテーブル「problems」の直積によって、マス目同士のすべての組み合わせを生成し、そこから「!=」で結ぶべきものだけを選びます。選ぶのは、（1）同じ行にあるもの、（2）同じ列にあるもの、（3）同じブロックにあるものです（ブロックの判定には商を求める「DIV」を使っていますが、これはMySQLの記法で、「/」を使うのが一般的です。JDBCはデータベース管理システムの違いを完全に隠蔽できるわけではありません）。
DROP FUNCTION IF EXISTS makeWhere// CREATE FUNCTION makeWhere(theId INT) RETURNS TEXT READS SQL DATA BEGIN DECLARE done INT DEFAULT 0; DECLARE stmt TEXT; DECLARE aRow,aCol,aVal,bRow,bCol,bVal INT; DECLARE item1,item2,itemTmp CHAR(20); DECLARE cur CURSOR FOR SELECT a.row,a.col,a.val,b.row,b.col,b.val FROM problems a,problems b WHERE a.id=theId AND b.id=theId AND (a.val=0 OR b.val=0) -- どちらかが未定の場合に -- 条件句を作る AND (a.row=b.row AND a.col!=b.col -- 条件句を作るのは、行が同じ OR a.row!=b.row AND a.col=b.col -- あるいは列が同じ OR ((a.row!=b.row OR a.col!=b.col) -- あるいはブロックが同じもの AND (a.row-1) DIV @m=(b.row-1) DIV @m AND (a.col-1) DIV @m=(b.col-1) DIV @m)); DECLARE cur2 CURSOR FOR SELECT DISTINCT item FROM whereItems ORDER BY item; DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done = 1; DELETE FROM whereItems; OPEN cur; REPEAT FETCH cur INTO aRow,aCol,aVal,bRow,bCol,bVal; IF NOT done THEN SET item1=IF(aVal!=0,aVal,CONCAT('tR',aRow,'C',aCol,'.n')); SET item2=IF(bVal!=0,bVal,CONCAT('tR',bRow,'C',bCol,'.n')); IF STRCMP(item1,item2)<0 THEN -- ペアを辞書順で並び替える。 INSERT INTO whereItems VALUES (CONCAT(item1,'!=',item2)); ELSE INSERT INTO whereItems VALUES (CONCAT(item2,'!=',item1)); END IF; END IF; UNTIL done END REPEAT; CLOSE cur; SET stmt=' WHERE '; -- 上で作成した条件をつなぎ合わせてWHERE節を作る。 SET done=0; OPEN cur2; REPEAT FETCH cur2 INTO itemTmp; IF NOT done THEN SET stmt=CONCAT(stmt,itemTmp,' AND '); END IF; UNTIL done END REPEAT; CLOSE cur2; -- 最後の余計な「 AND 」を削除 RETURN SUBSTRING(stmt,1,LENGTH(stmt)-5); END//
SELECT文全体
ファンクション:makeSelect、makeFrom、makeWhereの結果を結合して一つのSELECT文を作ります。
DROP FUNCTION IF EXISTS makeSql// CREATE FUNCTION makeSql(theId INT) RETURNS TEXT READS SQL DATA BEGIN RETURN CONCAT(makeSelect(theId),makeFrom(theId),makeWhere(theId)); END//
SELECT文の実行
SELECT文の前に「CREATE TABLE tmp 」を付けて、結果をテーブル「tmp」に格納します。
CALL initialize(CONCAT( '1 7 9 ', ' 3 2 8', ' 96 5 ', ' 53 9 ', ' 1 8 2', '6 4 ', '3 1 ', ' 4 7', ' 7 3 '))// RESET QUERY CACHE// DROP TABLE IF EXISTS tmp// CALL eval(CONCAT('CREATE TABLE tmp ',makeSql(0)))//
Query OK, 0 rows affected (0.42 sec)
0.4秒程度で解けました。
SELECT * FROM tmp\G *************************** 1. row *************************** R1C1: 1 R2C1: 5 R3C1: 7 . . . R7C9: 9 R8C9: 7 R9C9: 4 1 row in set (0.00 sec)
「\G」を付けているので縦に表示されますが、解が一つなら結果は1行です。「SELECT R1C1 FROM tmp」などとすれば1行1列に入る数字が分かります。
結果の整形
結果を見やすい形に整形しましょう。まず、解が複数ある場合にも対応できるように、テーブル「tmp」にidというカラムを追加します。
ALTER TABLE tmp ADD id INT AUTO_INCREMENT PRIMARY KEY//
テーブル「tmp」を1行ずつ処理します。ここでは、解の数字をテーブル「problems」に埋め込んで、表示用のプロシージャ:displayを呼び出しています。
DROP PROCEDURE IF EXISTS extractResult// CREATE PROCEDURE extractResult(theId INT) BEGIN DECLARE i,r,c INT; SET i=0; REPEAT -- テーブル:tmpを1行ずつ処理する。 SELECT MIN(id) INTO i FROM tmp WHERE id>i; IF i IS NOT NULL THEN SET r=1; WHILE r<=@maxNum DO SET c=1; WHILE c<=@maxNum DO CALL eval(CONCAT( -- 解をテーブル:problemsに埋め込む。 'UPDATE problems SET val=(SELECT R',r,'C',c, ' FROM tmp WHERE id=',i,') ', 'WHERE id=',theId,' AND row=',r,' AND col=',c)); SET c=c+1; END WHILE; SET r=r+1; END WHILE; CALL display(theId); -- 盤面表示用のプロシージャを呼び出す。 END IF; UNTIL i IS NULL END REPEAT; END// CALL extractResult(0)//
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
一連の操作を「mysql-meta.sql」にまとめてあります。MySQLに接続し、「SOURCE mysql-meta.sqlのフルパス」によって実行することができます（SQL Server版は「sqlserver-meta.sql」です）。
おわりに
SQLを使って数独を高速に解く方法を紹介しました。ここで紹介した方法は、数独の解をたった1つのSELECT文で記述するというものでした。SELECTはかなり大きなものになるため、手では書かずに、JDBCやストアド・プロシージャを用いて動的に生成しました。
SQLが優れている理由の一つに、それが宣言型言語であることが挙げられます。「何が欲しいか」を書けば、具体的な実現方法はコンピュータが考えます。それに対してC言語やJavaのような手続き型の言語では、具体的な実現方法も人間が書かなければなりません。
コンピュータが考える実現方法の効率が気になるかもしれませんが、第2部で紹介した手続き的なコードでは30秒ほど、Pinskiさんのコードでは200秒ほどかかる問題を、本手法では約1秒で解くことができました（筆者の作業環境で測定しました）。
宣言的に書きたくてもそれが難しい場合があります。例えば、本稿で実行したSELECT文は15KBほどあり、直接手で書くのは困難です。そのような時、問題を細かい部分に分けて手続き的な記述で解こうとする前に、宣言的な記述自体をプログラムで生成すること（メタ・プログラミング）を検討してみてください。うまくいけば、劇的なパフォーマンスを得られるでしょう。
参考資料
- 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」と同等なので、難しい問題は解けません。
