Try   HackMD

¿Es posible resolver el 15-puzzle?

En este ejercicio vamos a estar trabajando con la representación en forma de matriz cuadrada de enteros (int) de un 15-puzzle. Se puede jugar al juego desde aquí.
Se pide generar un método que para una matriz de entrada, devuelva verdadero, si el puzzle tiene solución o falso si no se puede resolver

Las reglas para comprobar que un 15-puzzle de lado L puede ser resuelto son:

Si L es impar:

  • El puzzle puede ser resuelto si el número de inversiones es par

Si L es par:

  • Si la fila donde esta el espacio en blanco esta en una fila impar:
    • El puzzle puede ser resuelto si el número de inversiones es impar
  • Si la fila donde esta el espacio en blanco esta en una fila par:
    • El puzzle puede ser resuelto si el número de inversiones es par

El número de inversiones (NI) se obtiene de la siguiente manera:
Si pensamos el puzzle en una dimensión en vez de dos dimensiones, el número de inversiones es la cantidad de números mayores a la derecha de cada posición. Por ejemplo consideremos una matriz de 3x3 escrito en una dimensión:

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

La cantidad de inversiones en este caso son 3:
[3, 2], [3, 1] y [2, 1]

Input/Output

[input] int[][] m
La matriz m representada en una matriz cuadrada de enteros. El número 0 representa el espacio vacio
2 ≤ m[0].length ≤ 9
0 ≤ m[i] ≤ (m[0].length)² - 1

[output] boolean
true | false

Ejemplo

Para la matriz m:

1 2 3
6 5 4
8 0 7

L = 3 -> impar
NI = 4 -> par: [6, 5], [6, 4], [5, 4], [8, 7]
Salida esperada: true

La salida debe ser:
validPuzzle(m) = true

Tests

Test 1
Para la matriz m:

1 8 2
0 3 4
7 6 5

L = 3 -> impar
NI = 9 -> impar: [8, 2], [8, 3], [8, 4], [8, 7], [8, 6], [8, 5], [7, 6], [7, 5], [6, 5]

Salida esperada: false

Test 2
Para la matriz m:

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

L = 4 -> par
Fila X = 1 -> impar
NI = 0 -> par

Salida esperada: false

Bibliografía

La lógica de la resolución de este tipo de puzzles de deslizamiento es explicada en el siguiente artículo de THE UNIVERSITY OF BIRMINGHAM: TilesSolvability