Sliding tile puzzle is something that is actually easy, if you are a fan of the Rubic Cube. And if you want to solve it with IDA* (iterative Deepening A*) and with Manhattan heuristic, this is the correct place. The solution is written for a Jupyter Lab and visualises the steps one by one, based on the step around the empty tile, which is a zero in our case.
A place in Nuremberg, where people used to sit and drink beer until they can make complete DFS of the sliding tile puzzle or until they had to go home. (whichever happened first)
What the puzzle is:
- You have an n x n board with tiles 1..N and a blank 0.
- A move swaps the blank with a neighbor (up, down, left, right).
- Goal: reach a specific arrangement. The blank’s goal index can be anywhere (index I); by default it is the bottom-right.
Input format:
- First number is the number of numbered tiles (8, 15, 24, etc). Total cells are N+1 = n^2
- The second number is the goal index of teh blank. (0 based). Use -1 for bottom-right.
- The third part of the input is the grid.
Expected output:
The directions are for the tile that is moved, not the blank.
The method in summary:
- IDA* = Iterative Deepening A*.
It does depth-first search with a cost limit on f = g + h (forecast = goal + heuristics).
If not solved, it raises the limit to the smallest cut value and repeats.
It uses low memory and remains optimal with an admissible heuristic. - Manhattan heuristic
For each tile, count the grid steps (up/down/left/right) to its goal square, then sum them.
Ignore the blank. This is admissible and consistent for sliding puzzles. - Solvability check
Many boards are unsolvable. We check parity of inversions (ignoring 0) and the row of the blank counted from the bottom. This works for odd and even boards and for any goal index I.
https://www.youtube.com/watch?v=T9kd-1ZEiUk
The GitHub code is here: https://github.com/Vitosh/Python_personal/blob/master/YouTube/046_Jupyter-N-Plates
Enjoy it! 🙂
دیدگاهتان را بنویسید