Sudoku(数独) を Mathematicaで解く(3): makeMap

目次へ

3. 候補の求め方

はじめに、1 行1列に入れるべき数の候補を検討する。Sudoku のルールによれば、1行に7と5 があるので 1 から9 の候補の数から 5, 7 が除かれる。1列に 5,8,9 があるので除かれる。1 行1列が属する 3x3 のブロックに 1,3,5,7,8 があるので候補から除かれる。従って、候補は 2,4,6 となる。これを Mathematica で表現する。

1 行目について

行列 ini から1行を取り出し、そこに含まれる数を選び出す。出力を ⇒ を使って表すことにします。

ini[[1]]
⇒ {Null, 7, Null, Null, Null, Null, 5, Null, Null}

Null を除くには関数 DeleteCases を使う

row = DeleteCases[ini[[1]], Null]
⇒ {7, 5}
1列について

行列 ini から1列を取り出し含まれる数を選び出す。

ini[[All, 1]]
⇒ {Null, 5, 8, Null, Null, 9, Null, Null, Null}

col = DeleteCases[ini[[All, 1]], Null]
⇒ {5, 8, 9}
3x3 のブロックについて

1行1列が属している 3x3 のブロックについて検討する。3x3 のブロックは次のようにして抜き取ることができる。

ini[[1;;3,1;;3]]
⇒ {{Null, 7, Null}, {5, 3, 1}, {8, Null, Null}}

波括弧が2重なっているので、内側の波括弧をFlatten を使って削除する。

Flatten[ini[[1;;3,1;;3]]]
⇒ {Null, 7, Null, 5, 3, 1, 8, Null, Null}

box = DeleteCases[Flatten[ini[[1;;3,1;;3]]], Null]
⇒ {7, 5, 3, 1, 8}
まとめると

row,colとboxの和集合を作る。

Union[row, col, box]
⇒ {1, 3, 5, 7, 8, 9}

候補の数の集合 {1,2,3,4,5,6,7,8,9} からこれを除いた数の集合が候補になる。

集合の引き算の関数は Complement であるから次のように書くことができる。

Complement[{1,2,3,4,5,6,7,8,9}, Union[row, col, box]]
⇒ {2, 4, 6}

ここで、1 から9の数からなるリストは、関数 Range[9] で作ることができるので、整理して書くと次になる。

Complement[Range[9], Union[row, col, box]]
⇒ {2, 4, 6}
追加説明

1 行2列には数が入っている。入れるべき数の候補は無いので、 { } で表現する。

一般化

以上を一般化して、i 行 j 列の場合を検討する。i 行を取り出すには ini[[i]] を使い、j 列を取り出すにはini[[All,j]] で取り出すことができる。ここで問題なのは、i 行 j 列が属する 3x3 ブロックの決定方法である。次の関数が解決してくれる。

f[i_]:=Which[1<=i<=3,1;;3, 4<=i<=6,4;;6, 7<=i<=9,7;;9]
f[1]
⇒ 1;;3

1 行1 列のブロックはini[[1;;3,1;;3]]である。従ってini[[f[1],f[1]]]と書ける。

1 行4 列のブロックは ini[[ 1;;3,4;;6]]である。ini[[f[1],f[4]]]と書ける。

{f[1],f[4]}
⇒ {1;;3,4;;6}

関数の定義

i行j列の候補のリストをつくる関数 candidates は次になる。全ての要素について調べれば、候補のリストをつくる関数 makeMap になる。

candidates[ini_?MatrixQ,{i_,j_}]:=Module[{f},
  f[k_]:=Which[1<=k<=3, 1;;3,4<=k<=6,4;;6,7<=k<=9,7;;9];
  If[ini[[i,j]]=!=Null,{},
    Complement[Range[9],
    Union[ini[[i]],ini[[All,j]],Flatten[ini[[f[i],f[j]]]]]]
  ]
  ]
makeMap[ini_?MatrixQ]:=Table[candidates[ini,{i,j}],{i,1,9},{j,1,9}]

使い方

candidates[ini, {1, 1}]
⇒ {2, 4, 6}

mapini=makeMap[ini];
Show[Rasterize[plotMapGrid[ini, mapini]], ImageSize -> 400]

関数 plotMapGrid は (2) で導入したものです。ただし、plotMapGrid ではこの図のように候補に色がつきません。色付けは後に説明します。

続く

次は、「候補図から解を見つける」を説明します。

目次へ