パズル問題解法のアルゴリズム講座
入門編
多重ループ検索
１．巨大な多重ループでパターンを生成
このパズルの重要な法則「押す順番は関係ない」ということから、前に述べたように「５×５＝２５個」のボタンをそれぞれ押すか押さないかの２通りからの選択なので｢２の２５乗＝３３，５５４，４３２通り｣の
パターンを調べることになりますが、
| １ | ２ | ３ | ４ | ５ |
| ６ | ７ | ８ | ９ | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 |
(１) ボタンの押す押さないを決めていく順番を右図とする。
(２) その順番通りにボタンの名前(変数名)をａ〜ｙとする。
(３) 変数の値は、押す場合を１，押さない場合を０とする。
とすると、次のようなプログラムが書けます。
/* 全てのパターンを生成する */
for (a=0; a < 2; a++)
for (b=0; b < 2; b++)
for (c=0; c < 2; c++)
for (d=0; d < 2; d++)
for (e=0; e < 2; e++)
(途中略)
for (x=0; x < 2; x++)
for (y=0; y < 2; y++) {
生成されたパターン通りにボタンを押す;
/* 結果の確認 */
if (全てのライトが消えていたら)
このパターンを記録する;
今のパターンでのボタン押しを元に戻す;
}
以上のような25重のfor文のループで全パターンを生成して解を求めることが出来ます。不明な物の個数分だけ、for文を重ねて記述すればよいのです。
簡単なパズル問題なら大抵はこの方法で解を出すことが出来ます。(アルゴリズムの基本)
２．ところで、もっとうまい方法はないか？
しかし、この方法だと前の実験の通り探索を終えるのに約30秒もかかってしまいます。結論から先に言うと「ライツアウト」の探索は、33,554,432通りも調べる必要はありません。
それどころか、「たったの３２通り」を調べるだけでよいのです。理由は簡単です。
| １ | ２ | ３ | ４ | ５ |
| ６ | ||||
| 25 |
(２) 最上段の５個のボタンの押すパターンを生成する。(２の５乗＝３２通り)
(３) ２段目以降については、すぐ上の位置のライトの状態で選択の余地なく決定される。
何故なら、右図の「６」の位置において、もし「１」の位置のライトがついていたら、
今それを消しておかないと、もう「１」のライトを消すことが出来なくなります。
逆に、もし「１」の位置のライトが消えていたら、今「６」を押して「１」をつけて
しまうと、もう「１」のライトを消すことが出来なくなります。
この現象が結局、最後の「25」まで続いてしまうのです。
(４) そして、最下段の５個のライトが総て消えていれば、それが解となります。
正式公開版の「ライツアウト」が瞬時に解を出す秘密はこれです。たった３２通りを調べているだけなのです。
（追記）ここで説明したアルゴリズムよりも、もっと面白い方法でライツアウトを解く方法があります。→ここ