Minesweeper の続き（複雑なケースにも対応）

他の人の答えを見てみたが、みなさん複雑なケースというのは考慮していないようだ。
一人で深読みしすぎたか・・・。まあ、せっかくなので作ってみる。

未開封セルの情報をリストアップ

まず、各セルごとに、以下の情報を調べて、リストアップしておく。

• 周囲の未開封セルの集合(set)
• 未発見の地雷数（＝セルの数字 - 発見済みの地雷数）

check_list = []  # list of (covered_cells, covered_mines)
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])
            check_list.append((covered_cells, covered_mines))

未開封セルをA,B,C...とすると、

• A,Bの1つが地雷 → ({A,B}, 1)
• A,B,Cの2つが地雷 → ({A,B,C}, 2)

というようにタプルを作り、check_listに追加する。実際には、A,B,C...は(x,y)の座標となる。

単純なケースをチェック

check_listを作成したら、単純なケースがないかチェックしていく。単純なケースとは、例えば、

• ({A}, 1) なら Aは地雷
• ({A,B}, 2) なら A,Bは地雷
• ({A,B}, 0) なら A,Bは安全

などで、

• 未発見の地雷数 == 0 なら、未開封セルは安全（地雷ではない）
• 未開封セルの数 == 未発見の地雷数 なら、未開封セルは地雷

と判断できる。

for covered_cells, covered_mines in check_list:
    pt = list(covered_cells)[0]
    if covered_mines == 0:
        return [False, pt[1], pt[0]]
    elif len(covered_cells) == covered_mines:
        return [True, pt[1], pt[0]]

ここまでは、前回のコードとほぼ同じ。

いよいよ複雑なケースに対応する

さて、ここからが本題。
次に、複数の情報から判断する複雑なケースを考える。例えば、

• ({A,B}, 1) と ({A,B,C}, 2) から、Cは地雷
• ({A,B}, 1) と ({A,B,C}, 1) から、Cは安全

などである。

先ほどのcheck_listの要素を組み合わせて、新たなcheck_listを作成する。
例えば、({A,B,C}, 2) と ({A,B}, 1) からは、({C}, 1) という新しい情報が得られる。

checked += check_list
check_list = []
for (cells1, mines1), (cells2, mines2) in itertools.permutations(checked, 2):
    if cells2 < cells1:
        new_cells = cells1 - cells2
        new_mines = mines1 - mines2
        if not any(cells == new_cells for cells, _ in checked + check_list):
            check_list.append((new_cells, new_mines))
covered_info += check_list

こうして、新たなcheck_listを作成したら、その中に、単純なケースがないかチェックする。

これをループで繰り返す。
一度では解けない問題でも、何度かループするうちに解けていく。
例えば、
[({A,B,C,D}, 2), ({A,B}, 1), ({C,D,E}, 1)]
から、新たに
({C,D}, 1)
という情報が得られる。これだけでは、まだ何も確定しないが、
[({A,B,C,D}, 2), ({A,B}, 1), ({C,D,E}, 1), ({C,D}, 1)]
から、新たに
({E}, 0)
が得られ、Eが安全だと確定する。

新しい情報が得られなくなったら、クリア不可。つまり、運試し問題だったということになる。

まとめ

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]

    if get((0, 0)) == -1:
        return [False, 0, 0]

    check_list = []  # list of (covered_cells, covered_mines)
    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}  # set
            if len(covered_cells) > 0:
                covered_mines = n - len([p for p in get_around_cells(pt) if get(p) == 9])
                check_list.append((covered_cells, covered_mines))

    checked = []
    while len(check_list) > 0:
        # Simple cases:
        # ({A}, 1)   -> A = mine
        # ({A,B}, 2) -> A = B = mine
        # ({A,B}, 0) -> A = B = safe
        for covered_cells, covered_mines in check_list:
            pt = list(covered_cells)[0]
            if covered_mines == 0:
                return [False, pt[1], pt[0]]
            elif len(covered_cells) == covered_mines:
                return [True, pt[1], pt[0]]
        checked += check_list

        # Complex cases:
        # ({A,B,C}, 2) and ({A,B}, 1) -> ({C}, 1)
        # ({A,B,C}, 1) and ({A,B}, 1) -> ({C}, 0)
        check_list = []
        for (cells1, mines1), (cells2, mines2) in itertools.permutations(checked, 2):
            if cells2 < cells1:
                new_cells = cells1 - cells2
                new_mines = mines1 - mines2
                if not any(cells == new_cells for cells, _ in checked + check_list):
                    check_list.append((new_cells, new_mines))

    raise Exception('I give up.')  # or click randomly

英語苦手なので、できるだけ英語を使わないようにコメントを付けてみた。意味が伝わるかな？