ライトアウト（ゲーム）

ライトアウトは、 1995年にタイガーエレクトロニクスがリリースした電子ゲームです。 ^[1]このゲームは、5×5のライトのグリッドで構成されています。ゲームが開始されると、これらのライトのランダムな番号または保存されたパターンがオンになります。いずれかのライトを押すと、そのライトと隣接するライトが切り替わります。パズルの目的は、できるだけ少ないボタン操作ですべてのライトをオフにすることです。 ^{[1] [2]}

同様の電子ゲームであるMerlin は、1970年代にパーカー・ブラザーズによってリリースされ、3×3のグリッドで同様のルールを採用していました。別の同様のゲームは、1983年にバルカン・エレクトロニクスによってXL-25という名前で制作されました。タイガー・トイズも1997年にゲーム・コムの携帯ゲーム機用にライト・アウトのカートリッジ版を制作し、ゲーム機に無料で同梱されました。ライト・アウトに似た新しいパズルが多数リリースされており、例えばライト・アウト 2000 (5×5で複数の色)、ライト・アウト・キューブ(6つの3×3の面でエッジ全体に効果があります)、ライト・アウト・デラックス(6×6) などがあります。 ^{[1] [2]}

Lights Out は、 Avi Olti、Gyora Benedek、Zvi Herman、Revital Bloomberg、Avi Weiner、Michael Ganor などのグループによって作成されました。グループのメンバーは共同で、または個別に、Hidato、NimX、iTop など、他のゲームもいくつか発明しました。

ゲームは 5 x 5 のライトのグリッドで構成されています。ゲームが開始されると、これらのライトのランダムな番号または保存されたパターンがオンになります。いずれかのライトを押すと、そのライトと隣接する 4 つのライトが切り替わります。パズルの目的は、すべてのライトをオフにすることです。できれば、できるだけ少ないボタン操作でオフにしてください。^{[1] [4]}

ライトがオンの場合、オフにするには奇数回切り替える必要があります。ライトがオフの場合、オフのままにするには偶数回（まったく切り替えないことも含む）切り替える必要があります。ゲームの戦略にはいくつかの結論が使用されます。まず、ライトを押す順序は重要ではなく、結果は同じになります。^[5]次に、最小限のソリューションでは、各ライトを1回以上押す必要はありません。ライトを2回押すと、まったく押さないのと同じになるためです。^[5]

1998年、マーロウ・アンダーソンとトッド・フェイルは線型代数を用いて、すべての構成が解けるわけではないことを証明し、また、解ける5×5問題には冗長な動きを除いて、ちょうど4つの勝利シナリオが存在することを証明した。^[6]ライト・アウトの5×5グリッドは、25×1の列ベクトルとして表すことができ、1と0はそれぞれライトのオンとオフの状態を表す。各要素は、2を法とする整数体Z _{2の要素である。アンダーソンとフェイルは、構成が解けるためには（元の構成からヌルベクトルを導出する）、以下の2つのベクトルN 1}とN ₂に直交する必要があることを発見した（5×5配列として示されているが、行列と混同しないように）。

$${\displaystyle N_{1}={\begin{pmatrix}0&1&1&1&0\\1&0&1&0&1\\1&1&0&1&1\\1&0&1&0&1\\0&1&1&1&0\end{pmatrix}},N_{2}={\begin{pmatrix}1&0&1&0&1\\1&0&1&0&1\\0&0&0&0&0\\1&0&1&0&1\\1&0&1&0&1\end{pmatrix}}}$$

さらに、彼らはN ₁と N _{2 を}使って解から3つの追加解を見つけることができ、これら4つの解が、与えられた開始構成に対する唯一の4つの解（冗長な動きを除く）であることを発見した。これらの4つの解は、X、X + N ₁、X + N ₂、およびX + N ₁ + N ₂であり、Xは与えられた開始構成に対する解である。^[6]この方法の入門書は、ロバート・アイゼルによって出版された。^[7]

「ライトチェイシング」は、ガウス消去法に似た方法で、常にパズルを解くことができます（解が存在する場合）が、多くの冗長な手順が発生する可能性があります。^{[2] [6] [8]}このアプローチでは、一番上の行から始めて、行を 1 つずつ操作します。行内のすべてのライトを無効にするには、すぐ下の行の隣接するライトを切り替えます。次に、同じ方法を最後の行まで連続する行に適用します。最後の行は、アクティブなライトに応じて個別に解決されます。一番上の行の対応するライト（下の表を参照）を切り替え、最初のアルゴリズムを再度実行して、解決策を導きます。^[8]

他のボード サイズの表と戦略は、空のボードでLights Out をプレイし、特定のライトを上段から下段に移動させた結果を観察することによって生成されます。

一度単一の解法が見つかったら、累積効果のないボタン押下の冗長なセットを排除することで、最小の移動回数の解法を決定することができる。^{[6] [8]}

六角形などのさまざまなボード構成に対して解の存在が証明されており^[9]、 n≤200のn行n列のボードに対する解は明示的に構築されています^{[10] 。}

N×Nのケースごとに解が存在する。これは任意の無向グラフ上で解くことができ、1つの頂点をクリックするとその値とその近傍の値が反転する。より一般的には、アクション行列が対称であれば、その対角線は常に解くことができる。^[11]

• ベルレカンプのスイッチングゲーム
• ペグソリティア
• 群論

• クリーンオンライン版
• オンライン版
• 解決策の見つけ方、一般的な説明