# ¿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](https://en.wikipedia.org/wiki/15_puzzle). Se puede jugar al juego desde [aquí](https://lorecioni.github.io/fifteen-puzzle-game/).
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](https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html)