15 Puzzle

1. 15 puzzle

In 1878, Noah Chapman invented the game of 15 puzzle. The puzzle consists of 15 identical square tiles in a square box. Each such element is numbered. The box has a size of 4x4 tiles (1 square remains empty). There may also be other variations of this game 3x3, 5x5 and others. The goal of the game is simple - arrange the tiles in ascending order by moving them inside the box.

2. The mathematics of permutations

The number of possible initial positions of the game is n!

In exactly half of all possible initial positions of the 15 puzzle, it is impossible to bring them to an assembled form. Read more here.

3. Task Formulation

Given 2 matrices: initial and final. Implement a solution to the problem (performing a depth-first search), applying heuristic.

4. The solution of the problem