• Create Account

### #ActualCornstalks

Posted 12 April 2013 - 10:09 AM

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

Minesweeper is NP-Complete, so you're not going to solve it with any polynomial time algorithm (assuming P != NP) (both A* and Dijkstra's are polynomial time algorithms, and as such are not powerful enough to solve this problem).

### #4Cornstalks

Posted 12 April 2013 - 10:09 AM

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

Minesweeper is NP-Complete, so you're not going to solve it with any polynomial time algorithm (assuming P != NP) (which A* and Dijkstra's both are).

### #3Cornstalks

Posted 12 April 2013 - 10:08 AM

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

Minesweeper is NP-Complete, so you're not going to solve it with any polinomial time algorithm (assuming P != NP) (which A* and Dijkstra's both are).

### #2Cornstalks

Posted 12 April 2013 - 10:04 AM

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

Are you sure, though, that a situation like this is realistic in minesweeper? Is there ever a time when you truly don't know which cell to pick next? You don't know which cell to select in the picture you posted because you edited the picture to remove information. I'm not sure exactly what the rules are in minesweeper when it comes to revealing cells in clusters, but from all the times I've played, I don't ever recall being in a situation where it was impossible to figure out which cell to pick next.

However, if you are in a situation like that, the answer is simple: just pick one. There's no guaranteed way to select a safe one. You might come up with a heuristic to help your guessing, but it won't be perfectly correct, and it's still not a graph search problem.

### #1Cornstalks

Posted 12 April 2013 - 10:01 AM

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search.

Are you sure, though, that a situation like this is realistic in minesweeper? Is there ever a time when you truly don't know which cell to pick next? You don't know which cell to select in the picture you posted because you edited the picture to remove information. I'm not sure exactly what the rules are in minesweeper when it comes to revealing cells in clusters, but from all the times I've played, I don't ever recall being in a situation where it was impossible to figure out which cell to pick next.

However, if you are in a situation like that, the answer is simple: just pick one. There's no guaranteed way to select a safe one. You might come up with a heuristic to help your guessing, but it won't be perfectly correct, and it's still not a graph search problem.

PARTNERS