Dado un tablero de 4×4 con 15 fichas (cada ficha tiene un número del 1 al 15) 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. Por ejemplo,
Aquí X marca el lugar donde se pueden cambiar los elementos y la configuración final siempre permanece igual, el rompecabezas se puede resolver.
En general, para una cuadrícula dada de ancho N, podemos averiguar si un rompecabezas N*N – 1 se puede resolver o no siguiendo las siguientes reglas simples:
- Si N es impar, entonces la instancia del rompecabezas se puede resolver si el número de inversiones es par en el estado de entrada.
- Si N es par, la instancia del rompecabezas se puede resolver si
- el espacio en blanco está en una fila par contando desde abajo (penúltimo, penúltimo, etc.) y el número de inversiones es impar.
- el espacio en blanco está en una fila impar contando desde abajo (último, penúltimo, quinto-último, etc.) y el número de inversiones es par.
- Para todos los demás casos, la instancia del rompecabezas no se puede resolver.
¿Qué es una inversión aquí?
Si asumimos que las fichas están escritas en una sola fila (array 1D) en lugar de distribuirse en filas N (array 2D), un par de fichas (a, b) forman una inversión si a aparece antes que b pero a > b.
Para el ejemplo anterior, considere las fichas escritas en una fila, así:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 X
La cuadrícula anterior forma solo 1 inversión, es decir, (2, 1).
Ilustración:
A continuación se muestra un programa simple de C++ para verificar si una instancia dada de 15 rompecabezas se puede resolver o no. El programa es genérico y se puede extender a cualquier ancho de cuadrícula.
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(arr[i], arr[j]) such that
// i < j but arr[i] > arr[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(arr[i], arr[j]) such that
// i < j but arr[i] > arr[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
?>
Python3
# Python3 program to check if a given instance of N*N-1
# puzzle is solvable or not
# A utility function to count inversions in given
# array . 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.
N=4
def getInvCount(arr):
arr1=[]
for y in arr:
for x in y:
arr1.append(x)
arr=arr1
inv_count = 0
for i in range(N * N - 1):
for j in range(i + 1,N * N):
# count pairs(arr[i], arr[j]) such that
# i < j and arr[i] > arr[j]
if (arr[j] and arr[i] and arr[i] > arr[j]):
inv_count+=1
return inv_count
# find Position of blank from bottom
def findXPosition(puzzle):
# start from bottom-right corner of matrix
for i in range(N - 1,-1,-1):
for j in range(N - 1,-1,-1):
if (puzzle[i][j] == 0):
return N - i
# This function returns true if given
# instance of N*N - 1 puzzle is solvable
def isSolvable(puzzle):
# 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
if __name__ == '__main__':
puzzle =[
[12, 1, 10, 2,],
[7, 11, 4, 14,],
[5, 0, 9, 15,], # Value 0 is used for empty space
[8, 13, 6, 3,],]
print("Solvable") if isSolvable(puzzle) else print("Not Solvable")
Solvable
Tiempo Complejidad : O(n 2 )
Complejidad espacial : O(n)
¿Cómo funciona esto?
Hecho 1: para una cuadrícula de ancho impar, todos los movimientos legales conservan la polaridad (par o impar) del número de inversiones.
Prueba del hecho 1
- Mover un mosaico a lo largo de la fila (izquierda o derecha) no cambia el número de inversiones y, por lo tanto, no cambia su polaridad.
- Mover un mosaico a lo largo de la columna (hacia arriba o hacia abajo) puede cambiar el número de inversiones. La ficha se mueve más allá de un número par de otras fichas (N – 1). Así que mover aumenta/disminuye el conteo de inversiones en 2, o mantiene el mismo conteo de inversiones.
Hecho 2: Para una cuadrícula de ancho uniforme, lo siguiente es invariable: (#inversions even) == (en blanco en la fila impar desde abajo).
Ejemplo: Considere el movimiento anterior. El número de inversiones a la izquierda es 49 y el espacio en blanco está en una fila par desde abajo. Entonces el valor del invariante es “falso == falso”, que es verdadero. El número de inversiones de la derecha es 48, porque el 11 ha perdido dos inversiones, pero el 14 ha ganado una. El espacio en blanco está en una fila impar desde la parte inferior. Entonces, el valor del invariante es «verdadero == verdadero», que sigue siendo verdadero.
Prueba de hecho 2
- Mover una ficha a lo largo de la fila (izquierda o derecha) no cambia el número de inversiones y no cambia la fila del espacio en blanco.
- Mover un mosaico a lo largo de la columna (hacia arriba o hacia abajo) cambia el número de inversiones. La ficha se mueve más allá de un número impar de otras fichas (N – 1). Entonces, el número de inversiones cambia un número impar de veces. La fila del espacio en blanco también cambia, de impar a par o de par a impar. Así que ambas mitades de los cambios invariantes. Por lo que su valor se conserva.
Combinando Hecho 1 + Hecho 2 = Hecho 3:
- Si el ancho es impar, entonces cada estado solucionable tiene un número par de inversiones.
Si el ancho es par, entonces cada estado solucionable tiene- un número par de inversiones si el espacio en blanco está en una fila impar contando desde abajo;
- un número impar de inversiones si el espacio en blanco está en una fila con un número par contando desde abajo;
Prueba del hecho 3:
- El estado inicial (resuelto) tiene esas propiedades.
- Esas propiedades se conservan por cada movimiento legal.
- Se puede llegar a cualquier estado solucionable desde el estado inicial mediante alguna secuencia de movimientos legales.
Artículo relacionado:
¿Cómo verificar si una instancia de 8 rompecabezas se puede resolver?
Fuente:
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
Este artículo es una contribución de Aditya Goel . 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