The 15 Puzzle is a popular sliding puzzle game, in which there is one empty space and 15 numbered tiles. The goal of the game is to move tiles around by sliding them into the empty space until the numbers are arranged in order and the empty space is in the bottom right corner. The Wikipedia page has some pretty good illustrations a more in-depth explanation of how the puzzle works.
This project is still in development, but my overall process has been to code basic A* heuristics and then improve on them with optimizations. I started by creating a model of the game that could be easily rendered to ASCII for visualization purposes, and have since improved on it to make it more suitable for the A* pathfinding algorithm. This game is proven to be NP-hard, so my approach has been to decrease graph coverage to roughly 1 node per 100 quadrillion (for a 40-move shuffle, which I've been using as a benchmark). Time and space complexity are both O(3^n) (where n is the minimum number of moves to solve the puzzle), so reducing the graph coverage drastically is absolutely necessary to solve this problem in anything less than billions of years and with anything less than billions of petabytes of memory. My end goal is to experiment with preprocessing and the IDA* algorithm to reduce space complexity to O(1) and be able to solve an 80-move shuffle (the most difficult shuffle possible).
In its current state, this code can be run on the command line as a script with python3 solver.py. It will print out the number of nodes explored, the number of moves to solve the shuffle, the actual series of moves, and the time (in seconds) it took to solve the shuffle. An interactive UI will be added once I'm satisfied with the heuristic implementations. For now, just change the string passed to the is_solvable() and solve_and_print() calls at the bottom of the file to one of the included shuffles, or add your own shuffle in the same format and pass that into the functions. Don't bother trying to solve the 80-move shuffle, as it will take many years (and use up all your RAM pretty quickly). In its current state, documentation is poor and the only available heuristic is a very buggy version of the Manhattan heuristic, so it's not recommended to try to change the heuristic or run it on the 40-move shuffle either. This will be changed in a matter of days from today (6/20/21), so check back later if you're interested.