CodeZine(コードジン)

特集ページ一覧

動的SQLによる数独の超高速解法

宣言的に書けるというSQLの性質を最大限に活用し、数独を1行のSELECT文で解く

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2007/09/18 14:00

ダウンロード mysql-meta.sql (2.0 KB)
ダウンロード sqlserver-meta.sql (2.3 KB)
ダウンロード Suudoku.java (1.7 KB)

目次

ストアド・プロシージャを用いる実装

 ストアド・プロシージャで実装しましょう。データベースに盤面を問い合わせ、その結果を使ってSQLを生成するというのはJDBCの場合と同じです。ストアド・プロシージャを使えば、すべてをデータベースの中で済ませることができます。

 コードはmysql-meta.sql(MySQL版)sqlserver-meta.sql(SQL Server版)にまとめてあります。

 先にも述べたように、この実装はPinskiさんのCALCULATE_GS_V3との比較のためのものです。分かりやすさという点ではJDBC版をお勧めします。

基本的なデータ構造・問題の入出力

 リレーショナル・データベースで数独の問題を管理する方法は第1部の補足で紹介しているので、そちらを参照してください。次のように、テーブル「nums」に1から9までの整数が、テーブル「problems」に数独の問題が格納されているとして話を進めます(idは複数の盤面を区別するためのものですが、本稿では使いません)。

nums
n
1
2
3
4
5
6
7
8
9
problems
idrowcolval
0111
0120
0130
0210
0223
0230

プロシージャ:eval

 まず、文字列として与えられたSQL文を実行するプロシージャ:evalを作成します(SQL Serverなら、「EXEC(SQL文字列)」で実行できるので、このようなプロシージャは不要です)。

eval
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節を直接生成しています。

 一般に、カーソルは遅いので使わない方がいいと言われますが、ここでの処理のように、データ全体にわたって行う処理で、一度やればそれで終わりの場合には、使用を躊躇する必要はありません。

makeSelect
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」のような文字列を生成します。ここでもカーソルを使います。

makeFrom
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版と同様、条件句を格納するためのテーブルを作成します。

whereItems
DROP TABLE IF EXISTS whereItems//

CREATE TABLE whereItems (item VARCHAR(20))//

 2つのテーブル「problems」の直積によって、マス目同士のすべての組み合わせを生成し、そこから「!=」で結ぶべきものだけを選びます。選ぶのは、(1)同じ行にあるもの、(2)同じ列にあるもの、(3)同じブロックにあるものです(ブロックの判定には商を求める「DIV」を使っていますが、これはMySQLの記法で、「/」を使うのが一般的です。JDBCはデータベース管理システムの違いを完全に隠蔽できるわけではありません)。

makeWhere
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文全体

 ファンクション:makeSelectmakeFrommakeWhereの結果を結合して一つのSELECT文を作ります。

makeSql
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」に格納します。

AlEscargot
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を呼び出しています。

extractResult
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ほどあり、直接手で書くのは困難です。そのような時、問題を細かい部分に分けて手続き的な記述で解こうとする前に、宣言的な記述自体をプログラムで生成すること(メタ・プログラミング)を検討してみてください。うまくいけば、劇的なパフォーマンスを得られるでしょう。

参考資料

  1. MySQLがストアド・プロシージャをサポートしたのは最近(バージョン5以降)のことなので、資料はあまり多くありません。まずはウェブ上のリファレンス・マニュアルを参照してください。
  2. SQLによるプログラミングの基本については、拙著『初級プログラマのためのWebアプリケーション構築入門 - 実践で学ぶJava,XHTML,SQL』(森北出版、2007年)を参照してください。
  3. 単なるデータの保管場所としてではないリレーショナル・データベースの使い方については、Antbony Molinaro著, 木下哲也ほか訳『SQLクックブック』(オライリージャパン 2007)が参考になります。
  4. ジョー・セルコ著, 秋田昌幸訳『プログラマのためのSQL』(ピアソン・エデュケーション 2001)は、SQLについての発展的な話題を数多く扱っています。同著者のJoe Celko's SQL Puzzles and Answers (Morgan Kaufmann, 2nd edition, 2007)で紹介されている数独の解法は、第1部の「解法1」と同等なので、難しい問題は解けません。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2007/09/21 14:33 「JDBCを用いる実装」のWHERE節生成部を修正(ellerさんのご指摘に従って)

バックナンバー

連載:SQLで解く数独

著者プロフィール

  • WINGSプロジェクト 矢吹 太朗(ヤブキ タロウ)

    <WINGSプロジェクトについて> 有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂...

  • 山田 祥寛(ヤマダ ヨシヒロ)

    静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for ASP/ASP.NET。執筆コミュニティ「WINGSプロジェクト」代表。 主な著書に「入門シリーズ(サーバサイドAjax/XM...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5