پرش به محتویات

بازی پازل ۱۵: وجود راه‌حل

این بازی روی یک صفحه‌ی $4 \times 4$ انجام می‌شود. روی این صفحه ۱۵ کاشی بازی شماره‌گذاری شده از ۱ تا ۱۵ وجود دارد. یک خانه خالی باقی می‌ماند (که با 0 نشان داده می‌شود). شما باید با حرکت دادن مکرر یکی از کاشی‌ها به خانه‌ی خالی، صفحه را به حالت زیر برسانید:

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

بازی «پازل ۱۵» توسط 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}$$

که در آن یکی از عناصر برابر با صفر است و خانه‌ی خالی را نشان می‌دهد ($a_z = 0$).

جایگشت زیر را در نظر بگیرید:

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

یعنی جایگشت اعداد متناظر با حالت صفحه بدون در نظر گرفتن عنصر صفر.

فرض کنید $N$ تعداد وارونگی‌ها در این جایگشت باشد (یعنی تعداد عناصری مانند $a_i$ و $a_j$ که $i < 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");

اثبات

در سال ۱۸۷۹، Johnson ثابت کرد که اگر $N + K$ فرد باشد، راه‌حلی وجود ندارد و در همان سال Story ثابت کرد که تمام حالت‌هایی که در آن‌ها $N + K$ زوج است، دارای راه‌حل هستند.

با این حال، تمام این اثبات‌ها بسیار پیچیده بودند.

در سال ۱۹۹۹، Archer اثبات بسیار ساده‌تری ارائه داد (می‌توانید مقاله‌ی او را از اینجا دانلود کنید).

مسائل تمرینی