Does this game have a solution

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

3x3

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

4x4

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

The objective of this game is to fill numbers from 1 to 8 (or 1 to 15) using the one space available to push the numbers to that empty space. Every time I end up with the combination shown above. I just want to convince myself that there is no way to attain the proper solution from the above scena开发者_Python百科rio. Please help.

EDIT : Solution has been posted at here and here

---

Yes, and no. If you generate the numbers randomly, I believe that there is a situation that could occur that causes the puzzle to be unsolvable. The way I'd suggest generating a puzzle is starting with the solved puzzle, and executing a number (increasing based on difficulty) of moves in reverse. That way you know that the end puzzle is solvable.

---

This discussion of The 15 Puzzle will probably give you the answer. I suspect that the analysis of the permutations in that puzzle will apply to your smaller puzzle.

---

From the french wikipedia on the "Taquin" (The 15 puzzle) :

Anecdote

Position initiale du taquin de Sam Loyd
Loyd affirma qu'il avait « rendu le monde entier fou » avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 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.
La résolution de ce problème est impossible. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut 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 de glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.

---

Anecdote

Initial position of Sam Loyd's 15 puzzle
Loyd said he had "made the world crazy" with a 15 puzzle modified. In the proposed configuration, the tiles 14 and 15 were reversed, the empty space being placed in the bottom right. Loyd claimed to have promised 1 000 USD for one who would put the tiles in order, but the reward was never claimed. Solving this problem is impossible. On the one hand, it must indeed swap the places of the tiles 14 and 15, and it can be shown that this operation requires an odd number of slides. On the other hand, the empty space must go back to its original position, an operation which, requires an even number of slides. It is possible to order the numbers 1 to 15 if the empty space is initially in the upper left.

---

Resources :

• fr.wikipedia - Taquin