ペンシルパズル BINOXXO ソルバー

ペンシルパズル BINOXXOプログラムで解いて みました。

アルゴリズム(人間用)

盤面を次のルールに従って書き換えていくと、 問題が解けます。

条件1:◯ならびに×が隣り合うのは2つまで

  1. 空欄を挟んで同じ記号がある場合に、間の空欄を反対の記号で埋める
    • O_O → OXO
  2. 同じ記号が連続している場合に、その両端を反対の記号で埋める
    • OO_ → OOX
  3. 同一行(列)に同じ記号が4つ使われている場合に、 その記号を置くと逆の記号が3つ連続するマスを探し、 そこに逆の記号を置く。
    • (Xがすでに4つ使われていると想定して)
      __OX_ → __OXO / _O_X_ → _O_XO / O__X_ → O__XO
      最後のマスにXを置くと、最初の3マスがOOOとなってしまう。
    • (Xがすでに4つ使われていると想定して)
      ____ → O__O
      最初もしくは最後のマスにXを置くと、残りの3マスがOOOとなってしまう。
  4. 同一行(列)に同じ記号が3つ使われている場合に、 4つ目を置くと残りのマスで逆の記号が3つ並んでしまうマスを探し、 そこに逆の記号を置く。
    • X__X__O__X → XOOX__O__X
      最初の空欄二ついずれかにXを置くと、残りのXが1つに対して残りのマスが __O__ となる。 したがって __O もしくは O__ のいずれかが OOO となってしまう。
    • XO_____OXX → XO__O__OXX
      空欄の中央に X を置くと、残りのXが一つに対して残りのマスが O__X__O となる。 したがってXの左の O__ もしくは右の __O いずれかが OOO となる。
    • X______OXX → XO_____OXX
      最初の空欄にXを置くと、残りのXが一つに対して残りのマスが _____O となる。 Xを残りのどこに置いてもOが3連続になる。

条件2:各列・行には同数の○ならびに×が入る

  1. 同一行(列)に同じ記号が5つ使われている場合に、空欄を逆の記号で埋める(条件2)
    • OOXOXOXXO_ → OOXOXOXXOX

条件3:すべての行・列は異なる並びになる

  1. 同一行(列)に同じ記号がすでに5つ配置されている行(列)に対して、 その記号が同じ位置に4つ配置されている行(列)Lがある場合。 Lの残りの1つの位置には、反対の記号を配置する(条件3)
    • (他にOOXOXXOXOXという行がある場合) OOX___OXOX → OOXX__OXOX

アルゴリズム(コンピューター用)

コンピューターに解かせる場合には、 条件1の3,4を細かく場合分けせず、 力づくで解かせるほうが簡単です。

まず行(列)の現在の状況が与えられると、 その行で使える残りのXとOの数が分かります。

行の状況残り X残り O
X__X__O__X24

これで作れる組み合わせを列挙すると、 次のようになります。 人間には面倒ですが、 コンピューターなら全パターン列挙は 一瞬 です。

条件1を満たすか
XXXXOOOOOXNG
XXOXXOOOOXNG
XXOXOXOOOXNG
XXOXOOOXOXNG
XXOXOOOOXXNG
XOXXXOOOOXNG
XOXXOXOOOXNG
XOXXOOOXOXNG
XOXXOOOOXXNG
XOOXXXOOOXNG
XOOXXOOXOXOK
XOOXXOOOXXNG
XOOXOXOXOXOK
XOOXOXOOXXOK
XOOXOOOXXXNG

大半は OOO もしくは XXX と同一記号が三連続しており、 条件1を満たしません。 条件を満たすものは次の三通りです。

XOOXXOOXOX
XOOXOXOXOX
XOOXOXOOXX

太字は全てのパターンで共通している部分です。 もともと入力に含まれていたXとOは当然共通していますが、 それに加えて左から2文字目と3文字目もOで共通しているので、 このマス目の値が確定します。

ついでに条件2も同じアルゴリズムでカバーできます。

コメントを送る

お気軽にお送りください。