CODEWITHSUNDEEP
pythonalgorithmgridpath-findingpuzzle
Linus
Linus

Reputation: 55

Slide Puzzle Solver Using Python

I'm making a Sliding Puzzle Game in python but with multiple empty squares, for example:

                            (solution)
[9] [1] [ ] [7]             [1] [2] [3] [4]
[ ] [3] [5] [ ]      ->     [5] [6] [7] [8]
[8] [4] [ ] [6]             [9] [ ] [ ] [ ]
[ ] [ ] [2] [ ]             [ ] [ ] [ ] [ ]

In each iteration you can move as many pieces as you want, one square, as long as there is an available square. For example:

                            (after one iteration)
[9] [1] [ ] [7]             [1] [ ] [7] [ ]
[ ] [3] [5] [ ]      ->     [9] [3] [5] [ ]
[8] [4] [ ] [6]             [ ] [8] [4] [6]
[ ] [ ] [2] [ ]             [ ] [2] [ ] [ ]

The goal is to find a general solution for any problem of this kind, with as few iterations as possible.

My curent method of solving this problem is pretty slow (a lot of iterations) in my opinion, so I would love to see someone else take a look at the problem.

Thanks in advance.

Upvotes: 0

Views: 1464

Answers (1)

joaopfg
joaopfg

Reputation: 1287

Here is an algorithm to solve this problem.

Let's define a function f that takes as input a state of the board and gives as output the minimum number of iterations to solve it for this state.

You want to evaluate f on the board that you have.

For the first iteration, you have some choices. For each of this choices, you will have a new set of choices for the second iteration, and so on.

However, notice that the graph of choices is not a tree. Making a certain set of choices can led to the same state as making another set of choices. So, sub problems overlap. This implies that you can use a dynamic programming approach (reusing solutions that were already evaluated for a sub problem). But you need to be careful with situations that cause infinite loop. It happens whenever you see a state that was already saw but is not yet evaluated. You can prune the graph at these nodes (just ignore them).

If this procedure ends without finding a solution, it's because there is no solution. If there is a solution, it will find it.

Let me know if you have difficult to implement this algorithm. I can add some code when I have time.

Upvotes: 1

Related Questions