SQLによる数独の解法

SQLの宣言的な記述を積み重ねて、数独の簡単な問題を解く

おわりに

　リレーショナル・データベース管理システム上でSQLを使って数独を解く方法を紹介しました。SQLの基本は次の2点です。

1. 宣言的に書く。つまり何が欲しいのかを書くのであって、どのように得るかを書くのではない
2. 小さいSQL文で実験し、それを連結して大きいSQL文を作る

　第1の点は、多くのデータを扱う問題にも拘わらず、for文のような繰り返しの制御文がほとんどないことから納得していただけるかと思います（納得できない方はぜひ第3部を読んでください）。第2の点は、本文中のコードの作り方で納得していただけるかと思います。どのようにして、小さいSQL文が形を変えずに大きいSQL文に組み込まれていくかを、太字で説明しました。

　以上2点を意識して、これまでC言語やJavaのような汎用プログラミング言語で行っていた処理を、SQLのような宣言的に書ける言語で行ってみてもらいたいと思います。

　第2部では本稿で解けなかった数独の問題に挑戦します。第3部では「宣言的に書く」ことを徹底し、よりSQLらしい書き方を紹介します。併せてお読みください。

補足：入出力方法の実装

盤面の入力

　入力は次のような形で行います（これは9×9までの数独にしか使えない簡便法です）。

CALL initialize(CONCAT(
' 45      ',
'2    97  ',
'3    8 6 ',
'      97 ',
'    3    ',
' 62      ',
' 9 3    4',
'  14    2',
'      51 '))//

　入力した際に、盤面のサイズとその平方根（ふつうの数独では9と3）をグローバル変数に格納しておきます。盤面のサイズは入力文字列長の平方根ですから、次のように求められます。

SET @maxNum=SQRT(CHAR_LENGTH(board));
SET @m=SQRT(@maxNum);

　サイズが決まったら、「CALL makeNumSeq(@maxNum);」として、「準備」で作成したテーブル「nums」に、1からそのサイズまでの整数を格納しておきます（ここでは汎用性のためにこうしていますが、ふつうの数独だけに限定するなら、@maxNumや@mはあらかじめ設定しておいてもいいでしょう。その方がコードは簡潔になります）。

　入力された盤面(board)のx行y列の値は、boardの「9*(x-1)+y」文字目に書かれています（一般の場合は「9」ではなく@maxNum）。テーブル「nums」を2つ結合するSELECT文を書けば、すべての値を取り出せます。空白部分は「0」になります。

SELECT a.n,b.n,SUBSTRING(board,9*(a.n-1)+b.n,1)+0
  FROM nums a,nums b;

　入力された文字列から値を読み取ってテーブル「problems」に格納するプロシージャ:initializeは次のようになります。

initialize

DROP PROCEDURE IF EXISTS initialize//

CREATE PROCEDURE initialize(board TEXT)
BEGIN
  DELETE FROM problems;
  DELETE FROM candidates;
  SET @maxNum=SQRT(CHAR_LENGTH(board));
  SET @m=SQRT(@maxNum);
  CALL makeNumSeq(@maxNum);

  INSERT INTO problems (row,col,val)
    SELECT a.n,b.n,SUBSTRING(board,@maxNum*(a.n-1)+b.n,1)+0
      FROM nums a,nums b;
END;//

盤面の出力

　ストアド・プロシージャ:displayは、「CALL display(0)//」のように盤面idを指定して呼び出すと、テーブル「problems」からデータを取得・整形して表示します。

0 4 5 0 0 0 0 0 0
2 0 0 0 0 9 7 0 0
3 0 0 0 0 8 0 6 0
0 0 0 0 0 0 9 7 0
0 0 0 0 3 0 0 0 0
0 6 2 0 0 0 0 0 0
0 9 0 3 0 0 0 0 4
0 0 1 4 0 0 0 0 2
0 0 0 0 0 0 5 1 0

　コードは次のようになります。

display

DROP PROCEDURE IF EXISTS display//

CREATE PROCEDURE display(theId INT)
BEGIN
  DECLARE r,c,v INT;
  DECLARE result TEXT;

  SET result='\n';
  SET r=1;
  WHILE r<=@maxNum DO
    SET c=1;
    WHILE c<=@maxNum DO
      -- r行c列の値を取得し、vに代入
      SELECT val INTO v FROM problems
        WHERE id=theId AND row=r AND col=c;
      SET result=CONCAT(result,v,' ');
      SET c=c+1;
    END WHILE;
    SET result=CONCAT(result,'\n');
    SET r=r+1;
  END WHILE;
  SELECT result;
END;//

参考資料

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」と同等なので、難しい問題は解けません。