CodeZine(コードジン)

特集ページ一覧

SQLによる数独の解法

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

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

数独の解法2

問題2
問題2

 「解法1」でどんな問題でも解けるかと言うと、そういうわけにはいきません(この問題は荻原上さんのサイト:ナンバープレース滝野川から許可を得て掲載しています)。

CALL initialize(CONCAT(
'   3     ',
'  146    ',
' 9    8  ',
'25       ',
' 8     4 ',
'       63',
'  4    7 ',
'    182  ',
'     2   '))//

CALL simpleDeduction(0)//

CALL display(0)//

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

 この問題を解くために、「ある数字Xの入り得る場所が、ある行(あるいは列・ブロック)に一つしかない場合、そこにXを入れる」という戦略を実装しましょう。

 2行目に注目してください。

問題2:簡単な推論
問題2:簡単な推論

 2行目に入り得る数字を調べます。

SELECT * FROM candidates WHERE row=2//

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

 2行目で「8」が入り得る場所は1列目しかありません。ですから、2行1列は「8」に決まります。

 次のようにして、各行ごとに、入り得る場所が一つしかないような数字を調べられます。

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

+-----+-----+
| row | val |
+-----+-----+
|   2 |   8 |
|   7 |   2 |
|   8 |   4 |
+-----+-----+

 場所を決定するために、テーブル「candidates」と結合させます。

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

+-----+-----+-----+
| row | col | val |
+-----+-----+-----+
|   2 |   1 |   8 |
|   7 |   2 |   2 |
|   8 |   9 |   4 |
+-----+-----+-----+

 列ごとの調査も同様です(この問題では該当するものがありません)。

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

 ブロックについても同様ですが、GROUP BY節で使うために、ブロックの位置も求めています。

SELECT a.row,a.col,a.val FROM candidates a
JOIN (
  SELECT id,val,(row-1) DIV @m AS x,(col-1) DIV @m AS y FROM candidates
  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//

+-----+-----+-----+
| row | col | val |
+-----+-----+-----+
|   1 |   5 |   8 |
|   5 |   9 |   2 |
|   7 |   2 |   2 |
|   9 |   5 |   4 |
+-----+-----+-----+

 以上のヒントを実装するために、updateProblemを次のように修正します。決定場所をrow, col, valの形で取得しているというのは「解法1」と共通しているので、新たにわかった場所をUNIONで追加するだけです。

updateProblem
DROP PROCEDURE IF EXISTS updateProblem//

CREATE PROCEDURE updateProblem(theId INT)
BEGIN
  UPDATE problems JOIN
  (
    -- 候補が一つだけ(「解法1」)
    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

    UNION -- その数字が入る場所が行内に1カ所しかない
    SELECT a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT row,val FROM candidates
        GROUP BY row,val HAVING COUNT(val)=1
    ) tmp ON tmp.row=a.row AND tmp.val=a.val

    UNION -- その数字が入る場所が列内に1カ所しかない
    SELECT a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT col,val FROM candidates
        GROUP BY col,val HAVING COUNT(val)=1
    ) tmp ON tmp.col=a.col AND tmp.val=a.val

    UNION -- その数字が入る場所がブロック内に1カ所しかない
    SELECT a.row,a.col,a.val FROM candidates a
    JOIN (
      SELECT id,val,(row-1) DIV @m AS x,(col-1) DIV @m AS y
      FROM candidates
      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
  ) tmp2 ON problems.row=tmp2.row AND problems.col=tmp2.col
  SET problems.val=tmp2.val;
END;//

 これで解けます。

CALL initialize(CONCAT(
'   3     ',
'  146    ',
' 9    8  ',
'25       ',
' 8     4 ',
'       63',
'  4    7 ',
'    182  ',
'     2   '))//

CALL simpleDeduction(0)//

CALL display(0)//

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

残る課題

問題3
問題3

 この問題は、これまでの方法では解けません(この問題は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
-- 解けていない。

 この問題を解くためには新たな戦略が必要になりますが、それは第2部で紹介しようと思います。


  • 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