読者です 読者をやめる 読者になる 読者になる

XYZ-Wing の判別関数と探索関数: sudokuwiki.org

目次へ

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} が行に並んでいる場合:
    1. stem {X, Y, Z} が属する box の中で、stem {X, Y, Z} と branch2 {Y, Z} が入っている行にある Z を削除できる。
  • Column: stem {X, Y, Z} と branch2 {Y, Z} が列に並んでいる場合:
    1. stem {X, Y, Z} が属する box の中で、stem {X, Y, Z} と branch2 {Y, Z} が入っている列にある Z を削除できる。
  • 削除できる数の番地がブランクの場合には XYZ-Wing の候補から除く。
  • 削除できる数の番地に数が無い場合には XYZ-Wing の候補から除く。

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_] を作った。
  • これらの関数を基礎にして実用的なプログラムを作るのが課題です。

目次へ