目次へ
Y-Wing type 2 の判別アルゴリズムと探索の関数
Sudokuwiki に載っている Y-Wing の説明には2種類の Y-Wing が載っているので、type 1 と type 2 に分けて議論することにする。この図を type 2 とする。
図を見ていると分かったような気になるがプログラムを作るために Y-Wing type 2 を判別する次のアルゴリズムを作った。
- 上の図の Y-Wing のデータ構造を { {{A, B}, {B, C}, {A, C}}, {{x,y},{u,v},{w,z}} } と表すことにする。
ここで {{x, y}, {u, v}, {w, z}} はそれぞれのセルの番地を表す。 - 条件1: {{A, B}, {B, C}, {A, C}} は Naked Triples の 2/2/2 に属している。 Click here.
- 条件2. {A, B} は 幹 (stem) を意味する。{B, C} と {A, C} は 枝 (branch) を表す。書き直すと {{stem}, {branch1}, {branch2}} になる
- 条件3: branch1 は stem が入っている box 内にあり、stem の行や列の外にある。すなわち、 u != x &&, v != y である。
- 条件4: branch2 はstem が入っている box 外にあり、 stem と横 (行) または縦 (列) に並んでいる。
すなわち、w == x && z != y または w != x && z == y である。 - ----------
- 削除できる数について。横並びと縦並びを分ける必要がある。
- Row: stem {A,B} と branch2 {A,C} が行に並んでいる場合：
- branch2 {A,C} が属す box 内で branch1 {B,C} の行ある C を削除できる。
- stem {A,B} が属する box の中で、stem {A,B} と branch2 {A, C} が属する行にある C を削除できる。
- Column: stem {A,B} と branch2 {A,C} が列に並んでいる場合：
- branch2 {A,C} が属す box 内で branch1 {B,C} の列にある C を削除できる。
- stem {A,B} が属する box の中で、stem {A,B} と branch2 {A, C} が属する列にある C を削除できる。
- 削除できる数の番地がブランクの場合、Y - Wing - type2 の候補から除く。
- 削除できる数の番地に削除できる数が無い場合、Y - Wing - type2 の候補から除く。
備考: XYZ-Wing を調べていて気が付いたこと。
- 条件3: branch1 は stem が入っている box 内にあり、stem の行や列の外にある。
- これに関して変更が必要に思われる。
- 条件3: branch1 は stem が入っている box 内にあり、stem と branch 2 の並びに branch 1 を加えたとき直線状に並ばない位置にある。
Mathematica Notebook
Y-Wing の例を使って次の Mathematica ノートブックで議論している。
次をクリックすると開きます。Y-Wing type 2 notebook
まとめ
- Y-Wing のデータ構造を { {{A, B}, {B, C}, {A, C}}, {{x,y},{u,v},{w,z}} } と表すことにする。ここで {{x, y}, {u, v}, {w, z}} はそれぞれのセルの番地を意味する。
- Y-Wing type 2 を判別する関数 yWingType2Q[ data : {{{_, _}, {_, _}, {_, _}}, {{_, _}, {_, _}, {_, _}}} ] を作った。
- Y-Wing type 2を見つける関数 findYWingType2Delete2[ map_ } を作った。
- 見つけた YWing type 2 のデータを使って 削除できる番号と番地を求める関数 makeDeletelist2Type2[ result_, map_] を作った。
- これらの関数を基礎にして実用的なプログラムを作るのが課題です。
