Comprueba si el 15 rompecabezas es solucionable

9

El enigma quince es peculiar porque solo la mitad de los posibles estados de disposición son solucionables. Si volteas las fichas 14 y 15, no hay forma de que puedas deslizar los bloques para que se vuelvan.

Su tarea es crear un programa que acepte una lista de enteros en el formato que elija (que contenga exactamente una instancia de cada uno de los números del 0 al 15, siendo 0 el espacio en blanco) que representa el estado de una disposición de mosaicos en una cuadrícula de 4x4, y genera un único valor booleano que determina si la cuadrícula tiene solución o no.

El código más corto para hacer esto en cualquier idioma gana.

Joe Z.
fuente
Buena pregunta :)
Cruncher
Iba a hacer esta pregunta, pero con una longitud lateral arbitraria; pero eso agrega muy poco al desafío.
Jonathan Allan el

Respuestas:

0

Jalea , 9 bytes

Œc>/€;TSḂ

Un enlace monádico que acepta una lista de enteros que se lee en orden de fila mayor alternando entre izquierda-derecha y derecha-izquierda, lo que produce 0si es solucionable y 1si no (para invertir esto agregue ¬a la derecha del código).

Pruébalo en línea! (este ejemplo es un tablero donde 12 solo necesita deslizarse en su lugar)

¿Cómo?

Similar a la respuesta de John Dvorak, calculamos paridades y utilizamos un orden de entrada similar a una serpiente para simplificar la paridad del tablero, aunque en lugar de verificar la igualdad de paridad sumamos el recuento fuera de orden con los índices distintos de cero y probamos si eso es impar:

Œ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?
Jonathan Allan
fuente
4

J, 28 caracteres

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

El orden de entrada es de fila principal con filas que se leen alternativamente de izquierda a derecha y de derecha a izquierda en una sola ruta a través de la tabla. Asume que el cero pertenece a la esquina superior izquierda.

Uso en Windows:

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

Explicación:

  • <nul set /p=se usa para evitar una nueva línea en la entrada, que echoproduce que ".no le gusta. Por supuesto, Unix es compatible echo /n.
  • v&.".&.stdin''lee "v bajo parse bajo stdin" que significa "entrada, luego analiza la entrada, luego hace v, luego deshace el análisis (= formato), luego deshace la entrada (= salida)". 1!:1]3es un carácter más corto, pero no tiene un inverso definido.
  • C.!.2significa "paridad de permutación". Devuelve 1(paridad par) o _1(paridad impar). Es decir,_1^inversions
  • _1^i.&0 significa "-1 a la potencia del índice de 0".
  • entonces, C.!.2=_1^i.&0significa "¿la paridad de permutación es igual a la paridad de la posición del agujero?"

Esto funciona para un tablero de 4x4, pero si la posición final deseada es mayor de fila de izquierda a derecha, entonces la permutación para la posición resuelta tiene un número impar de inversiones y, por lo tanto, paridad impar. Además, la paridad se invierte (para cualquier orden de entrada) cuando la posición deseada del agujero se mueve desde la parte superior izquierda a la parte inferior derecha. En ambos casos, la solución es un carácter: agregue -después =para revertir la paridad esperada.

Prueba de corrección:

Después de cada movimiento, el cero intercambia una posición con algún número, cambiando la paridad de permutación. El cero también alterna entre las posiciones de tablero de ajedrez blanco y negro, indicado por posiciones pares e impares en el orden de entrada. Por lo tanto, esta condición es necesaria. También es suficiente por el argumento del conteo: es de conocimiento común que exactamente la mitad de las posiciones es solucionable. Esta condición filtra exactamente la mitad de las posibles posiciones.

John Dvorak
fuente
Cuando dice "el cero también alterna entre las posiciones pares e impares": ¿no cambia en +1, -1, +4 o -4? Creo que un patrón marcado le da el color que necesita, pero podría describirse con mayor precisión.
Peter Taylor
@PeterTaylor tienes razón; lo siento. ¿Mi edición cuenta como una solución válida?
John Dvorak
Creo que su edición aborda un problema completamente diferente. Lo que cité está en el último párrafo.
Peter Taylor
"Entre posiciones pares e impares" es más como "entre cuadros blancos y negros en un tablero de ajedrez".
Joe Z.