Рубрики

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

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

Здесь X отмечает место, куда элементы могут быть сдвинуты, и окончательная конфигурация всегда остается той же самой, головоломка разрешима.

В общем, для данной сетки ширины N мы можем выяснить, является ли головоломка N * N — 1 разрешимой или нет, следуя приведенным ниже простым правилам:

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

Что здесь инверсия?
Если мы предположим, что листы записаны в один ряд (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 X
Вышеуказанная сетка образует только 1 инверсию, т.е. (2, 1).

Иллюстрация:

Ниже приведена простая программа на C ++, позволяющая проверить, является ли данный экземпляр головоломки 15 решаемым или нет. Программа является общей и может быть расширена до любой ширины сетки.

C ++

// C ++ программа для проверки, является ли данный экземпляр N * N-1
// головоломка разрешима или нет
#include <iostream>
#define N 4

using namespace std;

  
// Полезная функция для подсчета инверсий в заданном
// массив 'arr []'. Обратите внимание, что эта функция может быть
// оптимизирован для работы за O (n Log n) времени. Идея
// здесь, чтобы сделать код маленьким и простым.

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++)

        {

            // считать пары (i, j) так, чтобы я появился

            // до j, но я> j.

            if (arr[j] && arr[i] && arr[i] > arr[j])

                inv_count++;

        }

    }

    return inv_count;

}

  
// находим позицию пробела снизу

int findXPosition(int puzzle[N][N])

{

    // начать с правого нижнего угла матрицы

    for (int i = N - 1; i >= 0; i--)

        for (int j = N - 1; j >= 0; j--)

            if (puzzle[i][j] == 0)

                return N - i;

}

  
// Эта функция возвращает true, если дано
// экземпляр N * N - 1 головоломка разрешима

bool isSolvable(int puzzle[N][N])

{

    // Считаем инверсии в заданной головоломке

    int invCount = getInvCount((int*)puzzle);

  

    // Если сетка нечетная, вернуть true, если инверсия

    // количество четное

    if (N & 1)

        return !(invCount & 1);

  

    else     // сетка четная

    {

        int pos = findXPosition(puzzle);

        if (pos & 1)

            return !(invCount & 1);

        else

            return invCount & 1;

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  

    int puzzle[N][N] =

    {

        {12, 1, 10, 2},

        {7, 11, 4, 14},

        {5, 0, 9, 15}, // Значение 0 используется для пустого места

        {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-программа для проверки, является ли данный экземпляр N * N-1
// головоломка разрешима или нет

  

$N= 4;

  
// Полезная функция для подсчета инверсий в заданном
// массив 'arr []'. Обратите внимание, что эта функция может быть
// оптимизирован для работы за O (n Log n) времени. Идея
// здесь, чтобы сделать код маленьким и простым.

  

function  getInvCount( $arr)

{

    global $N;

     $inv_count = 0;

    for ($i = 0; $i < $N * $N - 1; $i++)

    {

        for ($j = $i + 1; $j < $N * $N; $j++)

        {

            // считать пары (i, j) так, чтобы я появился

            // до j, но я> j.

  

                $inv_count++;

        }

    }

    return $inv_count;

}

  
// находим позицию пробела снизу

function findXPosition($puzzle)

{

    global $N;

    // начать с правого нижнего угла матрицы

    for ($i = $N - 1; $i >= 0; $i--)

        for ($j = $N - 1; $j >= 0; $j--)

            if ($puzzle[$i][$j] == 0)

                return $N - $i;

}

  
// Эта функция возвращает true, если дано
// экземпляр N * N - 1 головоломка разрешима

function  isSolvable( $puzzle)

{

    global $N;

    // Считаем инверсии в заданной головоломке

    $invCount = getInvCount($puzzle);

  

    // Если сетка нечетная, вернуть true, если инверсия

    // количество четное

    if ($N & 1)

        return !($invCount & 1);

  

    else     // сетка четная

    {

        $pos = findXPosition($puzzle);

        if ($pos & 1)

            return !($invCount & 1);

        else

            return $invCount & 1;

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

  

  

    $puzzle =

    array(

        array(12, 1, 10, 2),

        array(7, 11, 4, 14),

        array(5, 0, 9, 15), // Значение 0 используется для пустого места

        array(8, 13, 6, 3),

    );

      

  

    if(isSolvable($puzzle)==0)

      

            echo  "Solvable";

     else 

            echo  "Not Solvable";

  

  
#This code is contributed by aj_36
?>


Выход :

Как это работает?

Факт 1: Для сетки нечетной ширины все допустимые ходы сохраняют полярность (четную или нечетную) числа инверсий.

Доказательство факта 1

  • Перемещение тайла по ряду (влево или вправо) не меняет количество инверсий и, следовательно, не меняет его полярность.
  • Перемещение плитки вдоль столбца (вверх или вниз) может изменить количество инверсий. Плитка движется мимо четного числа других плиток (N — 1). Таким образом, перемещение либо увеличивает / уменьшает счет инверсии на 2, либо сохраняет счет инверсии таким же.

Факт 2: Для сетки четной ширины инвариантно следующее: (#inversions even) == (пусто на нечетной строке снизу).

Пример: рассмотрим ход выше. Число инверсий слева равно 49, а пробел находится в четном ряду снизу. Таким образом, значение инварианта равно «false == false», что является истиной. Число инверсий справа равно 48, потому что 11 потерял две инверсии, а 14 получил одну. Пробел находится в нечетном ряду снизу. Таким образом, значение инварианта равно «true == true», что все еще верно.

Доказательство факта 2

  • Перемещение плитки по ряду (влево или вправо) не меняет количество инверсий и не меняет ряд пробелов.
  • Перемещение плитки вдоль столбца (вверх или вниз) меняет количество инверсий. Плитка движется мимо нечетного числа других плиток (N — 1). Таким образом, количество инверсий меняется нечетное количество раз. Строка пробела также изменяется с нечетного на четное или с четного на нечетное. Так что обе половины инвариантных изменений. Таким образом, его ценность сохраняется.

Объединяя Факт 1 + Факт 2 = Факт 3:

  • Если ширина нечетная, то каждое разрешимое состояние имеет четное число инверсий.
    Если ширина четна, то каждое разрешимое состояние имеет
    • четное число инверсий, если пробел находится в нечетном ряду, считая снизу;
    • нечетное число инверсий, если пробел находится в четном ряду, считая снизу;

Доказательство факта 3:

  • Исходное (решенное) состояние обладает этими свойствами.
  • Эти свойства сохраняются при каждом законном перемещении.
  • Любое разрешимое состояние может быть достигнуто из исходного состояния с помощью некоторой последовательности законных шагов.

Связанная статья:
Как проверить, разрешим ли экземпляр 8 головоломки?

Источник :
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

Эта статья предоставлена Aditya Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes