CODEWITHSUNDEEP
graphartificial-intelligencea-star2d-games
user216799
user216799

Reputation: 111

A* algorithm and games

I am trying to implement minesweeper solver in lisp. I know this is not rare problem but i didn't find any article that can help me with that. At start i have a minefield as input with numbers on uncovered fields. Algorithm should be finished when all mines are found. So, in every step i have to check what fields i can put in my list of mined fields and to choose one field from my list of not mined fields and open it. Later i will check is my list of mined fields completed and if yes algorithm is done. I would appreciate any help. I don't ask for source code, but i need good ideas. I am not experienced with this kind of problems.

I HAVE to use A* algorithm. And i don't need to open all unopened fields...I need to find positions of all mined fields. And of course it has to be the SHORTEST path to do that. When i find positions of all mined fields algorithm is finished. So, once more, i need to find all mined fields with optimal number of opened fields. And of course i need a heuristic for my algorithm which will help to choose one of all safe unopened fields. And that list of safe unopened fields needs to be determined after every opening. So i need to call main function, that function will check did i find all mined fields, if not, then all safe adjacent unopened fields needs to be added to list of paths. And a path with best heuristic will be chosen

Upvotes: 2

Views: 829

Answers (2)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

You do not need the A* algorithm; its purpose is to find the shortest path in a graph (such as the shortest path between two places in a map, or the smallest amount of moves that will solve a puzzle). You will probably want to use a technique that is known as backtracking.

As long as there are unopened fields, pick an unopened field that is next to an open field, and tentatively flag it as a mine. Then, look at an unopened field that is adjacent to the previous one as well as to an opened field, and flag that one as a mine too, if this doesn't contradict the adjacent numbers - if it does, flag it as safe instead. Continue. Eventually, you will have looked at all unopened fields that surround the current area and have found one possible way of flagging the fields as safe or unsafe. However, this was based on several guesses, so now you need to go back to the last field where you made a guess and then make the opposite guess and then move forwards again to get another possible flag combination. Then, go even further back, revise your guesses, and so on. This can be implemented quite neatly with recursion. Eventually, you will have a collection of possible flag combinations. If you can find a field that is safe in all possible flag combinations, open that field. Otherwise, pick a field that is safe in as many flag combinations as possible.

Upvotes: 0

Sulthan
Sulthan

Reputation: 130102

I did implement a minesweeper solver in my first year at the University so I can give you some tips. (This is not using A* algorithm)

  1. Important - Not all positions are solvable.

  2. Backtracking of the whole mine field is a bit complicated for advanced difficulties (complicated=takes some time, consider all the possibilites to place 100 mines in a 30x30 field).

  3. You can solve everything locally, in the same way a human solves the minesweeper. The potential of this is to give the users a hint how to continue instead of solving everything.

Example:

  1. Have a separate mine field where you do the solving
  2. Find all the unsolved cells that have a solved (number/ known mine) cell close enough (2 cell distance)
  3. For every such cell, take a 5x5 neighborhood with the cell in the center, find every possibility (backtracking) and check if the possibilites have something in common (mines/non-mines), if yes, you can check the mines and uncover the non-mines.
  4. Repeat while you can uncover something.
  5. When you cannot uncover anything and the number of remaining mines is small enough, you can try backtracking over the whole field.

I hope I remember it correctly, I did some proofs why the 5x5 area is enough to check but it was almost 10 years ago.

Upvotes: 3

Related Questions