Click on number tiles to move them to adjacent empty space in grid and arrange them in order 1 to 15.
- Press RESTART to start game
- Press SHUFFLE to shuffle game
- Press SOLVE to auto solve game
The n-puzzle is a classical problem for modelling algorithms involving heuristics. Half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. (source)
To make sure every new game and every shuffle is solvable, the game tries to shuffle the board starting from the solved state itself.
The problem of finding the shortest solution is NP-hard. Jamie Wong tries to solve this problem in browser using Tree Pruning, Las Vegas Randomization, Min-Heap Priority Queue, (Quantum Computers?) after taking Introduction to Artificial Intelligence course and the result is painfully slow if you shuffle the board too hard. Try it yourself.
Since, I wanted to implement this in a single weekend I chose a simple approach. The game stores every move in an array and just backtracks it to reach the solution. ¯_(ツ)_/⁻
The game intelligently (AI?) backtracks it's moves to prevent repetitive to and fro of the same moves. It store all the moves in an array and truncates if a previously seen state is encountered again.
react@16.8.6react-redux@7.0.3- Developed using
create-react-app - Deployed using
gh-pages
There might be some bugs and unhandled edge cases so go easy on this baby.