Minesweeper (Electronic Station) - マインスイーパー
どんな問題？
Minesweeper
http://www.checkio.org/mission/minesweeper/
マインスイーパーのゲームをクリアせよ。
- フィールドは10x10の固定とする。
- 左上 (0,0) には地雷は無い。
今回の問題は、いままでと少し違っていて、checkio()関数が何度も繰り返し呼ばれる。
chekio()の引数としてフィールド状態を受け取るので、次にどのセルを開くか（または、どのセルが地雷か）を戻り値として返す。すると、テストルーチンが、指定したセルをクリックする。地雷が爆発したらゲームオーバー。セーフなら、クリック後のフィールド状態を引数として、再度checkio()関数が呼び出される。これを繰り返して、地雷を爆発させずに、すべての安全なセルを開くか、すべての地雷をマークすればクリアとなる。
フィールドは10x10の固定サイズで、-1がまだ未開封のセル、0～8は数字（周囲の地雷数）、9はマークされた地雷となる。セルはfield[i][j]で指定する。戻り値で、開くセルを指定する場合は、[False, i, j]、地雷をマークする場合は、[True, i, j] とする。
ちなみに、数字0の場合、テストルーチン側が周囲の未開封セルを自動的に開いてくれるので、自分で数字0の周囲を開ける必要はない。
どうやって解く？
最初は、何から手を付ければいいかさっぱりだったが、マインスイーパーの基本ルールに返ってみる。
単純なケース
- 数字が1のとき、周辺に地雷が0個、未開封セルが1個 →未開封セルは地雷
- 数字が2のとき、周辺に地雷が1個、未開封セルが1個 →未開封セルは地雷
- 数字が3のとき、周辺に地雷が1個、未開封セルが2個 →未開封セルは2個とも地雷
「数字－周辺の地雷数」が未発見の地雷数となるので、未発見の地雷数と未開封セルの数が等しければ、未開封セルはすべて地雷ということがわかる。
- 数字が1のとき、周辺に地雷が1個、未開封セルが1個 →未開封セルは安全
- 数字が2のとき、周辺に地雷が2個、未開封セルが1個 →未開封セルは安全
未発見の地雷数が0なら、未開封セルは安全（地雷ではない）とわかる。
まあ、ここまでは単純に数字セル1個だけを見てわかるケースだ。
より複雑なケース
ところが、マインスイーパーでは、複数の数字セルを見ないと解けないケースがある。例えば、
０１□ ０２□ ０１□
このような場合だ。□が未開封セルで、上からA,B,Cと呼ぶことにする。
- 上の数字1から、A,Bの1つが地雷 …条件(1)
- 中の数字2から、A,B,Cの2つが地雷 …条件(2)
- 下の数字1から、B,Cの1つが地雷 …条件(3)
一つ一つの条件からは何も確定できない。しかし、条件(1)と(2)を同時に満たすためにはCが地雷と確定できる。すると条件(3)からBがセーフだと確定でき、条件(1)からAが地雷だと確定できる。
このように複数の条件から判断しないといけないケースがやっかいだ。
まずは単純なケースを解く
とりあえず、最初は単純なケースだけ考えてみる。
def checkio(field): def get(p): return field[p[1]][p[0]] def all_cells(): h = len(field) w = len(field[0]) return [(x, y) for y in range(h) for x in range(w)] def get_around_cells(center): return [p for p in all_cells() if p != center and abs(center[1] - p[1]) <= 1 and abs(center[0] - p[0]) <= 1] for pt in all_cells(): n = get(pt) if 0 <= n <= 8: covered_cells = [p for p in get_around_cells(pt) if get(p) == -1] # 未開封のセル if len(covered_cells) > 0: covered_mines = n - len([p for p in get_around_cells(pt) if get(p) == 9]) # 未発見の地雷数 cell = covered_cells[0] # 未開封のセルの１つ if len(covered_cells) == covered_mines: return [True, cell[1], cell[0]] elif covered_mines == 0: return [False, cell[1], cell[0]] return [False, 0, 0]
get_around_cells()がわかりにくいかもしれないが、centerの周辺8マス（centerは含まない）の座標を返している。
周辺の未開封セルをリストアップして、未発見の地雷数と比較している。数字が0のときにも、未開封セルがあれば開くようにしておいた。
ここまではいいんだよな。とりあえず、Run & Check
Task solved! クリア～
って、ちょっと待てーい。
これ、まだ単純なケースしか想定してないんだぞ。
だいたい、テストは3パターンだけなの？しかも、エディタにあらかじめ書いてあるSimple,Gate,Various と同じ内容。これでクリアって言われても、納得できんぞー！！！
このコードで解けない問題なんていっぱいあるはず。例えば、、、どんなんだろ？ちょっといろんな問題を作って試してみる。
と、その前に、ブラウザ上のエディタでは何かと不便なので、ここからは自分のPC上のPythonでテストしている。
ランダムに問題を作ってみる
問題を作成するには、地雷原を定義して、check_solution()に渡せばよい。地雷原は10x10のfieldで定義する。0が安全、1が地雷となる。
import random def make_random_field(mine_percent=20): field = [[int(random.randint(0, 99) < mine_percent) for x in range(10)] for y in range(10)] field[0][0] = field[1][0] = field[0][1] = field[1][1] = 0 return field
これで、ランダムな地雷原を作成できる。左上(0,0)はもちろん、(1,0)(1,1)(0,1)に地雷があっても、運試し問題になるので、左上4ヶ所に地雷は無いようにした。もちろん、解いていくと、運試し問題だったということはありえる。ちなみに、運試し問題とは、
１□□ □□□ □□□
こんなふうに、安全にクリックできる場所がないケースだ。
作った問題を試すには、
assert check_solution(checkio, make_random_field()), "random"
と書いて実行する。
フィールドを表示（デバッグ用）
解いてる過程が見えないので、もうちょっと見やすくしてみた。
def show_field(field): s = '０１２３４５６７８●□' print('\n'.join(''.join(s[num] for num in line) for line in field) + '\n')
checkio()内で、show_field(field) とすれば、下記のように表示される。●が地雷、□は未開封セルだ。
００００００００００ ０１１２１１１１１０ ０１●□□□□□１０ ０２□□□２１１１０ ０１□□□１００００ ０１□□□１００００ ０１□□□１１１１０ ０１□□□□□□１０ ０１１２１１１１１０ ００００００００００
解けない問題を発見
あれこれ試して、先ほどの私のコードでは解けない問題がいくつも見つかった。
追加テストとして載せておく。
assert check_solution(checkio, [ [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]), "additional test 1" assert check_solution(checkio, [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]]), "additional test 2"
先ほどの私の書いたコードでは、additional test 1の場合、
０１１２□□□□□□ ０１●３□□□□□□ ０１２□□□□□□□ ００１□□□□□□□ １２１□□□□□□□ □□□□□□□□□□ □□□□□□□□□□ □□□□□□□□□□ □□□□□□□□□□ □□□□□□□□□□
ここで止まってしまう。しかし、□(2,5)は地雷、□(3,4)はセーフだと確定できるはずだ。
なぜ、□(2,5)が地雷だと確定できるかというと、
００１ １２１ □□□ ↑↑↑ ＡＢＣ
未開封セルを左からA,B,Cとすると、A,Bのうち1つが地雷、A,B,Cのうち2つが地雷、つまりCが地雷となるのだ。
さて、こういった複雑なケースでもクリアできるようなコードを書いてみよう。
