Two rules clear solution for Minesweeper by nickie - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Two rules solution in Clear category for Minesweeper by nickie

adjacent = [(-1, -1), (-1, 0), (-1, 1),
            ( 0, -1),           (0, 1),
            ( 1, -1),  (1, 0),  (1, 1)]

def checkio(field):
    # Look for a cell that is safe to play
    n, m = len(field), len(field[0])
    for i in range(n):
        for j in range(m):
            # Consider all uncovered cells that are not mines
            if 0 <= field[i][j] < 9:
                # Find all surrounding cells with their values
                neighbors = [(i+di, j+dj, field[i+di][j+dj])
                             for (di, dj) in adjacent
                             if 0 <= i+di < n and 0 <= j+dj < m]
                # Find the unknown surrounding cells, continue if none
                unknown = [t for t in neighbors if t[2] < 0]
                if not unknown: continue
                # Find how many surrounding cells contain mines
                mines = sum(1 for t in neighbors if t[2] == 9)
                # Case #1: all unknown surrounding cells are empty
                if field[i][j] == mines:
                    return (False, unknown[0][0], unknown[0][1])
                # Case #2: all unknown surrounding cells contain mines
                elif field[i][j] == len(unknown) + mines:
                    return (True, unknown[0][0], unknown[0][1])
    # If no safe cell could be found, try the upper left
    if field[0][0] < 0:
        return (False, 0, 0)

if __name__ == '__main__':
    #These are just examples
    checkio([
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    ])  # [False, 0, 0]
    checkio([
        [0, 2, -1, -1, -1, -1, -1, -1, -1, -1],
        [0, 2, -1, -1, -1, -1, -1, -1, -1, -1],
        [0, 1, 1, 1, -1, -1, -1, -1, -1, -1],
        [0, 0, 0, 1, -1, -1, -1, -1, -1, -1],
        [0, 1, 1, 2, -1, -1, -1, -1, -1, -1],
        [0, 1, -1, -1, -1, -1, -1, -1, -1, -1],
        [0, 1, -1, -1, -1, -1, -1, -1, -1, -1],
        [2, 1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    ])  # [True, 0, 2]

Jan. 24, 2014

Comments:

nickie on Jan. 25, 2014, 2:26 a.m.
For anyone interested in an explanation of this solution, see <a href="http://www.checkio.org/mission/minesweeper/publications/Juge_Ti/python-3/first/#comment-outer-8654">my comment</a> in Juge_Ti's similar solution. I'm adding some code (Python 3) that could be useful if you want to test your solutions. <h4>Simulation</h4> Parameters: "plain" is the mine field, containing just 0=empty or 1=mine (no counting!); "flood" determines whether uncovering a zero will automatically uncover all neighboring cells; "show" determines whether the steps of the simulation will be printed. The result is the mine field (with counting) or None, if simulation failed. <pre class='brush: python'>def play(plain, flood=True, show=True): n, m = len(plain), len(plain[0]) ns = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] def num(i, j): return 9 if plain[i][j] == 1 \ else sum(1 for (di, dj) in ns if 0 <= i+di < n and 0 <= j+dj < m and plain[i+di][j+dj]) field = [[-1 for c in row] for row in plain] real = [[num(i, j) for j in range(m)] for i in range(n)] while min(map(min, field)) == -1: if show: for row in field: for c in row: print("{0:3d}".format(c), end="") print() result = checkio(field) if result == None: return None (verdict, i, j) = result if show: print(">", (verdict, i, j), end="\n") assert(field[i][j] == -1) assert(verdict == (real[i][j] == 9)) if not flood: field[i][j] = real[i][j] else: q = [(i, j)] while q: i, j = q.pop() if field[i][j] != -1: continue field[i][j] = real[i][j] if field[i][j] != 0: continue for di, dj in ns: if 0 <= i+di < n and 0 <= j+dj < m: q.append((i+di, j+dj)) assert(field == real) return field </pre> <h4>Generation</h4> Parameters: "n" and "m" are the mine field's dimensions; "p" is the probability that a cell contains a mine (a real between 0 and 1). The result is the mine field (with 0=empty, 1=mine). By "deterministic" I mean mine fields that do not need "guessing" (according to a given solution). <pre class='brush: python'># Random generator for mine fields from random import random def gen(n, m, p): plain = [[int(random() < p) for j in range(m)] for i in range(n)] plain[0][0] = 0 return plain # Generator of "deterministic" mine fields def gendet(n, m, p): while True: plain = gen(n, m, p) field = play(plain, True, False) if field != None: return field </pre>

Lasica on April 26, 2014, 9:52 p.m.
It's as clear as you can get :) Great solution. I finally found a way to describe adjacent table with python: <pre class='brush: python'>adjacent = set(itertools.combinations([1,-1,0,1,-1],2)) </pre> What do you think?

vinc on Sept. 1, 2014, 7:07 a.m.
<pre class='brush: python'>if 0 <= field[i][j] < 9: </pre> I think there is no need to check empty cells: field[i][j] == 0. You waste your time;) They have never got 'unknown' surrounding cells.

Sim0000 on July 14, 2018, 4:58 a.m.
Clear solution!

U.V on March 1, 2023, 6:21 p.m.
In my mind <pre class='brush: python'>mines = sum(t[2]==9 for t in neighbors) </pre> looks better and clearer than <pre class='brush: python'>mines = sum(1 for t in neighbors if t[2] == 9) </pre>

The Game is Worth it!

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.