Рубрики

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

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

Как определить, является ли данное состояние разрешимым?
Ниже приведены два примера, первый пример может достичь целевого состояния с помощью серии слайдов. Второй пример не может.

Следующее простое правило — проверить, разрешима ли головоломка 8.
Невозможно решить задачу из 8 головоломок, если число инверсий нечетно во входном состоянии. В примерах, приведенных на рисунке выше, первый пример имеет 10 инверсий, следовательно, разрешимых. Во втором примере 11 инверсий, поэтому неразрешимы.

Что такое инверсия?
Пара плиток образует инверсию, если значения на плитках находятся в обратном порядке их появления в целевом состоянии. Например, следующий экземпляр 8 головоломки имеет две инверсии, (8, 6) и (8, 7).

   1   2   3
   4   _   5
   8   6   7      

Ниже приведены реализации, позволяющие проверить, является ли данный экземпляр головоломки 8 решаемым или нет. Идея проста, мы считаем инверсии в данной 8 головоломки.

C ++

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

using namespace std;

  
// Утилита для подсчета инверсий в указанном массиве 'arr []'

int getInvCount(int arr[])

{

    int inv_count = 0;

    for (int i = 0; i < 9 - 1; i++)

        for (int j = i+1; j < 9; j++)

             // Значение 0 используется для пустого места

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

                  inv_count++;

    return inv_count;

}

  
// Эта функция возвращает true, если заданная головоломка 8 разрешима.

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

{

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

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

  

    // вернуть true, если счетчик инверсии четный.

    return (invCount%2 == 0);

}

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

int main(int argv, int** args)

{

  int puzzle[3][3] =  {{1, 8, 2},

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

                      {7, 6, 5}};

  isSolvable(puzzle)? cout << "Solvable":

                      cout << "Not Solvable";

  return 0;

}

Джава

// Java-программа для проверки, если данный
// экземпляр 8 головоломки решаем или нет

class GFG

      
// Полезная функция для подсчета
// инверсии в данном массиве 'arr []'

static int getInvCount(int[][] arr)

{

    int inv_count = 0;

    for (int i = 0; i < 3 - 1; i++)

        for (int j = i + 1; j < 3; j++)

          

            // Значение 0 используется для пустого места

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

                            arr[j][i] > arr[i][j])

                inv_count++;

    return inv_count;

}

  
// Эта функция возвращает true
// если дано 8 головоломка разрешима.

static boolean isSolvable(int[][] puzzle)

{

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

    int invCount = getInvCount(puzzle);

  

    // вернуть true, если счетчик инверсии четный.

    return (invCount % 2 == 0);

}

  
/ * Код водителя * /

public static void main (String[] args) 

{

    int[][] puzzle = {{1, 8, 2},{0, 4, 3},{7, 6, 5}};

    if(isSolvable(puzzle))

        System.out.println("Solvable");

    else

    System.out.println("Not Solvable");

}
}

  
// Этот код предоставлен chandan_jnu

C #

// C # программа для проверки, если данный
// экземпляр 8 головоломки решаем или нет

using System;

  

class GFG

      
// Полезная функция для подсчета
// инверсии в данном массиве 'arr []'

static int getInvCount(int[,] arr)

{

    int inv_count = 0;

    for (int i = 0; i < 3 - 1; i++)

        for (int j = i + 1; j < 3; j++)

          

            // Значение 0 используется для пустого места

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

                inv_count++;

    return inv_count;

}

  
// Эта функция возвращает true
// если дано 8 головоломка разрешима.

static bool isSolvable(int[,] puzzle)

{

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

    int invCount = getInvCount(puzzle);

  

    // вернуть true, если счетчик инверсии четный.

    return (invCount % 2 == 0);

}

  
/ * Код водителя * /

static void Main()

{

    int[,] puzzle = new int[3,3]{{1, 8, 2},

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

                            {7, 6, 5}};

    if(isSolvable(puzzle))

        Console.WriteLine("Solvable");

    else

       Console.WriteLine("Not Solvable");

}
}

  
// Этот код предоставлен chandan_jnu

PHP

<?php
// PHP программа для проверки
// данный экземпляр 8
// головоломка разрешима или нет

  
// Функция полезности для
// считать инверсии в
// данный массив 'arr []'

function getInvCount($arr)

{

    $inv_count = 0;

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

        for ( $j = $i + 1; $j < 9; $j++)

                $inv_count++;

    return $inv_count;

}

  
// Эта функция возвращает true
// если дано 8 головоломка разрешима.

function isSolvable($puzzle)

{

    // Считаем инверсии в

    // дано 8 головоломок

    $invCount = getInvCount($puzzle);

  

    // вернуть true, если

    // счет инверсии четный

    return ($invCount % 2 == 0);

}

  
// Код драйвера

$puzzle = array(array(1, 8, 2),

                array(0, 4, 3), // используется значение 0

                array(7, 6, 5));// для пустого места

                  

if(isSolvable($puzzle) == true) 

            echo "Solvable";

        else

            echo "Not Solvable";

                  
// Этот код предоставлен ajit
?>


Выход :

Solvable

Обратите внимание, что в приведенной выше реализации используется простой алгоритм подсчета инверсии. Это сделано для простоты. Код можно оптимизировать до O (nLogn), используя алгоритм сортировки слиянием для подсчета инверсий .

Как это работает?
Идея основана на том факте, что четность инверсий остается неизменной после ряда ходов, т. Е. Если счет инверсии нечетен на начальной стадии, то он остается нечетным после любой последовательности ходов, а если счет инверсии четен, то он остается даже после любой последовательности ходов. В состоянии цели есть 0 инверсий. Таким образом, мы можем достичь целевого состояния только из состояния, в котором есть даже счет инверсии.

Насколько четность числа инверсий инвариантна?
Когда мы перемещаем плитку, мы либо перемещаем строку (перемещая левую или правую плитку в пустое пространство), либо перемещаем столбец (перемещая плитку вверх или вниз в пустое пространство).
а) движение строки не меняет счет инверсии. Смотрите следующий пример

   1   2   3    Row Move     1   2   3
   4   _   5   ---------->   _   4   5 
   8   6   7                 8   6   7
  Inversion count remains 2 after the move

   1   2   3    Row Move     1   2   3
   4   _   5   ---------->   4   5   _
   8   6   7                 8   6   7
  Inversion count remains 2 after the move

б) перемещение столбца выполняет одно из следующих трех.
… .. (i) Увеличивает количество инверсий на 2. См. Следующий пример.

         1   2   3   Column Move     1   _   3
         4   _   5   ----------->    4   2   5  
         8   6   7                   8   6   7
      Inversion count increases by 2 (changes from 2 to 4)
       

… .. (ii) Уменьшает количество инверсий на 2

         1   3   4    Column Move     1   3   4
         5   _   6   ------------>    5   2   6
         7   2   8                    7   _   8
      Inversion count decreases by 2 (changes from 5  to 3)

… .. (iii) Сохраняет количество инверсий одинаковым.

         1   2   3    Column Move     1   2   3
         4   _   5   ------------>    4   6   5
         7   6   8                    7   _   8
        Inversion count remains 1 after the move 

Таким образом, если перемещение либо увеличивает / уменьшает счет инверсии на 2, либо сохраняет счет инверсии одинаковым, то невозможно изменить четность состояния с помощью любой последовательности перемещений строки / столбца.

Упражнение: Как проверить, является ли данный экземпляр головоломки 15 решаемым или нет. В 15 головоломках у нас есть доска 4х4, где 15 плиток имеют номер и одно пустое место. Обратите внимание, что приведенные выше простые правила подсчета инверсий не работают напрямую для 15 головоломок, правила необходимо изменить для 15 головоломок.

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

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

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

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

0.00 (0%) 0 votes