El juego de rompecabezas Magnets implica colocar un conjunto de imanes en forma de dominó (o electrets u otros objetos polarizados) en un subconjunto de ranuras en un tablero para satisfacer un conjunto de restricciones. Por ejemplo, el rompecabezas de la izquierda tiene la solución que se muestra a la derecha:
Cada ranura contiene una entrada en blanco (indicada por ‘x’) o un «imán» con un extremo positivo y otro negativo. Los números a lo largo de los lados izquierdo y superior muestran los números de cuadrados ‘+’ en filas o columnas particulares. Los que están a la derecha y abajo muestran el número de signos ‘-‘ en filas o columnas particulares. Las filas y columnas sin un número en uno o ambos extremos no tienen restricciones en cuanto al número de signos ‘+’ o ‘-‘, según el número que no esté presente. Además de cumplir con estas restricciones numéricas, la solución de un rompecabezas también debe satisfacer la restricción de que dos cuadrados que se tocan ortogonalmente no pueden tener el mismo signo (los cuadrados unidos en diagonal no están restringidos).
Se le proporcionan las arrays superior [], inferior [], izquierda [], derecha [] que indican el recuento de + o – a lo largo de los bordes superior (+), inferior (-), izquierdo (+) y derecho (-) respectivamente. Los valores de -1 indican cualquier número de signos + y –. También las reglas de array dadas[][] contienen cualquier carácter T, B, L o R. Para una ranura vertical en el tablero, T indica su extremo superior y B indica el extremo inferior. Para una ranura horizontal en el tablero, L indica el extremo izquierdo y R indica el extremo derecho.
Ejemplos:
Input : M = 5, N = 6
top[] = { 1, -1, -1, 2, 1, -1 }
bottom[] = { 2, -1, -1, 2, -1, 3 }
left[] = { 2, 3, -1, -1, -1 }
right[] = { -1, -1, -1, 1, -1 }
rules[][] = { { L, R, L, R, T, T },
{ L, R, L, R, B, B },
{ T, T, T, T, L, R },
{ B, B, B, B, T, T },
{ L, R, L, R, B, B }};
Output : + - + - X -
- + - + X +
X X + - + -
X X - + X +
- + X X X -
Input : M = 4, N = 3
top[] = { 2, -1, -1 }
bottom[] = { -1, -1, 2 }
left[] = { -1, -1, 2, -1 }
right[] = { 0, -1, -1, -1 }
rules[][] = { { T, T, T },
{ B, B, B },
{ T, L, R },
{ B, L, R } };
Output : + X +
– X –
+ – +
– + –
Podemos resolver este problema usando Backtracking .
# Write Python3 code here M = 5 N = 6 top = [ 1, -1, -1, 2, 1, -1 ] bottom = [ 2, -1, -1, 2, -1, 3 ] left = [ 2, 3, -1, -1, -1 ] right = [ -1, -1, -1, 1, -1 ] rules = [["L","R","L","R","T","T" ], [ "L","R","L","R","B","B" ], [ "T","T","T","T","L","R" ], [ "B","B","B","B","T","T" ], [ "L","R","L","R","B","B" ]]; def canPutPatternHorizontally(rules,i,j,pat): if j-1>=0 and rules[i][j-1] == pat[0]: return False elif i-1>=0 and rules[i-1][j] == pat[0]: return False elif i-1>=0 and rules[i-1][j+1] == pat[1]: return False elif j+2 < len(rules[0]) and rules[i][j+2] == pat[1]: return False return True def canPutPatternVertically(rules,i,j,pat): if j-1>=0 and rules[i][j-1] == pat[0]: return False elif i-1>=0 and rules[i-1][j] == pat[0]: return False elif j+1 < len(rules[0]) and rules[i][j+1] == pat[0]: return False return True def doTheStuff(rules,i,j): if rules[i][j] == "L" or rules[i][j] == "R": # option 1 +- if canPutPatternHorizontally(rules,i,j,"+-"): rules[i][j] = "+" rules[i][j+1] = "-" solveMagnets(rules,i,j) # option 2 -+ # option 3 xx def checkConstraints(rules): pCountH = [0 for i in range(len(rules))] nCountH = [0 for i in range(len(rules))] for row in range(len(rules)): for col in range(len(rules[0])): ch = rules[row][col] if ch == "+": pCountH[row] += 1 elif ch == "-": nCountH[row] += 1 pCountV = [0 for i in range(len(rules[0]))] nCountV = [0 for i in range(len(rules[0]))] for col in range(len(rules[0])): for row in range(len(rules)): ch = rules[row][col] if ch == "+": pCountV[col] += 1 elif ch == "-": nCountV[col] += 1 for row in range(len(rules)): if left[row] != -1: if pCountH[row] != left[row]: return False if right[row] != -1: if nCountH[row] != right[row]: return False for col in range(len(rules[0])): if top[col] != -1: if pCountV[col] != top[col]: return False if bottom[col] != -1: if nCountV[col] != bottom[col]: return False # # if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) : # return False return True def solveMagnets(rules,i,j): if i == len(rules) and j == 0: # check the constraint before printing if checkConstraints(rules): print(rules) elif j >= len(rules[0]): solveMagnets(rules,i+1,0) # normal cases else: if rules[i][j] == "L": # option 1 +- if canPutPatternHorizontally(rules,i,j,"+-"): rules[i][j] = "+" rules[i][j+1] = "-" solveMagnets(rules,i,j+2) rules[i][j] = "L" rules[i][j+1] = "R" # option 2 -+ if canPutPatternHorizontally(rules,i,j,"-+"): rules[i][j] = "-" rules[i][j+1] = "+" solveMagnets(rules,i,j+2) rules[i][j] = "L" rules[i][j+1] = "R" # option 3 xx if True or canPutPatternHorizontally(rules,i,j,"xx"): rules[i][j] = "x" rules[i][j+1] = "x" solveMagnets(rules,i,j+2) rules[i][j] = "L" rules[i][j+1] = "R" # vertical check elif rules[i][j] == "T": # option 1 +- if canPutPatternVertically(rules,i,j,"+-"): rules[i][j] = "+" rules[i+1][j] = "-" solveMagnets(rules,i,j+1) rules[i][j] = "T" rules[i+1][j] = "B" # option 2 -+ if canPutPatternVertically(rules,i,j,"-+"): rules[i][j] = "-" rules[i+1][j] = "+" solveMagnets(rules,i,j+1) rules[i][j] = "T" rules[i+1][j] = "B" # option 3 xx if True or canPutPatternVertically(rules,i,j,"xx"): rules[i][j] = "x" rules[i+1][j] = "x" solveMagnets(rules,i,j+1) rules[i][j] = "T" rules[i+1][j] = "B" else: solveMagnets(rules,i,j+1) # Driver code solveMagnets(rules,0,0)
Fuente: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/f2012-contest.pdf
Este artículo es una contribución de Anuj Chauhan (anuj0503) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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