CodeZine(コードジン)

特集ページ一覧

SQLによる数独の高速解法

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

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

数独の解法3(バックトラック)

問題3
問題3

 これが第1部で解けなかった問題です(この問題はTom Davis “The Mathematics of Sudoku”で、難問として紹介されているものです)。

CALL initialize(CONCAT(
'    7 94 ',
' 7  9   5',
'3    5 7 ',
' 874  1  ',
'463 8    ',
'     7 8 ',
'8  7     ',
'7      28',
' 5 268   '))//

CALL simpleDeduction(0)//

CALL display(0)//

0 0 0 0 7 0 9 4 0
0 7 0 0 9 0 0 0 5
3 0 0 0 0 5 0 7 0
0 8 7 4 0 0 1 0 0
4 6 3 0 8 0 0 0 0
0 0 0 0 0 7 0 8 0
8 0 0 7 0 0 0 0 0
7 0 0 0 0 0 0 2 8
0 5 0 2 6 8 0 0 0
-- 0(未定部分)がある、つまり解けていない。

 ここではアルゴリズムを工夫するのではなく、計算パワーに頼ることにしましょう。「数字を仮定して作業を進め、矛盾が生じたら仮定を棄却する(バックトラック)」という戦略を実装します。

 例えば、今の段階では1行1列に入る数字は次のとおりです。

SELECT * FROM candidates WHERE row=1 AND col=1//

+----+-----+-----+-----+
| id | row | col | val |
+----+-----+-----+-----+
|  0 |   1 |   1 |   1 |
|  0 |   1 |   1 |   2 |
|  0 |   1 |   1 |   5 |
|  0 |   1 |   1 |   6 |
+----+-----+-----+-----+

 1行1列の数字を「1」に仮定して、先に進んでみます。それでもし数字を埋められない事態になったら、仮定(つまり1行1列を「1」にしたこと)が間違っていたことになりますから、そこまで戻って、今度は「2」を試します。このような手続きを「バックトラック」と言います。解が複数ある場合にも対応できるように、もし「2」で成功したとしても(実際そうなのですが)、「5」と「6」も試すことにしましょう。

バックトラック

 一般的に、バックトラックは手続きを再帰的に呼び出すことで実現します。しかしながら、MySQLのストアド・プロシージャは再帰呼び出しをサポートしていませんから、別の方法で実現しなければなりません(SQL Serverも再帰の深さに32という上限があります)。そのための補助的な手続きを用意しましょう(「再帰をサポートしていない」というのは、SQLでふつうにパズルを解こうとする際の、最大の欠点だと筆者は思います。しかしながら、数独の場合は第3部の解法があるため、このことは大した問題ではありません)。

盤面のコピー

 識別idtheIdであるような盤面をコピーして、そのr行c列の値をvにするようなファンクション:copyProblemを実装します。

 新たに生成される盤面のidは、それまで使われているidの最大値+1とします。

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;

 全体を次のようなファンクション:copyProblemにまとめておきます。プロシージャではなくファンクションにする理由は後で説明します(ファンクション中でUPDATEを実行できないRDBMSもあるので注意してください)。

copyProblem
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;

  RETURN 1;
END;//

仮定

 値が決まっていない場所を一つ選びましょう。

-- 値の決まらない場所を一つ選択
SELECT row,col FROM problems a WHERE val=0 AND EXISTS (
  SELECT * FROM candidates b
  WHERE b.id=0 AND a.row=b.row AND a.col=b.col)
GROUP BY row,col LIMIT 1//

+-----+-----+
| row | col |
+-----+-----+
|   1 |   1 |
+-----+-----+

 この1行1列に入り得るすべての数字をいったん別のテーブル「tmp」に格納します。

-- 選択した場所に入り得る数字を取得
CREATE TEMPORARY TABLE tmp
  SELECT val FROM candidates WHERE id=0 AND row=1 AND col=1//

 盤面を4つコピーし、それぞれの1行1列に1、2、5、6を入れます。先ほど、copyProblemをプロシージャではなくファンクションにしていたのは、この作業を一つのSELECT文で書くためでした。

-- 数字を仮定して、新しい盤面を作る
SELECT copyProblem(0,1,1,val) FROM tmp//

 実際に盤面がコピーされていることを確認してみましょう。

CALL display(1)//

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

CALL display(2)//

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

CALL display(3)//

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

CALL display(4)//

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

 以上の手続きを一つのプロシージャ:expandにまとめます(copyProblemの戻り値を入れる変数iはダミーです)。

expand
DROP PROCEDURE IF EXISTS expand//

CREATE PROCEDURE expand(theId INT)
BEGIN
  DECLARE ro,co,i INT;

  -- 値の決まらない場所を一つ選択
  SELECT row,col INTO ro,co FROM problems a
    WHERE id=theId AND val=0 AND EXISTS (
    SELECT * FROM candidates b
      WHERE b.id=theId AND a.row=b.row AND a.col=b.col)
  GROUP BY row,col LIMIT 1;

  IF ro IS NOT NULL THEN
    DROP TABLE IF EXISTS tmp;

    -- 選択した場所に入り得る数字を取得
    CREATE TEMPORARY TABLE tmp
      SELECT val FROM candidates WHERE id=theId AND row=ro AND col=co;

    -- 数字を仮定して、新しい盤面を作る
    SELECT SUM(copyProblem(theId,ro,co,val)) INTO i FROM tmp;
  END IF;
END;//

プロシージャ:makeCandidatesの複数盤面対応

 これまで、表示したい盤面のidを指定しなければならないプロシージャ:displayだけは、複数盤面対応ができていました。他のプロシージャも複数盤面対応してなければなりません。次のように修正しましょう。

makeCandidates
DROP PROCEDURE IF EXISTS makeCandidates//

CREATE PROCEDURE makeCandidates(theId INT)
BEGIN
  DELETE from candidates WHERE id=theId;

  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)));
END;//

プロシージャ:updateProblemの複数盤面対応

 updateProblemも複数盤面に対応させます。

updateProblem
DROP PROCEDURE IF EXISTS updateProblem//

CREATE PROCEDURE updateProblem(theId INT)
BEGIN
  UPDATE problems
  JOIN (
    SELECT a.id,a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT row,col FROM candidates WHERE id=theId
        GROUP BY row,col HAVING COUNT(val)=1
    ) tmp ON tmp.row=a.row AND tmp.col=a.col
    WHERE a.id=theId

    UNION
    SELECT a.id,a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT row,val FROM candidates WHERE id=theId
        GROUP BY row,val HAVING COUNT(val)=1
    ) tmp ON tmp.row=a.row AND tmp.val=a.val
    WHERE a.id=theId

    UNION
    SELECT a.id,a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT col,val FROM candidates WHERE id=theId
        GROUP BY col,val HAVING COUNT(val)=1
    ) tmp ON tmp.col=a.col AND tmp.val=a.val
    WHERE a.id=theId

    UNION
    SELECT a.id,a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT val,(row-1) DIV @m AS x,(col-1) DIV @m AS y
      FROM candidates WHERE id=theId
      GROUP BY x,y,val HAVING COUNT(val)=1
    ) tmp ON tmp.x=(a.row-1) DIV @m
      AND tmp.y=(a.col-1) DIV @m AND tmp.val=a.val
    WHERE a.id=theId
  ) tmp2 ON problems.id=tmp2.id AND problems.row=tmp2.row
    AND problems.col=tmp2.col
  SET problems.val=tmp2.val;
END;

  • 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