15 Puzzle Game: Existência da Solução

Este jogo é jogado em um tabuleiro $4 \times 4$. Neste tabuleiro, existem $15$ peças numeradas de 1 a 15. Uma célula é deixada vazia (indicada por 0). Você precisa colocar o tabuleiro na posição apresentada abaixo movendo repetidamente uma das peças para o espaço livre:

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

O jogo "15 Puzzle" foi criado por Noyes Chapman em 1880.

Existência da solução

Vamos considerar este problema: dada uma posição no tabuleiro, determine se existe uma sequência de movimentos que leva a uma solução.

Suponha que tenhamos alguma posição no tabuleiro:

$$\begin{matrix} 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{matrix}$$

onde um dos elementos é igual a zero e indica uma célula vazia $a_z = 0$

Vamos considerar a permutação:

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

ou seja, a permutação de números correspondentes à posição no quadro sem um elemento zero

Seja $N$ o número de inversões nessa permutação (ou seja, o número de tais elementos $a_i$ e $a_j$ em que $i < j$, mas $a_i > a_j$).

Suponha que $K$ seja um índice de uma linha onde o elemento vazio está localizado (ou seja, usando nossa convenção, $K = (z - 1) \div \ 4 + 1$).

Assim, a solução existe se $N + K$ for par.

Implementação

O algoritmo acima pode ser ilustrado com o seguinte código:

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");

Prova

Em 1879, Johnson provou que, se $N + K$ é ímpar, a solução não existe e, no mesmo ano, Story provou que todas as posições em que $N + K$ é par têm uma solução.

No entanto, todas essas provas eram bastante complexas.

Em 1999, Archer propôs uma prova muito mais simples (você pode fazer o download do artigo dele aqui).

Problemas