Sliding Puzzle

The Sliding Puzzle demo is the classic 8-puzzle: eight numbered tiles and one empty square on a 3 by 3 board. The goal is to slide the tiles until they read 1 to 8 in order with the empty square in the bottom-right corner. The genetic algorithm doesn't solve the whole thing in one go. Before every move it evolves a short plan, plays the first move of that plan on the board, and then plans again from the new position.

The Puzzle¶

Each new board is made by starting from the solved puzzle and making 20 random slides, never undoing the slide just made. Because it starts from a solved board, every scramble is guaranteed to be solvable. Click Scramble at any time for a fresh one.

Moves are named by the direction the empty square travels: U, D, L and R for up, down, left and right.

How a Move Is Chosen¶

Each candidate in the population is a sequence of up to 20 moves. Every gene is turned into a legal slide from wherever the empty square is at that point, and the plan never immediately undoes its previous slide, so no moves are wasted bouncing back and forth.

Fitness looks at the board after the whole sequence has played out. It rewards a small total Manhattan distance, which is how many rows and columns each tile is away from its home square, added up over all eight tiles. A sequence that actually solves the puzzle gets a very large bonus, and among solving sequences, shorter ones score higher. A tiny extra goes to the closest the board got to solved along the way, which helps the search past spots where the right move briefly makes things look worse.

The GA runs until it reaches its generation limit or its time budget (1.5 seconds by default), and the first move of the best sequence is played. If that best sequence solves the puzzle, the demo keeps it and plays the rest of it move by move without searching again, as long as the board and settings haven't changed. The Move source row in the GA Result panel tells you which happened: a new GA search, or the verified evolved plan.

How a Run Looks¶

Click Auto-solve. The demo plans and plays one move after another until the puzzle is solved. The two squares that just swapped are highlighted, and the GA Result panel shows the current Manhattan distance, the last move played and which tile it moved, the best fitness, how many generations ran, how long the search took, and the first eight moves of the evolved sequence. Stop auto pauses the loop and Resume auto carries on from the same board. When the board is solved, a dialog offers a new game.

Settings to Try¶

Open Settings to change the GA used for each move. Your choices are saved in your browser and apply on the next Auto-solve, or straight away with Apply & Reset, which also scrambles a new board.

• Population size (10 to 200, default 60) and Generations per move (10 to 300, default 80).
• Mutation percent (1 to 50, default 15) and Elites preserved (0 to 10, default 2).
• Step deadline (0.3 to 5 seconds, default 1.5). How long the GA gets to think per move. Lower is snappier; higher gives it more time to find a clean solve.
• Sequence length (5 to 40, default 20). How many moves each plan holds. Longer plans can see further ahead, but the search space gets bigger.

What the Achievement Rewards¶

Signed-in users unlock the Puzzle solver achievement the first time a move chosen by the GA slides the last tile home and the board reads as solved.

For more on how the demos catalog works, see What the Demos Do.