CodeZine(コードジン)

特集ページ一覧

SQLによる数独の高速解法

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

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

盤面のチェック

 数字を仮定するため、途中でルールに反する状態になる可能性があります。その状態を検出できるようにしましょう。実験のために、1行1列に「7」が入ってしまったとしましょう。これはルールに反しています。

問題3:ルール違反の盤面
問題3:ルール違反の盤面
CALL initialize(CONCAT(
'    7 94 ',
' 7  9   5',
'3    5 7 ',
' 874  1  ',
'463 8    ',
'     7 8 ',
'8  7     ',
'7      28',
' 5 268   '))//

SELECT copyProblem(0,1,1,7)//

CALL display(1)//

7 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

 1行目にルール違反があることは、次のように確認できます。

SELECT row,val FROM problems
WHERE id=1 AND val!=0 GROUP BY row,val HAVING COUNT(val)>1//

+-----+-----+
| row | val |
+-----+-----+
|   1 |   7 |
+-----+-----+

 列についても同様です。

SELECT col,val FROM problems
WHERE id=1 AND val!=0 GROUP BY col,val HAVING COUNT(val)>1//

+-----+-----+
| col | val |
+-----+-----+
|   1 |   7 |
+-----+-----+

 同様に、左上のブロックにルール違反があることは、次のように確認できます。

SELECT (row-1) DIV 3 AS x,(col-1) DIV 3 as y,val FROM problems
WHERE id=1 AND val!=0 GROUP BY x,y,val HAVING COUNT(val)>1//

+------+------+-----+
| x    | y    | val |
+------+------+-----+
|    0 |    0 |   7 |
+------+------+-----+

 これらのチェックをファンクション:isValidにまとめておきます。この関数は、盤面がルールに違反していなければ空白の数を、違反していれば-1を返します。

isValid
DROP FUNCTION IF EXISTS isValid//

CREATE FUNCTION isValid(theId INT) RETURNS INT READS SQL DATA
BEGIN
  DECLARE i,j,k INT;

  -- 行に関するルール違反を調べる
  SELECT row,val INTO i,j FROM problems
  WHERE id=theId AND val!=0 GROUP BY row,val HAVING COUNT(val)>1 LIMIT 1;

  IF i IS NOT NULL THEN
    RETURN -1;
  END IF;

  -- 列に関するルール違反を調べる
  SELECT col,val INTO i,j FROM problems
  WHERE id=theId AND val!=0 GROUP BY col,val HAVING COUNT(val)>1 LIMIT 1;

  IF i IS NOT NULL THEN
    RETURN -1;
  END IF;

  -- ブロックに関するルール違反を調べる
  SELECT (row-1) DIV @m AS x,(col-1) DIV @m AS y,val
    INTO i,j,k FROM problems
  WHERE id=theId AND val!=0 GROUP BY x,y,val HAVING COUNT(val)>1 LIMIT 1;

  IF i IS NOT NULL THEN
    RETURN -1;
  END IF;

  -- 空白の数を返す
  SELECT COUNT(*) INTO i FROM problems WHERE id=theId AND val=0;
  RETURN i;
END;//

 盤面id=0は大丈夫ですが、盤面id=1はルールに違反していることが確認できます。

SELECT isValid(0)//

+------------+
| isValid(0) |
+------------+
|         53 |
+------------+

SELECT isValid(1)//

+------------+
| isValid(1) |
+------------+
|         -1 |
+------------+

ファンクション:simpleDeductionの修正

 ファンクション:simpleDeductionはほとんど変わりません。複数盤面に対応させ、isValidが0を返した時を終了条件に加えます(盤面を消去します)。

simpleDeduction
DROP PROCEDURE IF EXISTS simpleDeduction//

CREATE PROCEDURE simpleDeduction(theId INT)
BEGIN
  DECLARE oldResult,newResult INT DEFAULT 0;

  SET newResult=1;
  WHILE 0<newResult AND oldResult!=newResult DO
    SET oldResult=newResult;
    CALL makeCandidates(theId); -- 候補を求める
    CALL updateProblem(theId); -- 数字を当てはめる

    SELECT isValid(theId) INTO newResult; -- ルール違反を調べる
    IF newResult<0 THEN
      -- ルール違反をしていたら盤面を消去
      DELETE FROM problems WHERE id=theId;
    END IF;
  END WHILE;
END;//

主要プロシージャ:solve

 バックトラックを使って数独を解く手続きを、プロシージャ:solveにまとめます。この手続きは次のように進みます。

  1. まだ解いていない盤面を、simpleDeductionで解く
  2. すべて数字が決まったなら結果を表示する
  3. 空白が残っているなら、そこに仮に数字を入れた盤面を作り、1.に戻る
solve
DROP PROCEDURE IF EXISTS solve//

CREATE PROCEDURE solve()
BEGIN
  DECLARE theId,result INT DEFAULT 0;

  DELETE FROM problems WHERE id>0;
  DELETE FROM candidates;

  REPEAT
    -- まだ解いていない盤面を、simpleDeductionで解く
    CALL simpleDeduction(theId);
    
    -- すべて数字が決まったなら結果を表示する
    SELECT COUNT(*) INTO result FROM problems WHERE id=theId AND val!=0;
    IF result=@maxNum*@maxNum THEN
      CALL display(theId);
    ELSE
      -- 空白が残っている(盤面は残っているからルール違反は無い)
      IF result!=0 THEN
        CALL expand(theId); -- 仮に数字を入れた盤面を作る
      END IF;
      DELETE FROM problems WHERE id=theId;
    END IF;

    DELETE FROM candidates WHERE id=theId;
    SET theId=theId+1;
    SELECT MAX(id) INTO result FROM problems;
  UNTIL result<theId OR result IS NULL END REPEAT;
END;//
CALL initialize(CONCAT(
'    7 94 ',
' 7  9   5',
'3    5 7 ',
' 874  1  ',
'463 8    ',
'     7 8 ',
'8  7     ',
'7      28',
' 5 268   '))//

CALL solve()//

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

1 row in set (7.88 sec)

Query OK, 0 rows affected, 665 warnings (24.64 sec)
-- 0(未定部分)がない、つまり解けた。

  • 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