2 進変数の代数を使ったボードパズル

バイナリ変数の代数を使ったボードパズルでは、プレイヤーは、一連の手がかりセルと、変数 (未知数) としてマークされたその隣のセルを基に、隠されたオブジェクトを見つけます。値が 1 の変数は、オブジェクトがあるセルに対応します。逆に、値が 0 の変数は、空のセル (隠されたオブジェクトがない) に対応します。

これらのパズルは、(いいえ、はい)、(偽、真)、(存在しない、存在する)、( 0、1 ) などの 2 値変数の代数に基づいています。これにより、プレイヤーは、解決のためにいくつかの方程式と不等式をすばやく確立する必要があります。分割を使用すると、 問題の複雑さを軽減できます。さらに、パズルが1つだけ一意の解決方法が存在するように準備されている場合、この事実を使用して、計算なしでいくつかの変数を除外できます。

この問題は、整数線形計画法の特殊なケースである2進整数線形計画法としてモデル化することができます。 ^[1]

マインスイーパーとそのバリエーションは、このタイプのパズルの最も注目すべき例です。

以下の数式内の文字は変数として使用され、それぞれ0または1のいずれかの値のみを取ることができます。バイナリ変数を含む方程式の簡単な例を以下に示します。

a + b = 0

ここでは変数aとb が2 つありますが、方程式は 1 つです。解は、 aとb が0または1 の値しか取れないという事実によって制約されます。ここでの解は 1 つだけで、a = 0かつb = 0です。別の簡単な例を以下に示します。

a + b = 2

解決法は簡単です。a + b が2に等しくなるためには、aとbが1でなければなりません。

もう一つの興味深い事例を以下に示します。

a + b + c = 2

a + b ≤ 1

ここで、最初のステートメントは方程式であり、2 番目のステートメントは 3 つの可能なケースを示す不等式です。

1. a = 1かつb = 0、
2. a = 0かつb = 1であり、
3. a = 0かつb = 0、

最後のケースでは、 c = 2を強制することでcに矛盾が生じますが、これは不可能です。したがって、最初のケースと 2 番目のケースのどちらかが正しいことになります。これにより、 c は1でなければならないという事実が導き出されます。

大きな方程式を小さな形式に修正することは難しくありません。ただし、2 進変数を含む方程式セットは、線形代数を適用しても必ずしも解けるとは限りません。以下は、2 つの方程式の減算を適用する例です。

a + b + c + d = 3

ｃ ＋ ｄ ＝１

最初の文には4つの変数がありますが、2番目の文には2つの変数しかありません。後者はcとdの合計が1であることを意味します。この事実を最初の文に適用すると、上記の式は次のように簡略化できます。

a + b = 2

ｃ ＋ ｄ ＝１

バイナリ変数を使用した代数に基づくゲームは、さまざまな方法で視覚化できます。一般的な方法の 1 つは、方程式の右側をセル (ヒント セル) 内のヒントとして表し、ヒント セルの隣接セルを変数として表すことです。単純なケースを図 1 に示します。隣接セルは、エッジまたはコーナーを共有する上下、左右、コーナー セルであると想定できます。白いセルには、隠されたオブジェクトが含まれている場合もあれば、何も含まれていない場合もあります。つまり、これらはバイナリ変数です。これらは方程式の左側で発生します。各ヒント セル (図 1 の青い背景のセル) には、隠されたオブジェクトがある隣接セルの数に対応する正の数が含まれています。ボード上のオブジェクトの合計数は、追加のヒントとして与えることができます。変数がマークされた同じボードを図 2 に示します。

主な方程式は、与えられた隠されたオブジェクトの合計数を使用して書かれています。最初の図から、これは次の方程式に対応します。

a + b + c + d + e + f + g + h + i + j + k + m = 3

その他の方程式は、各ヒントセルごとに 1 つずつ構成されます。

a + b + c + e + f + h + i + j = 1

f + g + j + m = 1

h + i + j + k = 2

私 + j + m = 2

上記の方程式を解く方法はいくつかありますが、次の明示的な方法を適用できます。

1. 方程式からi + j + m = 2 であることがわかります。ただし、jとm は番号1のセルに隣接するため、次が当てはまります: j + m ≤ 1。つまり、変数i は1でなければなりません。
2. i = 1であり、変数iは番号1のヒントセルの隣接セルであるため、変数a、b、c、e、f、h、およびjはゼロでなければなりません。 2 番目の式でi = 1 を次のように置き換えることで、同じ結果を得ることができます。a + b + c + e + f + h + j = 0 。これは、 a = 0、b = 0、c = 0、e = 0、f = 0、h = 0、j = 0と同等です。
3. 図 3 は、ステップ 1 とステップ 2 の後に取得されます。 '–' の付いた灰色のセルは、値0を持つ変数です。 記号Δの付いたセルは、値1を持つ変数に対応します。 変数k は、値2を持つ左端の手がかりセルの唯一の隣接セルです。 この手がかりセルには、オブジェクトを持つ隣接セルが 1 つと、変数kを持つ残りのセルが 1 つだけあります。 したがって、k は1でなければなりません。
4. 同様に、変数mも1でなければなりません。これは、値が2である右端の手がかりセルに隣接する唯一の残りの変数だからです。
5. k = 1、m = 1、i = 1なので、 3 つの隠されたオブジェクトのマーキングが完了し、d = 0、g = 0 となります。最終的な解は図 4 に示されています。

上記の例（図 2）では、変数a、b、c、e は手がかりセル1の隣接セルであり、他のセルの隣接セルではありません。次のような解決策が考えられます。

• a = 1、 b = 0、 c = 0、 e = 0
• a = 0、 b = 1、 c = 0、 e = 0
• a = 0、 b = 0、 c = 1、 e = 0
• a = 0、 b = 0、 c = 0、 e = 1

ただし、パズルが 1 つの (一意の) 解のみを持つように作成されている場合は、変数a、b、c、e をすべて0 に設定できます。そうしないと、複数の解が存在します。

パズルの構成によっては、プレイヤーがパーティショニング^[2]を使用して複雑さを軽減できる場合があります。例を図 5 に示します。各パーティションは、隠されたオブジェクトの数に対応します。パーティション内の隠されたオブジェクトの合計は、ボード上に隠されたオブジェクトの総数と等しくなければなりません。パーティショニングを決定する 1 つの方法は、共通の隣接セルを持たないリード手がかりセルを選択することです。図 5 の赤い透明ゾーンの外側のセルは空でなければなりません。言い換えると、すべて白いセルには隠されたオブジェクトがありません。上部のパーティション ゾーン内には隠されたオブジェクトがなければならないため、上から 3 番目の行には隠されたオブジェクトが含まれていてはなりません。このことから、手がかりセルの周囲の下段の 2 つの可変セルには隠されたオブジェクトがなければならないことがわかります。残りの解決方法は簡単です。

場合によっては、プレーヤーは変数セルを1に設定し、矛盾が生じていないかチェックできます。図 6 の例は矛盾のチェックを示しています。隠しオブジェクトΔでマークされたセルがテスト対象です。このマークにより、すべての変数 (灰色のセル) が0に設定されます。これは矛盾に続きます。値1で赤でマークされた手がかりセルには、隠しオブジェクトを含めることができる隣接セルが残っていません。したがって、テスト対象のセルには隠しオブジェクトが含まれていてはなりません。代数形式では、次の 2 つの方程式があります。

a + b + c + d = 1

a + b + c + d + e + f + g = 1

ここで、a、b、c、およびd は、図 6 の上の灰色の 4 つのセルに対応します。Δのセルには変数fが付けられ、他の 2 つの灰色のセルにはeとgが付けられています。 f = 1と設定すると、a = 0、b = 0、c = 0、d = 0、e = 0、g = 0となります。上記の最初の式では、左辺は0になりますが、右辺は1になります。これは矛盾です。

いくつかのパズルでは、結論に到達するために、試行と確認を複数のステップで適用する必要がある場合があります。これは、矛盾につながる可能性のあるパスを排除するため のバイナリ検索アルゴリズム^{[3]と同等です。}

バイナリ変数のため、ソリューションの方程式セットは線形性を持ちません。言い換えると、方程式行列のランクは必ずしも適切な複雑さに対応しない可能性があります。

この種類のパズルの複雑さは、いくつかの方法で調整できます。最も簡単な方法の 1 つは、ボード上のセルの総数に対するヒント セルの数の比率を設定することです。ただし、この方法では、固定比率に対して複雑さの範囲が大きく変化する可能性があります。別の方法は、いくつかの問題解決戦略に基づいて、ヒント セルを段階的に減らすことです。複雑な戦略は、方程式を別の方程式で減算するなど、複雑さのレベルが高い場合に有効にしたり、試行と確認のステップをより深くしたりすることができます。ボードのサイズが大きくなると、問題の範囲が広がります。隠されたオブジェクトの数とセルの総数の比率も、パズルの複雑さに影響します。

• ポール・ハルモス、素朴集合論。ニュージャージー州プリンストン: D. Van Nostorm Company、1960 年。Springer -Verlag 社、ニューヨーク、1974 年再版。ISBN 0-387-90092-6  (Springer-Verlag 版)。
• Alexander Schrijver、『線形計画法と整数計画法の理論』、John Wiley & Sons、1986年。1999年に再版。ISBN 0-471-98232-6。 
• Adam Drozdek、『C++ のデータ構造とアルゴリズム』、Brooks/Cole、第 2 版、2000 年。ISBN 0-534-37597-9。