記事タイトルが長すぎる．
はじめに
みなさんは，ボタンを押すとそのボタンと周囲4近傍のボタンの ON/OFF が反転して，全てのボタンを ON にすればクリアのパズルゲーム(5x5はライツアウトと言うらしい)をやったことがありますか？ 私はああいったパズルが苦手で，なかなか解くことができません．
したがって，機械に頼ることになります．
ソースコード
解説
場の状態は，下の表の対応するビット(下から数えたビットの位置，1-index)が立っているかどうかで表されています．
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 9 | 8 | 7 |
| 1 | 6 | 5 | 4 |
| 2 | 3 | 2 | 1 |
したがって，例えば 0b010001110 は，次のような場の状態を表しています．
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | OFF | ON | OFF |
| 1 | OFF | OFF | ON |
| 2 | ON | ON | OFF |
ボタンを押すと ON/OFF が反転する，という操作は排他的論理和によって表されるので，これによって次に遷移するべき状態を網羅することができます． そして，場の状態を頂点，ボタンの押し方を辺とすると，これは初期状態から目的状態への最短経路問題を解くことに帰着されます．
start と goal を適宜変更して実行すると，最短手数とその解き方が表示されます．
解の存在性
さて，全ての問題(初期状態と目的状態の組)に対して解が存在するのか，という疑問が生じてきます．
まず，初期状態として 0b000000000 を考えることにします．
次に，目的状態として 0b100000000 と 0b010000000 と 0b000010000 の3つの状態を考えます．
それぞれ，「左上のみON」「真ん中上のみON」「真ん中のみON」を表しています．
この3つの組に対して，上記のプログラムに入力として与えて(goal を書き換えて)実行したところ，結果は以下の通りになりました．
0b000000000 → 0b100000000
5 0,0 2,0 2,1 0,2 1,2
0b000000000 → 0b010000000
4 1,1 0,2 1,2 2,2
0b000000000 → 0b000010000
5 1,2 2,1 1,1 1,0 0,1
どうやらこの3つの組に対しては解が存在します． そして，「全てのボタンがOFFの状態から始めて，9つのボタンのうちどれか1つだけをONにする」という場合は，先述した3つの操作をそれぞれ線対称/(1,1)に対して90度回転，などしてやれば網羅することができます．
これらの解は，どれも「最終的には，目的とするボタン以外のボタンのON/OFFは変化させずに，目的のボタンのみをONにする」という操作になっています．
さらに，あらゆる初期状態とあらゆる目的状態に対して，いま生成された9つの操作を組み合せて所望の状態にし，奇数回行った操作は1回分だけ残し，偶数回行った操作は除外してやれば，最短解を生成することができます．
こうして，全ての組合せに対して最短解が存在することが分かりました．
5x5 の場合
5x5 の場合は実装していないのですが，興味深い考察をしているサイトがありました．
場合によっては解が存在せず，パズルの解の存在条件は連立合同方程式を解くことによって導出することができる，とのことです．
おまけ
ボタン(略)ゲームの体感ができるページをだいぶ前に作ってました．
初期状態を与えることができない仕様になっている……．
