Как проверить, разрешима ли головоломка из 15?

Опубликовано: 20 Января, 2022

Дана доска 4 × 4 с 15 плитками (каждая плитка имеет одно число от 1 до 15) и одним пустым местом. Цель состоит в том, чтобы расположить числа на плитках по порядку, используя пустое пространство. Мы можем вставить четыре соседних плитки (слева, справа, сверху и снизу) в пустое пространство. Например,

Здесь X отмечает место, где элементы могут быть перемещены, а окончательная конфигурация всегда остается той же, что и головоломка.
В общем, для данной сетки шириной N мы можем проверить, разрешима ли головоломка N * N - 1 или нет, следуя приведенным ниже простым правилам:

Если N нечетно, то экземпляр головоломки разрешим, если количество инверсий четное во входном состоянии.
Если N четно, экземпляр головоломки разрешим, если
- пробел находится в четной строке, считая снизу (вторая-последняя, четвертая-последняя и т. д.), а количество инверсий нечетное.
- пробел находится в нечетной строке, считая снизу (последняя, третья-последняя, пятая-последняя и т. д.), а количество инверсий четное.
Во всех остальных случаях экземпляр головоломки не разрешим.

Что здесь за инверсия?
Если мы предположим, что плитки записаны в одной строке (1D Array), а не распределены по N строкам (2D Array), пара плиток (a, b) образует инверсию, если a появляется перед b, но a> b.
Для примера выше рассмотрим плитки, написанные в ряд, например:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 Х
Приведенная выше сетка образует только одну инверсию, т.е. (2, 1).
Иллюстрация:

Below is a simple C++ program to check whether a given instance of 15 puzzle is solvable or not. The program is generic and can be extended to any grid width.

C++

// C++ program to check if a given instance of N*N-1
// puzzle is solvable or not
#include <iostream>
#define N 4
using namespace std;
 
// A utility function to count inversions in given
// array "arr[]". Note that this function can be
// optimized to work in O(n Log n) time. The idea
// here is to keep code small and simple.
int getInvCount(int arr[])
{
    int inv_count = 0;
    for (int i = 0; i < N * N - 1; i++)
    {
        for (int j = i + 1; j < N * N; j++)
        {
            // count pairs(i, j) such that i appears
            // before j, but i > j.
            if (arr[j] && arr[i] && arr[i] > arr[j])
                inv_count++;
        }
    }
    return inv_count;
}
 
// find Position of blank from bottom
int findXPosition(int puzzle[N][N])
{
    // start from bottom-right corner of matrix
    for (int i = N - 1; i >= 0; i--)
        for (int j = N - 1; j >= 0; j--)
            if (puzzle[i][j] == 0)
                return N - i;
}
 
// This function returns true if given
// instance of N*N - 1 puzzle is solvable
bool isSolvable(int puzzle[N][N])
{
    // Count inversions in given puzzle
    int invCount = getInvCount((int*)puzzle);
 
    // If grid is odd, return true if inversion
    // count is even.
    if (N & 1)
        return !(invCount & 1);
 
    else     // grid is even
    {
        int pos = findXPosition(puzzle);
        if (pos & 1)
            return !(invCount & 1);
        else
            return invCount & 1;
    }
}
 
/* Driver program to test above functions */
int main()
{
 
    int puzzle[N][N] =
    {
        {12, 1, 10, 2},
        {7, 11, 4, 14},
        {5, 0, 9, 15}, // Value 0 is used for empty space
        {8, 13, 6, 3},
    };
    /*
    int puzzle[N][N] = {{1, 8, 2},
                    {0, 4, 3},
                    {7, 6, 5}};
 
    int puzzle[N][N] = {
                    {13, 2, 10, 3},
                    {1, 12, 8, 4},
                    {5, 0, 9, 6},
                    {15, 14, 11, 7},
                };
 
    int puzzle[N][N] = {
                    {6, 13, 7, 10},
                    {8, 9, 11, 0},
                    {15, 2, 12, 5},
                    {14, 3, 1, 4},
                };
 
 
    int puzzle[N][N] = {
                    {3, 9, 1, 15},
                    {14, 11, 4, 6},
                    {13, 0, 10, 12},
                    {2, 7, 8, 5},
                };
    */
 
    isSolvable(puzzle)? cout << "Solvable":
                        cout << "Not Solvable";
    return 0;
}

PHP

<?php
//PHP  program to check if a given instance of N*N-1
// puzzle is solvable or not
 
$N= 4;
 
// A utility function to count inversions in given
// array "arr[]". Note that this function can be
// optimized to work in O(n Log n) time. The idea
// here is to keep code small and simple.
 
function  getInvCount( $arr)
{
    global $N;
     $inv_count = 0;
    for ($i = 0; $i < $N * $N - 1; $i++)
    {
        for ($j = $i + 1; $j < $N * $N; $j++)
        {
            // count pairs(i, j) such that i appears
            // before j, but i > j.
 
                $inv_count++;
        }
    }
    return $inv_count;
}
 
// find Position of blank from bottom
function findXPosition($puzzle)
{
    global $N;
    // start from bottom-right corner of matrix
    for ($i = $N - 1; $i >= 0; $i--)
        for ($j = $N - 1; $j >= 0; $j--)
            if ($puzzle[$i][$j] == 0)
                return $N - $i;
}
 
// This function returns true if given
// instance of N*N - 1 puzzle is solvable
function  isSolvable( $puzzle)
{
    global $N;
    // Count inversions in given puzzle
    $invCount = getInvCount($puzzle);
 
    // If grid is odd, return true if inversion
    // count is even.
    if ($N & 1)
        return !($invCount & 1);
 
    else     // grid is even
    {
        $pos = findXPosition($puzzle);
        if ($pos & 1)
            return !($invCount & 1);
        else
            return $invCount & 1;
    }
}
 
/* Driver program to test above functions */
 
 
    $puzzle =
    array(
        array(12, 1, 10, 2),
        array(7, 11, 4, 14),
        array(5, 0, 9, 15), // Value 0 is used for empty space
        array(8, 13, 6, 3),
    );
     
 
    if(isSolvable($puzzle)==0)
     
            echo  "Solvable";
     else
            echo  "Not Solvable";
 
 
#This code is contributed by aj_36
?>

Output

Solvable

Алгоритмы

Как проверить, разрешима ли головоломка из 15?

C++

PHP

РЕКОМЕНДУЕМЫЕ СТАТЬИ