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

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

アルゴリズム（人間用）

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

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

1. 空欄を挟んで同じ記号がある場合に、間の空欄を反対の記号で埋める
   • O_O → OXO
2. 同じ記号が連続している場合に、その両端を反対の記号で埋める
   
   • OO_ → OOX
3. 同一行（列）に同じ記号が４つ使われている場合に、 その記号を置くと逆の記号が３つ連続するマスを探し、 そこに逆の記号を置く。
   
   • （Xがすでに4つ使われていると想定して）
     __OX_ → __OXO / _O_X_ → _O_XO / O__X_ → O__XO
     最後のマスにXを置くと、最初の３マスがOOOとなってしまう。
   • （Xがすでに4つ使われていると想定して）
     ____ → O__O
     最初もしくは最後のマスにXを置くと、残りの３マスがOOOとなってしまう。
4. 同一行（列）に同じ記号が３つ使われている場合に、 ４つ目を置くと残りのマスで逆の記号が３つ並んでしまうマスを探し、 そこに逆の記号を置く。
   • X__X__O__X → XOOX__O__X
     最初の空欄二ついずれかにXを置くと、残りのXが１つに対して残りのマスが __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が３連続になる。

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

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

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

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

アルゴリズム（コンピューター用）

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

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

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

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

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

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