Comment résoudre par programme le puzzle 15 (nombres mobiles)?

tous, vous avez probablement vu le déplacement de nombre/photo puzzle. Celui où vous avez des numéros de 1 à 15 dans une grille 4x4, et tentent de les obtenir à partir aléatoire de la position de départ pour

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15

Ma copine ou certains de mes non-programmeur amis pouvez résoudre ce problème avec certains mumbo-jumbo, de la magie, qu'ils ne peuvent pas m'expliquer. Je ne peux pas résoudre le puzzle.

L'approche la plus prometteuse que j'ai trouvé est de résoudre première ligne, alors que j'obtiendrais

1   2  3  4
X   X  X  X
X   X  X  X
X   X  X

puis la première colonne sans toucher résolu cellules

1   2  3  4
5   X  X  X
9   X  X  X
13  X  X

puis la deuxième ligne de

1   2  3  4
5   6  7  8
9   X  X  X
13  X  X

puis la deuxième colonne

1   2  3  4
5   6  7  8
9   10  X  X
13  14  X

le problème est, que reste X (aléatoire) de la dalle sont parfois impossibles à résoudre position et c'est là que ma solution ne peut pas. Mais je me sens comme si je suis sur la bonne voie.

Mon programme ne prend la résolution de certaines de ligne/colonne en essayant d'obtenir le nombre X à la position indiquée sans perturber le fonctionnement de cellules appropriées, si possible. Mais il ne peut pas faire le dernier de 3 cases sur la grille 2x2. Ce qui me manque?

source d'informationauteur Axarydax

  1. 5

    Vous êtes certainement sur la bonne voie, mais plutôt que de le résoudre par ligne/colonne de manière itérative au point d'être de gauche avec un 2x2, résoudre jusqu'à ce que vous avez un minimum de 3x3 puis de les résoudre simplement que la grille. 3x3 est la plus petite taille dont vous avez besoin pour bien re-commande de la grille (tout en 2x2 ne vous donne pas la flexibilité que vous pouvez avoir besoin, comme vous l'avez déjà discuté). Cette approche est évolutif, vous pouvez résoudre 5x5, 10x10 etc.

  2. 10

    Assurez-vous que votre puzzle est résoluble en premier. Tous ne sont pas.

    Sinon votre stratégie semble sain.

  3. 4

    Ce site a une belle explication sur les grilles 3x3, vous pouvez probablement s'étendre à d'4x4 assez facilement.

  4. 3

    Je pense que le moyen Le plus efficace de résoudre ce, à l'aide d'additifs modèles, avec un admisible heuristique, et de l'IDA* algorithme. Comme décrit ici - http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf. (Je pense que Felner nous a dit qu'il a trouvé un moyen qui est bien mieux, mais je ne me souviens pas exactement de ce qu'il était (bidirectionnel*?), mais de toute façon cela devrait être suffisant (-: ).

    De toute façon ce cours était il y a longtemps, donc je vous recommande la lecture de l'article..

    HTH. Prendre soin.

  5. 1

    Par la réduction le seul cas où vous ne pouvez pas résoudre doit être de la forme

    1 3

    2 X

    et que vous souhaitez obtenir pour

    1 2

    3 X

    par l'utilisation d'un autre de ligne et de colonne vous pouvez déplacer des personnes à la bonne place avec un simple précalculées séquence

  6. 1

    La solution la stratégie décrite par le posteur d'origine sera toujours travailler pour une norme résoluble 15-puzzle. Si Axarydax peut réduire de 15-puzzle à l'état qu'il décrit et toujours pas en mesure de le résoudre, alors il était impossible de commencer avec. Laissez-moi vous expliquer.

    Si nous traitons de l'espace vide dans le puzzle comme l'un des carreaux, puis chaque mouvement implique la permutation à vide "tuile" pour une case adjacente. Cela nous permet de nous à l'égard des motions sur le puzzle de permutations sur 16 caractères. Qui est, des éléments du groupe symétrique S16. Chaque primitive déplacer est un "swap" ou de transposition entre deux éléments (dont l'un est le vide).

    Parce que le puzzle commence et se termine avec la tuile vierge dans la partie inférieure droite, la tuile vierge devez déplacer un même nombre de fois pour le puzzle à résoudre. (C'est plus facile à voir en imaginant une superposées motif en damier sur le dessus du puzzle -- après un nombre impair de déplace le vide serait sur un autre carré de couleur.) Cela signifie que la solution adopté doit être un produit de uniformément nombre de permutations, de sorte qu'il doit être un élément de l'alternance de groupe16qui a exactement la moitié de la S16. (Du 16! les permutations de S1616!/2 permutations sont encore, et de 16!/2 sont impairs. En outre, même*même=même, même*impair = impair, et de l'impair*impair=pair.)

    Si la nécessaire correction de permutation arrive à être bizarre, il n'est pas possible de résoudre le puzzle, peu importe ce que vous faites. Si la correction de permutation est de même, et si Axarydax suit la stratégie décrite, alors la permutation nécessaires pour le reste de 2x2 bloc sera nécessairement un même permutation de la fixation du carré blanc. Le seul, même permutations de seulement trois éléments sont les rotations 1->2->3->1 (cycle de notation (123)) et 1->3->2->1 (cycle de notation (132)). Ceux-ci sont facilement effectuées sur les quatre autres carrés, sans déranger les autres.

    Car il est peu plausible que le Axarydax ne peut pas comprendre ces solutions triviales de la 2x2 blocs, je pense que soit il a été pranked, ou la 15-puzzle d'une tentative non standard, d'une certaine façon.

  7. 0

    Il y a toujours jusqu'à 4 transférer des postes de donné un. Je me demande si l'algorithme simple qui va au-dessus de toutes les options de construction 2-4 arbre atteindre le "résolu" position ou le dépassement de pile 🙂