This game has a solution.

Question

I am developing a simple game using Java swing. I want to know if this particular game has a solution in the following scenario. If I am convinced that a theoretical solution cannot be reached at this point, I will send a notification to the user.

3x3
http://img814.imageshack.us/img814/7449/screenshot20100924at206.png

4x4
http://img39.imageshack.us/img39/1851/screenshot20100924at241.png

The goal of this game is to fill in numbers from 1 to 8 (or from 1 to 15) using one space available for entering numbers into this empty space. Every time I finish the combination shown above. I just want to convince myself that there is no way to get the right solution from the above scenario. Please, help.

EDIT: The solution is posted in here and here.

Answer 1

Yes and no. If you randomly generate numbers, I believe that there is a situation that could lead to the puzzle being unsolvable. The way that I propose creating a puzzle begins with the puzzle being solved and the number (increasing in complexity) of the movements in the reverse order. So you know that the ultimate puzzle is solvable.

Answer 2

This discussion of 15 Puzzle is likely to give you an answer. I suspect that the permutation analysis in this puzzle is applicable to your little riddle.

Answer 3

From the French Wikipedia on Takvin (15 puzzles):

Joke

Position initiale du taquin de Sam Loyd
Loyd affirma qu'il avait "rendu le monde entier fou" avec un taquin modifié. Dans la configuration offer, les carreaux 14 and 15 étaient inversés, l'espace vide étant placé en bas à droite. Loyd prétendait avoir promis 1,000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.
Unable to solve the problem. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on on pept montrer que cette opération nécessite un nombre impair de glissements. D'autre part, il faut que la case vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair of glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.

---

Joke

Sam Loyd's 15 puzzle starting position Loyd said he "made the world crazy" with a modified 15 puzzle. In the proposed configuration, tiles 14 and 15 were inverted, an empty space was placed in the lower right corner. Loyd claimed to have promised $ 1,000 for someone who would put the tiles in order, but the award was never claimed. The solution to this problem is impossible. On the one hand, it should really swap tiles 14 and 15, and it can be shown that an odd number of slides are required for this operation. On the other hand, empty space should return to its original position, an operation that requires an even number of slides. You can order numbers from 1 to 15 if the empty space is initially in the upper left corner.

---

Resources:

• fr.wikipedia - Taquin