目次へ
Y-Wing type 1 の判別アルゴリズム
Sudokuwiki に載っている Y-Wing の説明には2種類の Y-Wing が載っているので、type 1 と type 2 に分けて議論することにする。この図を type 1 とする。
図を見ていると分かったような気になるがプログラムを作るために Y-Wing type 1 を判別する次のアルゴリズムを作った。
- 上の図の 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: branch 1 は stem が属している box にはなく、 stem と横(行)に並んでいるものとする。すなわち、x == u && y != v 。
- 条件4: branch2 は stem が属している box にはなく、 stem と縦(列)に並んでいるものとする。すなわち、x != u && y == v 。
- 削除できる数について
- 条件5: branch 1 と branch 2 に共通に入っている数 C を endpoint と呼び、削除できる数である。
- branch2 の {w, z} の行番号 w と branch1 の {u, v} の列番号 v とからなるセルの番地 {w, v} の中にある C を削除できる。
Mathematica Notebook
Y-Wing の例を使って次の Mathematica ノートブックで議論している。
次をクリックすると開きます。 Y-Wing type1 notebook
プログラムによれば、削除できるものは 番地 {6, 3} の 8 と 番地 {4, 1} の 4 である。最初の解が書き込まれていない。 Sudokuwiki に質問したところ、Y-Wing strategy の Comment に採択されて載っている。
まとめ
- Y-Wing のデータ構造を { {{A, B}, {B, C}, {A, C}}, {{x,y},{u,v},{w,z}} } と表すことにする。ここで {{x, y}, {u, v}, {w, z}} はそれぞれのセルの番地を意味する。
- Y-Wing type 1 を判別する関数 yWingType1Q[ data : {{{_, _}, {_, _}, {_, _}}, {{_, _}, {_, _}, {_, _}}} ] を作った。
- Y-Wing type 1を見つける関数 findYWingType1Delete[ map_ } を作った。
- 見つけた YWing type 1 のデータを使って 削除できる番号と番地を求める関数 makeDeletelistType1[ result_] を作った。
