Juego del 15: existencia de la solución

Este juego se juega en un tablero $4 \times 4$ . En este tablero hay $15$ fichas numeradas del 1 al 15. Una celda se deja vacía (denotada por 0). Hay que llevar el tablero a la posición presentada abajo moviendo repetidamente una de las fichas al espacio libre:

$\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 0 \end{array}$

El juego “15 Puzzle” fue creado por Noyes Chapman en 1880.

Existencia de la solución

Consideremos este problema: dada una posición en el tablero, determinar si existe una secuencia de movimientos que lleve a una solución.

Supongamos que tenemos alguna posición en el tablero:

$\begin{array}{cccc} a_{1} & a_{2} & a_{3} & a_{4} \\ a_{5} & a_{6} & a_{7} & a_{8} \\ a_{9} & a_{10} & a_{11} & a_{12} \\ a_{13} & a_{14} & a_{15} & a_{16} \end{array}$

donde uno de los elementos es igual a cero e indica una celda vacía $a_z = 0$

Consideremos la permutación:

$a_1 a_2 … a_{z-1} a_{z+1} … a_{15} a_{16}$

es decir, la permutación de números correspondiente a la posición en el tablero sin el elemento cero

Sea $N$ el número de inversiones en esta permutación (es decir, el número de tales elementos $a_i$ y $a_j$ tales que $i < j$ , pero $a_i > a_j$ ).

Supongamos que $K$ es un índice de una fila donde está ubicado el elemento vacío (es decir, usando nuestra convención, $K = (z - 1) \div \ 4 + 1$ ).

Entonces, la solución existe sii $N + K$ es par.

Implementación

El algoritmo de arriba se puede ilustrar con el siguiente código de programa:


int a[16];
for (int i=0; i<16; ++i)
    cin >> a[i];
 
int inv = 0;
for (int i=0; i<16; ++i)
    if (a[i])
        for (int j=0; j<i; ++j)
            if (a[j] > a[i])
                ++inv;
for (int i=0; i<16; ++i)
    if (a[i] == 0)
        inv += 1 + i / 4;
 
puts ((inv & 1) ? "No Solution" : "Solution Exists");

Demostración

En 1879 Johnson demostró que si $N + K$ es impar, entonces la solución no existe, y en el mismo año Story demostró que todas las posiciones cuando $N + K$ es par tienen solución.

Sin embargo, todas estas demostraciones eran bastante complejas.

En 1999 Archer propuso una demostración mucho más simple (se puede descargar su artículo aquí ).

Problemas de práctica

Hackerrank - N-puzzle