This program was inspired by AIS's 'Can you HACK it?' Tiles challenge, which requires the user to solve a 5 x 5 variant of the 15 puzzle in under 350 moves and a time constraint.
The initial approach was to find and use a constant time and memory solution, where rules would be hard coded. This was fine, and turns out to be just a large state machine. However, that does not lead to a good story or learning experience about machine learning. Additionally, the program was a mess to debug.
The solution this program uses solves (with enough time and computing power) any variant of the 15 puzzle,
down to size 3 x 3 and as large as 8 x 8. The current approach uses Local Search Heuristics,
also known as Hill Climbing, combined with an allowance. There is no neural net.
The algorithm explores a graph, starting with its parent node, and "moving" in the up, down, right, and left,
caluclating an evalution score of 0.0(terrible) to 1.0(sovled). If a child is evaluation to be better than
its parent, it gets to keep its allowance. If worse, it must "pay" its allowance. Once a node no longer has an
allowance, it may no longer be explored.
There are two "programs" included (two python packages). Tile Solver can be run with run_ts with an assortment
of flags. For a quick demonstration, run run_ts -v -r 4, which will run in verbose mode on a 4 x 4 radnomly
generated board. EvalSuite is a multi processed evalution tool that runs n amount of boards of various sizes,
and aggregates various important attributes into a statistical output. This tool allows for better understanding
of changes made to Tile Solver. It is currently still be impleneted and is the main focus as of today (12/27/2025).
Local Search Heuristics does not guarantee to find the global minima (the shortest possible path to a solution). On occassions, it is possible, but often times it finds a local minima (a solution; but no the best solution) that satisifies the problem. This algorithm is no different, and under the constraint of moves as found in the original AIS challenge, can find itself computing millions of evaluations for boards at the bottom of the tree that have no hope of finding the solution.
python3 -m venv venv
source venv/bin/activate
pip install -r requirments.txt
For a demonstartion of Tile solver, run run_ts -v -r 4.
For a demonstration on EvalSuit, run eval_ts. Note: this is being actively developed and may not work. Unix only.
There will be no contributions accepted at this time.
15 puzzle is not always solveable. EvalSuit and TileSolver use random generate boards that are proved
to be solveable by counting the amount of inversions.
- CuPy: GPU Acceleration. Should be interesting.
- Fire Graphs: Run a fire graph on a single evaluation. Determine any bottlenecks.