実践練習のまとめ?

問題 1060 †

２年前の世界大会(ICPC2003 World Final )でも 実は類題(Problem B Light Bulbs)が出題されている。

問題概説 †

４ｘ４のオセロ板が与えられていて、各マスには白または黒のオセロの駒が配置されている。空白のマスは無い。この状態であるマスを選択すると、そのマスおよび上下左右の５マスを同時にひっくり返すことができる。

与えられた盤面状態から最短手数で盤面を白一色または黒一色にできるなら手数を表示せよ。不可能なら Impossible と表示せよ。

解法 †

同じマスを二回選択することには意味がないことに気づくのが第一ステップ。 一つのマスを選択するということはその上下左右および自身のマスに対して xor 演算を適用すると考えれば各マスは最大１回しか選択する必要はない。

2^16 の探索にも見えるが実は 2^4 のループで済む。上の４つを確定すれば残りの１２マスは自動的に確定することに注意すると上の４つを２＾４全探索するのが割と簡単である。

とここまで解説してはみたが、2^16 は小さいのでこの問題は 全探索がコード記述量から言ってベストと考えられる。 2^(6*6) ぐらいになると上のアルゴリズムでないと動かない。

その他 †

このパズルはライツアウトと呼ばれている。 XOR演算は線形性を持っているので実はこの問題は連立一次方程式で解くことができる。 肝心の連立一次方程式で解く方法は冗長で読みにくいが http://www.ic-net.or.jp/home/takaken/nt/light/light2.html を参照されたし。

余談だが、この問題を選定したスタッフは、この問題を６〜７年前くらいに 解くプログラムを書いたことがある。 6x6 以降の大きな盤面において、真っ白を真っ黒にするためのパターンを 求めると美しいパターンが現れて感動していた。 かなり大きな盤面でも盤面のサイズによっては解が１通りしか 無かったりするのがかなり不思議だった。 Pentium 60MHz のマシンで 15x15 位までは普通に計算できた記憶がある。