CodeZine(コードジン)

特集ページ一覧

SQLによる数独の解法

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

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

数独の解法1(単純な場合)

 「数字の候補が一つしか無いマス目には、その数字を入れる」という戦略を実装します。

候補の列挙

 空白部分に入り得る数字を決めていきます。まず、すべての可能性を列挙し、そこからルールに反するものを除外します。

すべての可能性

 すべての可能性は、テーブル「nums」を3つ使って生成することができます(「複数のテーブルを結合して組み合わせを生成する」というテクニックを使っています)。

-- すべての可能性
SELECT 0 AS id,a.n AS row,b.n AS col,c.n AS val
FROM nums a,nums b,nums c//
すべての可能性(9*9*9=729個)
idrowcolval
0111
0112
0113
0114
0115
0116
0117
0118
0119
0121
0122

未定の部分

 上述の「すべての可能性」というのはちょっと考えがなさ過ぎます。考えるべきは盤面の空白部分、つまりテーブル「problems」で値が0のところについてだけです(図の水色部分)。

問題1の空白部分
問題1の空白部分

 空白部分は次のように得られます。

-- 空白部分
SELECT * FROM problems WHERE val=0//

 ですから、先述のSELECT文は、次のように改良できます(条件を結合する条件は「row=a.n AND col=b.n」です)。

-- すべての可能性
SELECT 0 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 val=0
      AND row=a.n AND col=b.n)//

 このように、「小さい文から始めて、条件や副問い合わせを追加しながら目的の文に近づけていく」というのがSQL文を書くコツです。この作業をさらに続けます。

数独のルール

 数独のルールを適用しましょう。例えば、5行3列に入れられない数字は、第5行あるいは第3列、5行3列が属するブロックに登場するものです(水色部分にある数字)。

問題1:数独のルール
問題1:数独のルール

 これらは次のように取得することができます(商を求めるのに「DIV」を使うのはMySQL独自の書き方で、「/」を使うのが一般的です)。

-- 特定のマス目に入らない数字
SELECT * FROM problems
WHERE val!=0
  AND (row=5
    OR col=3
    OR ((row-1) DIV 3=(5-1) DIV 3
      AND (col-1) DIV 3=(3-1) DIV 3))//

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

 一般化して言えば、a.n行b.n列にc.nが入り得るためには、テーブル「problems」の(1) a.n行、(2) b.n列、(3) a.n行b.n列が属するブロックに、数字c.nがあってはいけません。先ほどのSELECT文にこの条件を加えると、次のようになります(結合条件を入れて書き換えています)。

SELECT 0 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 val=0
      AND row=a.n AND col=b.n)
  AND NOT EXISTS (
    -- 特定のマス目に入らない数字
    SELECT * FROM problems
    WHERE val=c.n
      AND (row=a.n
        OR col=b.nv
        OR ((row-1) DIV 3=(a.n-1) DIV 3
          AND (col-1) DIV 3=(b.n-1) DIV 3)))//

プロシージャ:makeCandidates

 指定したidの盤面だけに対して、これまで紹介した操作を行うプロシージャ:makeCandidatesは次のようになります(引数のtheIdで盤面idを与えます)。

makeCandidates
DROP PROCEDURE IF EXISTS makeCandidates//

CREATE PROCEDURE makeCandidates(theId INT)
BEGIN
  DELETE FROM candidates;
  INSERT INTO candidates -- 結果をテーブルに挿入
    SELECT 0 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 val=0
          AND row=a.n AND col=b.n)
      AND NOT EXISTS (
        SELECT * FROM problems
        WHERE 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;//

 プロシージャを実行します。

CALL makeCandidates(0)//

数字の当てはめ

 7行8列に注目してください。

問題1:数字の当てはめ
問題1:数字の当てはめ

 ここに入る数字は「8」しかないことは、数独のルールからすぐに分かります。実際に、テーブル「candidates」でもそうなっています。

SELECT val FROM candidates WHERE row=7 AND col=8//

+-----+
| val |
+-----+
|   8 |
+-----+

 ですから、この場所は「8」に決まりです。

 このように、入り得る数字が一つしかない場所は、その数字に決まりです。この作業のためにまず、入り得る数字の候補が一つしかない場所を取り出します(今の場合1カ所しかありません)。

SELECT row,col FROM candidates GROUP BY row,col HAVING COUNT(val)=1//

+-----+-----+
| row | col |
+-----+-----+
|   7 |   8 |
+-----+-----+

 その場所に入る数字を知るために、テーブル「candidates」と結合させます。

SELECT a.row,a.col,a.val FROM candidates a
JOIN (
``  SELECT row,col FROM candidates 
      GROUP BY row,col HAVING COUNT(val)=1``
) tmp ON tmp.row=a.row AND tmp.col=a.col//

+-----+-----+-----+
| row | col | val |
+-----+-----+-----+
|   7 |   8 |   8 |
+-----+-----+-----+

 実はこの操作は、MySQLに限っては次のように書くこともできますが、SQL Serverではエラーになるので、ここでは使いません。

SELECT row,col,val FROM candidates
  GROUP BY row,col HAVING COUNT(val)=1//

 候補が一つしかない場所に、その数字を当てはめるようなストアド・プロシージャ:updateProblemにまとめておきましょう。

DROP PROCEDURE IF EXISTS updateProblem//

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

解法1のまとめ

 今挑戦している問題は、makeCandidatesupdateProblemを繰り返せば解けます。この操作をストアド・プロシージャ:simpleDeductionにまとめておきましょう。空白部分(値が0のところ)の数が変わらなくなるまで繰り返します。

simpleDeduction
DROP PROCEDURE IF EXISTS simpleDeduction//

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

  REPEAT -- 繰り返し。終了条件はUNTILに
    SET oldResult=newResult;
    -- 候補を求める。
    CALL makeCandidates(0);
    -- 数字を当てはめる。
    CALL updateProblem(0);
    -- 空白部分を数える。
    SELECT COUNT(*) INTO newResult FROM problems WHERE val=0;
  UNTIL (newResult=0 || oldResult=newResult) END REPEAT;
END;//

 実際に解けることを確認します。

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

CALL simpleDeduction(0)//

CALL display(0)//

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

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

修正履歴

  • 2007/09/21 17:06 第2部・第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