目次へ
XYZ-Wing の判別アルゴリズムと探索の関数
Sudokuwiki.org に XYZ-Wing の解説 が載っている。
図を見ていると分かったような気になるがプログラムを作るために XYZ-Wing を判別する次のアルゴリズムを作った。
- データ構造を{ {{X,Y, Z}, {X, Z}, {Y, Z}}, {{x, y}, {u, v}, { w, z}} } と表すことにする。 {{x, y}, {u, v}, {w, z}} はそれぞれのセルの番地とする。
- 条件1. {{X, Y, Z}, {X, Z}, {Y, Z}} は Naked Triples の 3/2/2 に属している。。 Click here.
- 条件2. {X, Y, Z} は 幹 (stem) を意味する。
- {X, Z} と {Y, Z} は 枝 (branch) を表す。書き直すと {{stem}, {branch1}, {branch2}} になる。
- 条件3. branch2 はstem が入っている box 外にあり、 stem と横 (行) または縦 (列) に並んでいる。
すなわち、w == x && z != y または w != x && z == y である。 - 条件4. branch1 は stem が入っている box 内にあり、stem と branch2 が並んだ行や列の外にある。
すなわち、IF x == w, u != x . IF y == z, v != y . stem, branch2 と branch1 は直線上に並ばない。 - ----------
- 削除できる数について。削除できる数は 3 組に共通にある Z である。
- 横並びと縦並びを分ける必要がある。
- Row: stem {X, Y, Z} と branch2 {Y, Z} が行に並んでいる場合:
- stem {X, Y, Z} が属する box の中で、stem {X, Y, Z} と branch2 {Y, Z} が入っている行にある Z を削除できる。
- Column: stem {X, Y, Z} と branch2 {Y, Z} が列に並んでいる場合:
- stem {X, Y, Z} が属する box の中で、stem {X, Y, Z} と branch2 {Y, Z} が入っている列にある Z を削除できる。
Mathematica Notebook
次の XYZ-Wing の例を使って次の Mathematica ノートブックで議論している。
次をクリックすると開きます。XYZ-Wing notebook
まとめ
- XYZ-Wing のデータ構造を{ {{X,Y,Z}, {X, Z}, {Y, Z}}, {{x, y}, {u, v}, { w, z}} } と表すことにする。 {{x, y}, {u, v}, {w, z}} はそれぞれのセルの番地とする。
- XYZ-Wing を判別する関数 xyzWingQ[ data : {{{_, _, _}, {_, _}, {_, _}}, {{_, _}, {_, _}, {_, _}}} ] を作った。
- XYZ-Wing を見つける関数 findXYZWingDelete2[ map_ } を作った。
- 見つけた XYZWing のデータを使って 削除できる番号と番地を求める関数 makeDeletelist2byXYZWing[ result_, map_] を作った。
- これらの関数を基礎にして実用的なプログラムを作るのが課題です。