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

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

目次へ

WXYZ-Wing-4222  の判別アルゴリズムと探索の関数

Sudokuwiki.org に WXYZ-Wing の解説 が載っている。

  図を見ていると分かったような気になるがプログラムを作るために WXYZ-Wing を判別する次のアルゴリズムを作った。この配置の特徴を示すため WXYZ-Wing-4222 と呼ぶことにする。

  • データ構造を{ {{W,X,Y, Z},{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, Z}, {W, Z}, {X, Z},{Y, Z} } は Naked Quads の 4/2/2/2 に属している。 クリック here.
  • 条件2.
    {W, X, Y, Z} は 幹 (stem) を意味する。{W,Z}, {X, Z} と {Y, Z} は 枝 (branch) を表す。書き直すと { stem, branch1, branch2, branch3 } になる。
  • この配置では 幹 と 枝 の要素の数が {4, 2, 2, 2} なので WXYZ-Wing-4222 と呼ぶことにする。
  • 条件3.
    branch2 と branch3 はstem が入っている box 外にあり、 stem と横 (行) または縦 (列) に並んでいる。すなわち、w == x && z != y または w != x && z == y である。
    1. branch2 と branch3 は同じ box 内でもよいし違うbox でもよい。
    2.  stem と branch2 の距離は、stem と branch3 の距離より小さいものとする。
  • 条件4.
    branch1 は stem が入っている box 内にあり、stem と{ branch2, branch3 }が並んだ行や列の外にある。
    すなわち、IF x == w, u != x . IF y == z, v != y .
    1. stem, branch2 と branch1 は直線上に並ばない。
削除する数について
  • 削除できる数は 4 組に共通にある Z である。
  • Row:
    stem {W, X, Y, Z} と { branch2 {X, Z} , branch3 {Y, Z} } が行に並んでいる場合:
    1. stem {W, X, Y, Z} が属する box の中で、stem {W, X, Y, Z} と { branch2 {X, Z} , branch3 {Y, Z} } が入っている行にある Z を削除できる。
  • Column:
    stem {W, X, Y, Z} と { branch2 {X, Z} , branch3 {Y, Z} } が列に並んでいる場合:
    1. stem {W, X, Y, Z} が属する box の中で、stem {W, X, Y, Z} と { branch2 {X, Z} , branch3 {Y, Z} } が入っている列にある Z を削除できる。
  • 削除できる数の番地がブランクの場合には WXYZ-Wing の候補から除く。
  • 削除できる数の番地に数が無い場合には WXYZ-Wing の候補から除く。

Mathematica Notebook

次の WXYZ-Wing の例を使って次の Mathematica ノートブックで議論している。
次をクリックすると開きます。WXYZ-Wing-4222 notebook

 

The Logic of Sudoku,  p.59 の例

まとめ

  • WXYZ-Wing-4222 のデータ構造を{ {{W,X,Y,Z}, {W, Z}, {X, Z}, {Y, Z}}, {{x, y}, {u, v}, {w, z}, {i, j} } } と表すことにする。 {{x, y}, {u, v}, {w, z}, {i, j} } はそれぞれのセルの番地とする。
  • WXYZ-Wing-4222 を判別する関数 wxyzWing4222Q[ data : {{{_, _, _,_}, {_, _}, {_, _}, {_, _}}, {{_, _}, {_, _}, {_, _}, {_, _}}} ] を作った。
  • WXYZ-Wing-4222 を見つける関数 findWXYZWing4222Delete2[ map_ } を作った。
  • 見つけた WXYZWing-4222 のデータを使って 削除できる番号と番地を求める関数 makeDeletelist2byXYZWing4222[ result_, map_] を作った。
  • これらの関数を基礎にして実用的なプログラムを作るのが課題です。

目次へ