콘텐츠로 이동

15 퍼즐 게임: 해의 존재성

이 게임은 $4 \times 4$ 크기의 판에서 진행합니다. 이 판에는 1부터 15까지 번호가 매겨진 $15$개의 타일이 있습니다. 한 칸은 비어 있습니다(0으로 표시합니다). 타일 하나를 빈칸으로 옮기는 동작을 반복하여 판을 아래에 제시된 상태로 만들어야 합니다:

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

"15 퍼즐" 게임은 1880년에 Noyes Chapman이 만들었습니다.

해의 존재성

다음 문제를 생각해 봅시다: 판의 상태가 주어졌을 때, 해에 이르는 이동 순서가 존재하는지 판별하는 문제입니다.

판의 상태가 다음과 같다고 가정합시다:

$$\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}$$

여기서 원소 중 하나는 0이며 빈칸을 나타냅니다: $a_z = 0$

다음 순열을 생각해 봅시다:

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

즉, 판의 상태에서 0인 원소를 제외한 수들로 이루어진 순열입니다

이 순열의 역전 개수를 $N$이라고 합시다(즉, $i < j$이지만 $a_i > a_j$인 원소 $a_i$와 $a_j$ 쌍의 개수입니다).

빈 원소가 있는 행의 번호를 $K$라고 합시다(즉, 앞서 정한 표기법에 따르면 $K = (z - 1) \div \ 4 + 1$입니다).

그러면 $N + K$가 짝수일 때, 그리고 그때에만 해가 존재합니다.

구현

위 알고리즘은 다음 프로그램 코드로 나타낼 수 있습니다:

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

증명

1879년에 Johnson은 $N + K$가 홀수이면 해가 존재하지 않음을 증명했고, 같은 해에 Story는 $N + K$가 짝수인 모든 상태에 해가 있음을 증명했습니다.

그러나 이 증명들은 모두 상당히 복잡했습니다.

1999년에 Archer는 훨씬 간단한 증명을 제시했습니다(그의 논문은 여기에서 내려받을 수 있습니다).

연습 문제