How to begin coding a brain for a 8-puzzle game to calculate least moves

Question

I managed to solve this problem with a brute force with RNG it takes around 4-5 seconds to find the best solution even though the working grid is a 3x3.

I want to know how do I make it possible to generate the same moves the brute force finds without the brute force.

I'll list 2 examples and the solutions brute force found. I tried to analyze the solutions to figure out why it picked them and I can't figure anything out.

This game works by using cyclic rotation in both directions (left to right) and (right to left)

Left to right cyclic rotation does this
If [a, b, c] then [b, c, a]
Right to left cyclic rotation does this
If [a, b, c] then [c, a, b]

Game Data lets say is this (it can be any permutation of 1 to 9)
For example
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

I can move the pieces on the table in 8 different ways.
1) Cyclic Rotation (Left To Right) based on Row.
2) Cyclic Rotation (Right to Left) based on Row.
3) Top To Bottom based on Column.
4) Bottom To Top based on Column.
Now 5 to 8 don't require Column or Row since they are set diagonally.
5) Top Left To Bottom Right (Left To Right).
6) Top Left To Bottom Right (Right To Left).
7) Top Right To Bottom Left (Left To Right).
8) Top Right To Bottom Left (Right To Left).

The data is loaded as following

• 007 | 002 | 006
• 001 | 005 | 004
• 003 | 008 | 009

Solution brute forced:
1). [Top-Right] To [Bottom-Left] (Right To Left)
2). Bottom to Top, Column : 0
3). Left To Right, Row : 1

Here is the solution simlutated

1). [Top-Right] To [Bottom-Left] (Right To Left)

• 007 | 002 | 003
• 001 | 006 | 004
• 005 | 008 | 009

2). Bottom to Top, Column : 0

• 001 | 002 | 003
• 005 | 006 | 004
• 007 | 008 | 009

3). Left To Right, Row : 1

• 001 | 002 | 003
• 004 | 005 | 006
• 007 | 008 | 009

Here is example 2 which takes 6 moves to solve

• 009 | 008 | 007
• 006 | 005 | 004
• 003 | 002 | 001

Solve with: (6 moves)
1). [Top-Right] To [Bottom-Left] (Right To Left)
2). Top to Bottom, Column:1
3). Bottom to Top, Column:0
4). [Top-Left] To [Bottom-Right] (Left To Right)
5). Left To Right, Row:1
6). Right to Left, Row:2

So it's a pretty simple puzzle but finding efficient solutions is not a simple task. Can someone guide me in a right direction.

Answer 1

If you want to try for something even better than BFS (perhaps you want to graduate to a 14-puzzle or something), try looking into heuristic search methods, such as A* (pronounced A-star). These algorithms use some sort of rule as a proxy for evaluating which paths are likely to be successful. In the case of A*, the worst case is that it will reduce to Breadth-First Search.

The challenging part is coming up with a good heuristic to use. For A*, you need a heuristic that will never overestimate how good a path is, only underestimate. Thus, you can often come up with good heuristics by imagining best-case scenarios, or relaxing restrictions on the problem. For instance, if you're trying to find the shortest path from one point to another, the straight-line distance between points is a good heuristic. In the case of the 8-puzzle, you want some sort of metric that will gradually improve as you get closer to solving the puzzle.

Answer 2

Instead of using your random number generator solution, be more methodical.

A breadth first search (BFS) is easy to implement and will guarantee that you find the optimal solution. BFS is simply testing all of the follow up states to the current state, then testing all of the follow up states to all of those states recursively until a solution is found. More directly, BFS tests all the moves of solution length 1, then all of the moves of solution length 2, etc, until it finds a solution.

The naive implementation has the down fall of testing the same position multiple times, but you can prevent that by storing all of the previous states and their depth in the search and skipping any repeats where the stored value is lower than the current depth. There are a great many improvements for BFS, but for the simplicity of this game (only 9! states), you won't see much improvement with more sophisticated algorithms.