Project Name

Upgraded README.md

Taquin is a three.js experience. Showing, explaining and detailing a school homework.

Goal

The purpose of this project is to solve a sliding puzzle, initiate in a random solvable configuration, by finding the optimal path to the goal configuration.

Solution

To solve it, we are going to use an A* algorithm with a manhattan distance

The solvability criteria is not the same for a
odd-sized and an even-sized board

Odd-sized

For a Odd-sized board, the solvability criteria is the number of inversion

Indeed, each move change the number of inversion by an even number

Thus, an odd-sized board is solvable only if the number of inversion is even

Even-sized

For a Even-sized board, the solvability criteria is the sum of the number of inversion and the line of the empty tile

An even-sized board is solvable only if the sum of the number of inversion and the line of the empty tile is odd

Number of inversion

To get the number of inversion, we just gonna use a Fenwick tree (BIT) on a array version of our board, to slightly improve complexity (from O(n²) to O(n*log(n²)))

more here

A* algorithm need distance evaluation.

We can use either Hamming distance or Manhattan distance.

Hamming

The Hamming distance between a board configuration and the goal configuration is the number of tiles in the wrong position.

Manhattan

The Manhattan distance between a board configuration and the goal configuration is is the sum of the Manhattan distances (sum of the vertical and horizontal distance) from the tiles to their goal positions.