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:
Si L 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:
La cantidad de inversiones en este caso son 3:
[3, 2], [3, 1] y [2, 1]
[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
Para la matriz m:
L = 3 -> impar
NI = 4 -> par: [6, 5], [6, 4], [5, 4], [8, 7]
Salida esperada: true
La salida debe ser:
validPuzzle(m) = true
Test 1
Para la matriz m:
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:
L = 4 -> par
Fila X = 1 -> impar
NI = 0 -> par
Salida esperada: false
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