in Education by
I have implemented in Python an algorithm for solving the game 'Minesweeper'. The program works as follows: Say that the solver clicks a square named 'a'. For sake of example let the number thus revealed equal 2. The neighbors of the square which are as yet unclicked are (again by way of example) named 'b' and 'c'. The program then associates the square with the expression [2, {'b', 'c'}], and strips 'a' from all other expressions. The deduction of which squares are mines and which are not proceeds by pairwise simplification of such expressions under two circumstances. If the squares in one expression are a subset of the squares of the other expression: [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}] If all the squares in one expression are established to be mines: [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}] Then, for some expression X, if X[0] == 0, we are free to click all squares named in X[1], and if X[0] == len(X[1]), then we can flag them. I am, however, struggling to identify which pairs of expressions to attempt to simplify. My current approach is to maintain a stack of squares; whenever a square is clicked or has its expression successfully simplified, it is added to the stack (if it is not already there). When a square is popped from the stack, simplification is attempted between its expression (X), and any other expressions such that X[1] & Y[1] != set(). The algorithm terminates when the stack is depleted. Currently, however, though this works quite well, it is not capable of correctly solving all unambiguous configurations, and how well it performs on a given board changes significantly if I replace the stack with a queue, or use some algorithm to determine which square to pop! I would be very much appreciative of any examples of precedent to my approach, or avenues of potential exploration. Select the correct answer from above options

1 Answer

0 votes
by
 
Best answer
Your approach can "solve" a condition if it is completely full or empty of mines, or if it is a subset of another condition. However, there are some deductions that this won't handle. Your conditions will be: [2, {a, b, c, d}], [1, {c, d, e}], [2, {d, e, f}], [1, {e, f, g}], [2, {f, g, h, i}] Your algorithm can't make any deductions about this. However, if you're an experienced Minesweeper player, you'll recognize that the 1 2 1 pattern in the center has only a single solution, with mines below the 1s: a 2 1 2 1 2 i b 2 * 2 * 2 h There are still some unknowns, with mine under a or b and another under ‘h’ or ’i’, but if this was part of a larger puzzle you might be able to figure those out later on (or you may have to guess). I believe my set of mines approach worked like this: For each tile that has been expanded, collect one set of all its unexpanded neighbors (the "area"), and a list containing all the sets of mines that could occur in that area. So for instance, the 5 known tiles in the example above would generate (from left to right): ({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}]) ({c, d, e}, [{c}, {d}, {e}]) ({d, e, f}, [{d, e}, {d, f}, {e, f}]) ({e, f, g}, [{e}, {f}, {g}]) ({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}]) Anyway, to combine two conditions I'd first check that they were overlapping, by intersecting the area sets. If there was no overlap, the conditions can't be usefully combined. I have implemented the following code in python, and it does not get terminated while the stack is depleted. import stdio import stdarray import sys import random # Accept integers m and n, and float p as command-line arguments. # Create a m x n minesweeper game where each cell is a bomb with # probability p. Write the m x n game and the neighboring bomb counts # to standard output. m = int(sys.argv[1]) n = int(sys.argv[2]) p = float(sys.argv[3]) # Create bombs as a m+2 * n+2 array. bombs = stdarray.create2D(m+2, n+2, False) # bombs is [1..m][1..n]; the border is used to handle boundary cases. for r in range(1, m+1): for c in range(1, n+1): bombs[r][c] = (random.random() < p) # Write the bombs. for r in range(1, m+1): for c in range(1, n+1): if bombs[r][c]: stdio.write('* ') else: stdio.write('. ') stdio.writeln() # Create solution as m+2*n+2 array. solution = stdarray.create2D(m+2, n+2, 0) # solution[i][j] is the number of bombs adjacent to cell (i, j). for r in range(1, m+1): for c in range(1, n+1): # (rr, cc) indexes neighboring cells. for rr in range(r-1, r+2): for cc in range(c-1, c+2): if bombs[rr][cc]: solution[r][c] += 1 # Write solution. stdio.writeln() for r in range(1, m+1): for c in range(1, n+1): if bombs[r][c]: stdio.write('* ') else: stdio.write(str(solution[r][c]) + ' ') stdio.writeln() If you want to make your career in Artificial Intelligence then go through this video:

Related questions

0 votes
    I'm working through my AI textbook I got and I've come to the last homework problem for my section: "Implement the ... in C# or Java? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    It always amazed me how the Akinator app could guess a character by asking just several questions. So I wonder ... more about them? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    I am searching for information on algorithms to process text sentences or to follow a structure when creating sentences ... be great. Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    I am learning programming (Python and algorithms) and was trying to work on a project that I find interesting. ... is impossible). Select the correct answer from above options...
asked Feb 2, 2022 in Education by JackTerrance
0 votes
    I am a little confused about the Hill Climbing algorithm. I want to "run" the algorithm until I found the ... question is too simple. Select the correct answer from above options...
asked Jan 30, 2022 in Education by JackTerrance
0 votes
    From what I've read so far they seem very similar. Differential evolution uses floating point numbers instead, and ... of both. Select the correct answer from above options...
asked Jan 30, 2022 in Education by JackTerrance
0 votes
    I'm looking for a decent implementation of the OPTICS algorithm in Python. I will use it to form density-based ... to that cluster. Select the correct answer from above options...
asked Jan 28, 2022 in Education by JackTerrance
0 votes
    I try to learn and implement a simple genetic algorithm library for my project. At this time, evolution, ... Gaussian distribution?.) Select the correct answer from above options...
asked Jan 26, 2022 in Education by JackTerrance
0 votes
    I'm trying to solve the Travelling Salesman Problem (TSP) with a Genetic algorithm. My genome is a permutation of ... problem in C#? Select the correct answer from above options...
asked Jan 26, 2022 in Education by JackTerrance
0 votes
    I'm trying to read an image from electrocardiography and detect each one of the main waves in it (P wave, QRS ... some ideas? Thanks! Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    In the MNIST beginner tutorial, there is the statement accuracy = tf.reduce_mean(tf.cast(correct_prediction, "float")) tf ... (x,1)? Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I know the basics of feedforward neural networks, and how to train them using the backpropagation algorithm, but I'm ... , even better. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I am looking for an open source neural network library. So far, I have looked at FANN, WEKA, and OpenNN. Are the ... , and ease of use. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    Suppose I have a Tensorflow tensor. How do I get the dimensions (shape) of the tensor as integer values? I ... 'Dimension' instead. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I'm hoping to use either Haskell or OCaml on a new project because R is too slow. I need to be able to ... in either Haskell or OCaml? Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
...