Rompecabezas magnético | Retrocediendo-9

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *