目次へ
WXYZ-Wing-3222 の判別アルゴリズムと探索の関数
Sudokuwiki.org に WXYZ-Wing の解説 が載っている。WXYZ-Wing-4222 を参考に WXYZ-Wing-3222 を判別する次のアルゴリズムを作った。
次の例は WXYZ-Wing-3222 で削除できるのは {F, 6} の 5 である。
削除した結果 6列 の{{G, 6}, {I, 6}} にある 5 が Box/Line Reductionに対応し Box 8 内にある２個の 5 が削除できる。
上の WXYZ-Wing の例は 幹 (stem) の WXYZ が WXY になっている。データを次のように表現することにする。
- データ構造を{ {{W,X,Y},{W,Z}, {X, Z}, {Y, Z} }, { {x, y}, {u, v}, {w, z},{ i, j } } } と表すことにする。 {{x, y}, {u, v}, {w, z}, { i, j }} はそれぞれのセルの番地とする。
- 条件1.
{ {W, X, Y}, {W, Z}, {X, Z},{Y, Z} } は Naked Quads の 3/2/2/2 に属している。 クリック here. - 条件2.
{W, X, Y} は 幹 (stem) を意味する。{W,Z}, {X, Z} と {Y, Z} は 枝 (branch) を表す。書き直すと { stem, branch1, branch2, branch3 } になる。
この配置では 幹 と 枝 の要素の数が {3, 2, 2, 2} なので WXYZ-Wing-3222 と呼ぶことにする。 - 条件3.
branch1 は stem が入っている box 内にあり、stem と{ branch2, branch3 }が並んだ行や列の外にある。すなわち( stem, branch2, branch3 ) と branch1 は直線上に並ばない。 if x == w== i, then u != x . if y == z == j, then v != y . - 条件4.
branch2 と branch3 はstem が入っている box 外にあり、 stem と横 (行) または縦 (列) に並んでいる。すなわち、w == x && z != y または w != x && z == y である。- branch2 と branch3 は同じ box 内でもよいし違うbox でもよい。
- stem と branch2 の距離は、stem と branch3 の距離より小さいものとする。
削除する数について
- 削除できる数は 3個の branch に共通にある Z である。
- Row:
stem {W, X, Y} と { branch2 {X, Z} , branch3 {Y, Z} } が行に並んでいる場合：- stem {W, X, Y, Z} が属する box の中で、stem {W, X, Y} と { branch2 {X, Z} , branch3 {Y, Z} } が入っている行にある Z を削除できる。
- Column:
stem {W, X, Y} と { branch2 {X, Z} , branch3 {Y, Z} } が列に並んでいる場合：- stem {W, X, Y} が属する box の中で、stem {W, X, Y, Z} と { branch2 {X, Z} , branch3 {Y, Z} } が入っている列にある Z を削除できる。
- 削除できる数の番地がブランクの場合には WXYZ-Wing の候補から除く。
- 削除できる数の番地に数が無い場合には WXYZ-Wing の候補から除く。
Mathematica Notebook
次の WXYZ-Wing の例を使って次の Mathematica ノートブックで議論している。
次をクリックすると開きます。WXYZ-Wing-3222 notebook
まとめ
- WXYZ-Wing-3222 のデータ構造を{ {{W,X,Y}, {W, Z}, {X, Z}, {Y, Z}}, {{x, y}, {u, v}, {w, z}, {i, j} } } と表すことにする。 {{x, y}, {u, v}, {w, z}, {i, j} } はそれぞれのセルの番地とする。
- WXYZ-Wing-3222 を判別する関数 wxyzWing3222Q[ data : {{{_, _, _}, {_, _}, {_, _}, {_, _}}, {{_, _}, {_, _}, {_, _}, {_, _}}} ] を作った。
- WXYZ-Wing-3222 を見つける関数 findWXYZWing3222Delete2[ map_ } を作った。
- 見つけた WXYZWing-3222 のデータを使って 削除できる番号と番地を求める関数 makeDeletelist2byXYZWing3222[ result_, map_] を作った。
- これらの関数を基礎にして実用的なプログラムを作るのが課題です。
