Hey,
I am pretty sure most of you know about the minesweeper game. I wanted to code (in C#) my own minesweeper game and was looking for some input as to what would be a good algorithm for that game. I have been browsing over the web for quite some time now but could not find a good solution. Can anyone help me with it?
Thanks
Have you seen this C# implementation of the game? The source code is downloadable, and the object model is explained.
The comments are that you don't need an algorithm to build the game. I believe you mean an algorithm in the sense of solving and everyone might be understanding it that way as well.
However any solution to a problem can be considered an algorithm.
Like most math problems you can dissect the whole algorithm into smaller less complex algorithms, until you get down to something small enough to solve. This will get you the first correct solution. Later you can optimize the smaller algorithms in the context of the whole algorithm.
The gameboard can be thought of as a 2 dimensional array. You will have an algorithm associated with each operation. The first operation would probably be a randomly generated set of mine locations with x, y coordinates with a parameter of the number of mines and size of board. You would have another algorithm associated with revealing a square, which takes the board and a location and determines how many mines are adjacent to it. The final algorithm would take the board and check if any squares without mines are left to reveal.
Now you can take each of these algorithms and attempt to optimize each of them for better performance and say "what's the best way to count the squares with mines adjacent to a current square, given a 2 dimensional array using x,y coordinates.
I'm definitely not a minesweeper expert, but here's the algorithm I use when I try to solve it:
Go over all the squares that are the border of the revealed area. For each of these squares, count the number of mines you have revealed next to it. subtract the number that is written in the square (the true number of mines that are around it). That is the number of unrevealed mines left around this square. Divide that by the number of unrevealed squares around the current square. That is the probability of each of the adjacent square containing a mine. If any square has a probability of 1, you mark it as a mine. If any square has a probability of 0 you mark it as safe. Then you update the relevant numbers.
What do you do if no square has probability 0 or 1? An optimal algorithm would take into consideration constraints from multiple squares. But as a I wrote in the begining, I'm not a minesweeper expert, so I choose randomly from the other squares that has probability closest to 0 or to 1.
"Algorithm" is just a fancy word for automating something which makes sense. If you know how to play (and win) minesweeper, you will also be able to write an algorithm for it. Good luck! :)
I just want to add the following if you try to write a solver - Minesweeper is NP complete. That means until someone proves P = NP it might be possible that you can do nothing better then performing a brute force search in some situations (but maybe the game it is not NP complete for small fields).
Check this: http://quantum-p.livejournal.com/19616.html
Any position on the board, that cant be solved intuitively with the monkey-reasoning is a matrix that could be able to solve some individual(or the whole position) squares which can lead to better solving rates. Simple random guessing didn't produce good results. I implemented this method into my solving algorithm in C++ by adding a linear system of equations-solver. I am researching the difficulcy of Minesweeper by running tens of thousands games through the algorithm and doing statistics.
My algorithm solves upto 85% of (9,9,10) easy level minesweepers. I haven't yet ran complete tests on other difficulcy levels, but smaller tests suggest that medium level (16,16,40) has a solving rate of 55-60 % and Hard level(30,16,99) as low as 5-10%. I am going to add a few new things that would make it most optimal.