目次へ
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]
⇒ {{{2,4,6},{},{2,4,6,9},{2,3,8,9},{1,3,8,9},{1,2,8,9},{},{1,2,8},{3,6,8,9}},
{{},{},{},{2,7,8,9},{7,8,9},{2,7,8,9},{},{2,8},{6,7,8,9}},
{{},{9},{2,9},{},{},{1,2,5,7,9},{1,2,3,7,9},{1,2},{3,7,9}},
{{6,7},{},{6,8},{7,8,9},{6,7,8,9},{},{1,9},{},{}},
{{3,7},{},{5,8},{2,3,5,7,8,9},{3,5,7,8,9},{2,5,7,8,9},{2,9},{},{4,8,9}},
{{},{},{5,6,8},{},{3,5,6,8},{2,5,6,8},{2},{},{8}},
{{4,6},{5,6,8,9},{4,5,6,8,9},{4,5,7,8,9},{},{},{6,7},{5},{}},
{{1,4,6},{5,6},{},{4,5,7},{1,5,6,7},{1,5,6,7},{},{},{}},
{{1,2,6},{5,6,8,9},{},{5,8,9},{1,5,6,8,9},{1,5,6,8,9},{3,6},{},{3,6}}};
mapini//MatrixForm
mapini=makeMap[ini];
Show[Rasterize[plotMapGrid[ini, mapini]], ImageSize -> 400]
関数 plotMapGrid は (2) で導入したものです。ただし、plotMapGrid ではこの図のように候補に色がつきません。色付けは後に説明します。
続く
次は、「候補図から解を見つける」を説明します。