SQLによる数独の解法

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

数独の解法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行目に入り得る数字を調べます。

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

　この問題は、これまでの方法では解けません（この問題は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部で紹介しようと思います。