ペンシルパズル BINOXXO を プログラムで解いて みました。
アルゴリズム(人間用)
盤面を次のルールに従って書き換えていくと、 問題が解けます。
条件1:◯ならびに×が隣り合うのは2つまで
- 空欄を挟んで同じ記号がある場合に、間の空欄を反対の記号で埋める
- O_O → OXO
- 同じ記号が連続している場合に、その両端を反対の記号で埋める
- OO_ → OOX
- 同一行(列)に同じ記号が4つ使われている場合に、
その記号を置くと逆の記号が3つ連続するマスを探し、
そこに逆の記号を置く。
- (Xがすでに4つ使われていると想定して)
__OX_ → __OXO / _O_X_ → _O_XO / O__X_ → O__XO
最後のマスにXを置くと、最初の3マスがOOOとなってしまう。 - (Xがすでに4つ使われていると想定して)
____ → O__O
最初もしくは最後のマスにXを置くと、残りの3マスがOOOとなってしまう。
- (Xがすでに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連続になる。
- X__X__O__X → XOOX__O__X
条件2:各列・行には同数の○ならびに×が入る
- 同一行(列)に同じ記号が5つ使われている場合に、空欄を逆の記号で埋める(条件2)
- OOXOXOXXO_ → OOXOXOXXOX
条件3:すべての行・列は異なる並びになる
- 同一行(列)に同じ記号がすでに5つ配置されている行(列)に対して、
その記号が同じ位置に4つ配置されている行(列)Lがある場合。
Lの残りの1つの位置には、反対の記号を配置する(条件3)
- (他にOOXOXXOXOXという行がある場合) OOX___OXOX → OOXX__OXOX
アルゴリズム(コンピューター用)
コンピューターに解かせる場合には、 条件1の3,4を細かく場合分けせず、 力づくで解かせるほうが簡単です。
まず行(列)の現在の状況が与えられると、 その行で使える残りのXとOの数が分かります。
行の状況 | 残り X | 残り O |
---|---|---|
X__X__O__X | 2 | 4 |
これで作れる組み合わせを列挙すると、 次のようになります。 人間には面倒ですが、 コンピューターなら全パターン列挙は 一瞬 です。
行 | 条件1を満たすか |
---|---|
XXXXOOOOOX | NG |
XXOXXOOOOX | NG |
XXOXOXOOOX | NG |
XXOXOOOXOX | NG |
XXOXOOOOXX | NG |
XOXXXOOOOX | NG |
XOXXOXOOOX | NG |
XOXXOOOXOX | NG |
XOXXOOOOXX | NG |
XOOXXXOOOX | NG |
XOOXXOOXOX | OK |
XOOXXOOOXX | NG |
XOOXOXOXOX | OK |
XOOXOXOOXX | OK |
XOOXOOOXXX | NG |
大半は OOO もしくは XXX と同一記号が三連続しており、 条件1を満たしません。 条件を満たすものは次の三通りです。
行 |
---|
XOOXXOOXOX |
XOOXOXOXOX |
XOOXOXOOXX |
太字は全てのパターンで共通している部分です。 もともと入力に含まれていたXとOは当然共通していますが、 それに加えて左から2文字目と3文字目もOで共通しているので、 このマス目の値が確定します。
ついでに条件2も同じアルゴリズムでカバーできます。