CodeZine(コードジン)

特集ページ一覧

SQLによる数独の高速解法

続「SQLによる数独の解法」 数独の難問を解く

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

高速化

 バックトラックを実装したので、すべての数独の問題を解くことができるようになりました。しかしながら、実装をかなり単純なものにしていたため、かなりの無駄があるのも事実です。本稿の最後でAlEscargotを解きますが、この段階の実装では1分ほどかかってしまいます(それでもCALCULATE_GS_V3よりは速いのですが)。そこで、アルゴリズムを少し改良しましょう(「はじめに」で述べたように、本稿ではアルゴリズムを工夫することにはあまりこだわりません)。

プロシージャ:makeCandidatesの改良

 空白だったところに数字が入ると、他の空白部分に入る数字の候補(つまりテーブル「candidates」の内容)も変わります。これまでは、テーブル「candidates」を更新する際、すべてを削除してから新たにデータを挿入していました。これは明らかに無駄です。ルールに反する数字を削除するだけで十分です(追加した部分を太字で示しています)。

makeCandidates-2
DROP PROCEDURE IF EXISTS makeCandidates//

CREATE PROCEDURE makeCandidates(theId INT)
BEGIN
  DECLARE f INT;

  -- 既に候補が求められているかどうかをチェック
  SELECT COUNT(*) INTO f FROM candidates WHERE id=theId;

  IF f=0 THEN -- 求められていない場合は前と同じ
    INSERT INTO candidates
      SELECT theId AS id,a.n AS row,b.n AS col,c.n AS val
      FROM nums a,nums b,nums c
      WHERE EXISTS (
        SELECT * FROM problems
        WHERE id=theId AND val=0 AND row=a.n AND col=b.n)
        AND NOT EXISTS (
          SELECT * FROM problems
          WHERE id=theId AND val=c.n
            AND (row=a.n
              OR col=b.n
              OR ((row-1) DIV @m=(a.n-1) DIV @m
              AND (col-1) DIV @m=(b.n-1) DIV @m)));
  ELSE -- 求められているなら、新たに無効になった候補を削除
    DELETE FROM candidates
    WHERE id=theId AND
    EXISTS (
      SELECT * FROM problems b
      WHERE id=theId
        AND ((b.val!=0 AND b.row=candidates.row
          AND b.col=candidates.col)
          OR (b.val=candidates.val
            AND (b.row=candidates.row
              OR b.col=candidates.col
              OR ((b.row-1) DIV @m=(candidates.row-1) DIV @m
                AND (b.col-1) DIV @m=(candidates.col-1) DIV @m)))));
  END IF;
END;//

ファンクション:copyProblemの改良

 ある盤面で数字を決定できるマス目がなくなったら、その盤面をコピーして、空白に入る数字を仮定して先に進みます。盤面をコピーしても、新しい盤面の空白に入る数字の候補は一から新たに求めていました。これは無駄です。古い盤面についての数字の候補は、新しい盤面でも大体使えるはずです。そこで、盤面をコピーする際に、候補の数字もコピーするようにしましょう。

copyProblem-2
DROP FUNCTION IF EXISTS copyProblem//

CREATE FUNCTION copyProblem(theId INT,r INT,c INT,v INT)
  RETURNS INT MODIFIES SQL DATA
BEGIN
  DECLARE newId INT;
  SELECT MAX(id)+1 INTO newId FROM problems;

  INSERT INTO problems
    SELECT newId AS id,row,col,val FROM problems WHERE id=theId;
  UPDATE problems SET val=v WHERE id=newId AND row=r AND col=c;

  INSERT INTO candidates
    SELECT newId AS id,row,col,val FROM candidates WHERE id=theId;

  RETURN 1;
END;//

AlEscargot

AlEscargot
AlEscargot

 いよいよAlEscargotに挑戦しましょう。「はじめに」で紹介したように、これはかなりの難問で、『高パフォーマンスなストアドプロシージャの設計』の著者Pinskiさんは、この問題を(筆者の環境で)約200秒かけて解くコードを「まずまず高速」だと評されています。

CALL initialize(CONCAT(
'1    7 9 ',
' 3  2   8',
'  96  5  ',
'  53  9  ',
' 1  8   2',
'6    4   ',
'3      1 ',
' 4      7',
'  7   3  '))//

CALL solve()//
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

1 row in set (33.77 sec)

Query OK, 0 rows affected, 1302 warnings (39.02 sec)

 このように、本稿で紹介したコードは、AlEscargotを40秒程度で解くことができます。

 PinskiさんのコードはSQL Server用のものなので、正しく比較するために、本稿で紹介したコードをSQL Server用に書き直して実験したところ(「sqlserver.sql」にまとめてあります)、AlEscargotを約25秒で解くことができました。

おわりに

 SQLを用いて数独を解く方法を紹介しました。

 「宣言的に書く。つまり何が欲しいのかを書くのであって、どのように得るかを書くのではない」というのがSQLの基本です。ここで紹介した方法は、個々のステップは宣言的でfor文のような繰り返しの制御文はほとんどありませんが、全体としては手続き的、つまりプログラマが数独の解法を細かく指示する形になっています。

 CALCULATE_GS_V3と比べれば、コードのサイズが約1/3、速度が約6倍になったわけですが、それでも「たかが数独のためにずいぶん大がかりな作業が必要だな」とか「速くなったと言っても30秒もかかるのか」という感想を持つ方もおられるでしょう。第3部ではこれらの不満を解消するために、全体の宣言的な記述を試みます。本稿と比較することによって、宣言的に書くということがどういうことなのかが明らかになるでしょう。

参考資料

  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 17:08 第3部へのリンクを追加

バックナンバー

連載: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