why-is-the-15-puzzle-unsolvable

Why is the 15 Puzzle unsolvable

The “15 Puzzle”, also known as the “15 Digital Problem”, is not unsolvable, but rather the goal state cannot be reached in certain initial states.

Game Description

“15 Puzzle is a slider game where the game board is a 4×4 grid with 15 sliders labeled 1 to 15 and a space. The player's goal is to move the sliders in a left-to-right, top-to-bottom order, resulting in an ordered sequence of 1 to 15, with the space in the lower right corner.

Unsolvable cases

The situation cannot be legally moved to reach the target state if, and only if, the number of inverse-order pairs in the initial state is odd. A reverse-ordered pair is a pair of numbers in a series that are called a reverse-ordered pair if their front and back positions are in the opposite order of magnitude, i.e., the number in front is greater than the number behind. For example, in the series 2, 4, 3, 1 , the inverse pairs are (2, 1), (4, 3), (4, 1), (3, 1), totaling four.

Proof.

The movement of the sliders on the board can be thought of as a transformation of the arrangement of these sliders. Each time a slider is moved, a space is actually exchanged with a neighboring slider. And this swapping operation changes the parity of the inverse logarithm of the arrangement. The inverse logarithm of the target state is 0, which is even. If the initial state's inverse logarithm is odd, no matter how many times it is moved, its inverse logarithm cannot be changed to even, and the target state cannot be reached.

If you like to play Puzzles ball too, it's totally free and fun and easy.