¿Qué es 8 rompecabezas?
Dado un tablero de 3×3 con 8 fichas (cada ficha tiene un número del 1 al 8) y un espacio vacío. El objetivo es colocar los números en los mosaicos en orden usando el espacio vacío. Podemos deslizar cuatro fichas adyacentes (izquierda, derecha, arriba y abajo) en el espacio vacío
¿Cómo encontrar si el estado dado es solucionable?
Los siguientes son dos ejemplos, el primer ejemplo puede alcanzar el estado objetivo mediante una serie de diapositivas. El segundo ejemplo no puede.
La siguiente es una regla simple para verificar si un rompecabezas de 8 se puede resolver.
No es posible resolver una instancia de 8 rompecabezas si el número de inversiones es impar en el estado de entrada.
En los ejemplos dados en la figura anterior, el primer ejemplo tiene 10 inversiones, por lo tanto, solucionable. El segundo ejemplo tiene 11 inversiones, por lo tanto irresoluble.
¿Qué es la inversión?
Un par de fichas forman una inversión si los valores de las fichas están en orden inverso al de su aparición en el estado objetivo. Por ejemplo, la siguiente instancia del rompecabezas 8 tiene dos inversiones, (8, 6) y (8, 7).
1 2 3 4 _ 5 8 6 7
Las siguientes son las implementaciones para verificar si una instancia dada de 8 rompecabezas se puede resolver o no. La idea es simple, contamos inversiones en el rompecabezas de 8 dado.
C++
// C++ program to check if a given instance of 8 puzzle is solvable or not
#include <iostream>
using namespace std;
// A utility function to count inversions in given array '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++)
// Value 0 is used for empty space
if (arr[j] && arr[i] && arr[i] > arr[j])
inv_count++;
return inv_count;
}
// This function returns true if given 8 puzzle is solvable.
bool isSolvable(int puzzle[3][3])
{
// Count inversions in given 8 puzzle
int invCount = getInvCount((int *)puzzle);
// return true if inversion count is even.
return (invCount%2 == 0);
}
/* Driver program to test above functions */
int main()
{
int puzzle[3][3] = {{1, 8, 2},
{0, 4, 3}, // Value 0 is used for empty space
{7, 6, 5}};
isSolvable(puzzle)? cout << "Solvable":
cout << "Not Solvable";
return 0;
}
Java
// Java program to check if a given
// instance of 8 puzzle is solvable or not
class GFG
{
// A utility function to count
// inversions in given array 'arr[]'
static int getInvCount(int[] arr)
{
int inv_count = 0;
for (int i = 0; i < 9; i++)
for (int j = i + 1; j < 9; j++)
// Value 0 is used for empty space
if (arr[i] > 0 &&
arr[j] > 0 && arr[i] > arr[j])
inv_count++;
return inv_count;
}
// This function returns true
// if given 8 puzzle is solvable.
static boolean isSolvable(int[][] puzzle)
{
int linearPuzzle[];
linearPuzzle = new int[9];
int k = 0;
// Converting 2-D puzzle to linear form
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
linearPuzzle[k++] = puzzle[i][j];
// Count inversions in given 8 puzzle
int invCount = getInvCount(linearPuzzle);
// return true if inversion count is even.
return (invCount % 2 == 0);
}
/* Driver code */
public static void main (String[] args)
{
int[][] puzzle = {{1, 8, 2},{0, 4, 3},{7, 6, 5}};
// in linear
if(isSolvable(puzzle))
System.out.println("Solvable");
else
System.out.println("Not Solvable");
}
}
Python3
# Python3 program to check if a given
# instance of 8 puzzle is solvable or not
# A utility function to count
# inversions in given array 'arr[]'
def getInvCount(arr):
inv_count = 0
empty_value = -1
for i in range(0, 9):
for j in range(i + 1, 9):
if arr[j] != empty_value and arr[i] != empty_value and arr[i] > arr[j]:
inv_count += 1
return inv_count
# This function returns true
# if given 8 puzzle is solvable.
def isSolvable(puzzle) :
# Count inversions in given 8 puzzle
inv_count = getInvCount([j for sub in puzzle for j in sub])
# return true if inversion count is even.
return (inv_count % 2 == 0)
# Driver code
puzzle = [[8, 1, 2],[-1, 4, 3],[7, 6, 5]]
if(isSolvable(puzzle)) :
print("Solvable")
else :
print("Not Solvable")
# This code is contributed by vitorhugooli
# Fala meu povo desse Brasil varonil 😉
C#
// C# program to check if a given
// instance of 8 puzzle is solvable or not
using System;
class GFG
{
// A utility function to count
// inversions in given array 'arr[]'
static int getInvCount(int[] arr)
{
int inv_count = 0;
for (int i = 0; i < 9; i++)
for (int j = i + 1; j < 9; j++)
// Value 0 is used for empty space
if (arr[i] > 0 && arr[j] > 0 && arr[i] > arr[j])
inv_count++;
return inv_count;
}
// This function returns true
// if given 8 puzzle is solvable.
static bool isSolvable(int[,] puzzle)
{
int[] linearForm;
linearForm = new int[9];
int k = 0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
linearForm[k++] = puzzle[i, j];
// Count inversions in given 8 puzzle
int invCount = getInvCount(linearForm);
// return true if inversion count is even.
return (invCount % 2 == 0);
}
/* Driver code */
static void Main()
{
int[,] puzzle = new int[3,3]{{1, 8, 2},
{0, 4, 3}, // Value 0 is used for empty space
{7, 6, 5}};
if(isSolvable(puzzle))
Console.WriteLine("Solvable");
else
Console.WriteLine("Not Solvable");
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP program to check if
// a given instance of 8
// puzzle is solvable or not
// A utility function to
// count inversions in
// given array '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;
}
// This function returns true
// if given 8 puzzle is solvable.
function isSolvable($puzzle)
{
// Count inversions in
// given 8 puzzle
$invCount = getInvCount($puzzle);
// return true if
// inversion count is even.
return ($invCount % 2 == 0);
}
// Driver Code
$puzzle = array(array(1, 8, 2),
array(0, 4, 3), // Value 0 is used
array(7, 6, 5));// for empty space
if(isSolvable($puzzle) == true)
echo "Solvable";
else
echo "Not Solvable";
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to check if a given
// instance of 8 puzzle is solvable or not
// A utility function to count inversions
// in given array 'arr[]'
function getInvCount(arr)
{
let inv_count = 0 ;
for(let i=0;i<2;i++){
for(let j=i+1;j<3;j++){
// Value 0 is used for empty space
if (arr[j][i] > 0 && arr[j][i] > arr[i][j])
inv_count += 1;
}
}
return inv_count;
}
// This function returns true
// if given 8 puzzle is solvable.
function isSolvable(puzzle)
{
// Count inversions in given 8 puzzle
let invCount = getInvCount(puzzle);
// return true if inversion count is even.
return (invCount % 2 == 0);
}
// Driver code
// Value 0 is used for empty space
puzzle = [[1, 8, 2],[0, 4, 3],[7, 6, 5]] ;
if(isSolvable(puzzle))
document.write("Solvable");
else
document.write("Not Solvable");
</script>
Solvable
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Tenga en cuenta que la implementación anterior utiliza un algoritmo simple para el recuento de inversiones. Se hace de esta manera por simplicidad. El código se puede optimizar a O (nLogn) utilizando el algoritmo basado en la ordenación por combinación para el recuento de inversión .
¿Como funciona esto?
La idea se basa en el hecho de que la paridad de las inversiones sigue siendo la misma después de una serie de movimientos, es decir, si el recuento de inversiones es impar en la etapa inicial, entonces permanece impar después de cualquier secuencia de movimientos y si el recuento de inversiones es par, entonces permanece incluso después de cualquier secuencia de movimientos. En el estado objetivo, hay 0 inversiones. Entonces, podemos alcanzar el estado objetivo solo desde un estado que tiene un recuento de inversión par.
¿Cómo es invariante la paridad del conteo de inversiones?
Cuando deslizamos un mosaico, hacemos un movimiento de fila (moviendo un mosaico de izquierda o derecha al espacio en blanco) o hacemos un movimiento de columna (moviendo un mosaico hacia arriba o hacia abajo al espacio en blanco).
a) Un movimiento de fila no cambia el conteo de inversión. Ver siguiente ejemplo
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
b) Un movimiento de columna hace uno de los siguientes tres.
…..(i) Aumenta el recuento de inversión en 2. Consulte el siguiente ejemplo.
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) Disminuye el conteo de inversión por 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) Mantiene la cuenta de inversión igual.
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
Entonces, si un movimiento aumenta/disminuye el recuento de inversión en 2, o mantiene el mismo recuento de inversión, entonces no es posible cambiar la paridad de un estado mediante ninguna secuencia de movimientos de fila/columna.
Ejercicio: Cómo verificar si una instancia dada de 15 rompecabezas es solucionable o no. En un rompecabezas de 15, tenemos un tablero de 4×4 donde 15 fichas tienen un número y un espacio vacío. Tenga en cuenta que las reglas simples anteriores de conteo de inversión no funcionan directamente para 15 rompecabezas, las reglas deben modificarse para 15 rompecabezas.
Artículo relacionado: ¿Cómo verificar si una instancia de 15 rompecabezas se puede resolver?
Este artículo es una contribución de Ishan . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA