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 40 random slides, never undoing the slide just made. Because it starts from a solved board, every scramble is guaranteed to be solvable. A scramble is only kept if its Manhattan distance (explained below) is at least 8, so a new board always needs at least 8 moves and never opens already solved or one slide away. Click Scramble at any time for a fresh one. A small picture of the goal board sits in the GA Result panel.

On screen, moves are shown as arrows for the direction a tile slides into the empty square. For example, ← means the tile to the right of the empty square slid left.

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 Last move row in the GA Result panel tells you which happened: a new GA search, or the verified evolved plan.

How a Run Looks¶

Click Step to let the GA plan and play a single move, or Auto-solve to have it plan and play one move after another until the puzzle is solved. Stop auto pauses the loop and Resume auto carries on from the same board.

You can also play by hand. Tiles next to the empty square are buttons (with a small arrow showing which way they would slide): click one, or tab to it and press Enter, to slide it. You can mix your own moves with GA moves, and the GA always plans from the board as it is now. While Auto-solve is running, the tiles and Step are paused so the board can't change under it.

The tile that just moved slides into place and is highlighted. Above the board you'll see the move count and the distance to the goal. The GA Result panel shows the last move (which tile slid which way, and whether you or the GA played it) and, after a GA move, the best fitness, how many generations ran, how long the search took, and the first eight moves of the evolved sequence. When the board is solved, a message says how many moves it took and 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 from the next GA move (Step or 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. Solving it entirely by hand doesn't count.

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