Applying A* (A-star) to solve n-puzzle problems.

• This project applies A* for solving the n-puzzle problem. The project supports 5 heuristics now, including Misplaced, Manhattan, Inversion, Manhattan with Linear Conflict, and Walking Distance. The project also provides a user-friendly interface for users to interact with the puzzle.

• You can change the size of the problem to what you want. And you can provide the start state for the problem by the State field. The project will provide you with the solution, and the time it took to find the solution.

• Note:

  • 4x4 is the best one this app can solve, do not try to solve a 5x5 or 6x6 puzzle, it will take a lot of memory and time. If it runs out of memory, your browser will crash.
  • If your start state is not solvable, the Find Solution button will be disabled.

• In this project, I implemented 5 heuristics that will be shown in the table below.

• Use deployed version aStar.

• Do it local

  $ git clone git@github.com:1cedrus/aStar.git
  $ cd aStar && bun install
  $ bun start

I skip Misplaced - Hamming Distance because it is slow and memory-costly so it will be impossible to solve 4x4 problems.

Case 1: 4,7,5,6,0,2,14,13,3,1,9,10,15,11,12,8

Case 2: 0,1,6,3,10,2,12,11,15,8,5,13,14,9,4,7

Case 3: 7,4,8,11,1,10,14,2,12,0,6,13,3,9,5,15

Case 4: 8,1,14,15,2,0,3,12,4,6,13,11,5,9,10,7

Case 5: 13,11,2,6,3,4,12,8,7,1,0,5,15,14,9,10

• If you notice, Manhattan Distance and Inversion Distance differ in their focus:

  • Manhattan Distance only cares about the correct position of tiles and the fastest way to move them to their correct positions, ignoring the empty box.
  • Inversion Distance, on the other hand, focuses on how many times the empty box needs to move left-right or up-down to reduce the inversion count to 0 (the goal state has an inversion count of 0), without considering the correct spot for each tile.

  So, which one is faster depends on the specific problem.

• Walking Distance is the mix between Manhattan Distance and Inversion Distance. Make it have a better performance.

• Manhattan & Linear Conflict is the mix between Manhattan and Linear Conflict.

• Manhattan - Inversion - Walking Distance
• Linear Conflict
• My Report (Vietnamese)