Le casse - tête à quinze est particulier en ce que seulement la moitié des états d’arrangement possibles sont résolus. Si vous retournez les tuiles 14 et 15, vous ne pouvez pas faire glisser les blocs pour qu'ils soient retournés.

Votre tâche consiste à créer un programme qui accepte une liste d'entiers au format de votre choix (contenant exactement une instance de chacun des nombres de 0 à 15, 0 étant l'espace vide) représentant l'état d'une disposition de tuiles dans une grille 4x4, et génère une valeur booléenne unique déterminant si la grille est résoluble ou non.

Le code le plus court pour le faire dans n'importe quelle langue gagne.

Gelée , 9 octets

Œc>/€;TSḂ

Un lien monadique acceptant une liste des entiers lisant dans l'ordre des lignes principales alternant entre gauche-droite et droite-gauche qui donne 0si résoluble et 1sinon (pour inverser cela, ajoutez ¬à droite du code).

Essayez-le en ligne! (cet exemple est une planche où 12 doit juste glisser en place)

Comment?

Semblable à la réponse de John Dvorak, nous calculons les parités et utilisons un ordre d'entrée semblable à un serpent pour simplifier la parité du damier, bien qu'au lieu de vérifier l'égalité de parité, nous additionnons le nombre de défauts avec les indices non nuls et testons si cela est impair:

Œc>/€;TSḂ - Link: list of integers
Œc        - unordered pairs
    €     - for each:
   /      -   reduce with:
  >       -     greater than?
      T   - truthy indices (i.e. [1..16] without 1-indexed index of 0)
     ;    - concatenate
       S  - sum
        Ḃ - is odd?

J, 28 caractères

((C.!.2=_1^i.&0)&.".&.stdin''

L'ordre d'entrée est ligne par ligne avec des lignes lues alternativement de gauche à droite et de droite à gauche dans un seul chemin à travers le tableau. Suppose que le zéro appartient au coin supérieur gauche.

Utilisation sous Windows:

<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

Explication:

• <nul set /p=est utilisé pour empêcher une nouvelle ligne dans l'entrée, qui echoproduit ce qui ".n'aime pas. Bien sûr, Unix prend en charge echo /n.
• v&.".&.stdin''lit "v under parse under stdin" qui signifie "entrée, puis analyse l'entrée, puis fait v, puis annule l'analyse (= format), puis annule l'entrée (= sortie)". 1!:1]3est un caractère plus court, mais il n'a pas d'inverse défini.
• C.!.2signifie "parité de permutation". Il renvoie soit 1(parité paire) soit _1(parité impaire). C'est,_1^inversions
• _1^i.&0 signifie "-1 à la puissance d'index de 0".
• ainsi, C.!.2=_1^i.&0signifie "la parité de permutation est-elle égale à la parité de position du trou?"

Cela fonctionne pour une carte 4x4, mais si la position finale souhaitée est de gauche à droite, la permutation de la position résolue a un nombre impair d'inversions, et donc une parité impaire. De plus, la parité est inversée (pour tout ordre de saisie) lorsque la position de trou souhaitée se déplace du coin supérieur gauche vers le coin inférieur droit. Dans les deux cas, le correctif est un caractère: ajoutez -après =pour inverser la parité attendue.

Preuve d'exactitude:

Après chaque coup, le zéro échange une position avec un certain nombre, inversant la parité de permutation. Le zéro alterne également entre les positions en damier blanc et noir, indiquées par des positions impaires et paires dans l'ordre d'entrée. Ainsi, cette condition est nécessaire. Elle est également suffisante par l'argument du comptage: il est notoire qu'exactement la moitié des positions est résoluble. Cette condition filtre exactement la moitié des positions possibles.