Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o puzzle "Instant Insanity" usando backtracking?

+1 voto
103 visitas
perguntada Jul 6, 2016 em Ciência da Computação por Camila (31 pontos)  

O problema consiste em empilhar quatro cubos com faces de diferentes cores de forma que em cada lado da pilha a cor de um cubo não seja repetida por outro.

A imagem será apresentada aqui.

Compartilhe

1 Resposta

0 votos
respondida Jul 6, 2016 por Camila (31 pontos)  

Uma implementação possível usando python é apresentada no código abaixo.

Para solucionar o puzzle considero a classe cube, que define os cubos do jogo e seus movimentos possíveis (girar no sentido horário e girar para trás). Os elementos da lista que define cada cubo representam, em ordem, as faces frontal, direita, traseira, esquerda, superior e inferior. Considero, ainda, que o jogo será resolvido com os cubos empilhados, então para gerar uma solução precisamos comparar as faces direita, esquerda, frontal e traseira, que representam cada lado da pilha. A função isLegal verifica se as posições atuais dos cubos geram uma solução. Por fim, defino as 24 possíveis posições de cada objeto e a solução testando todas posições possíveis para os cubos.

    class cube:
    def __init__(self,facelist):
        self.facelist=facelist

    def __getitem__(self,key):
        return self.facelist[key]

    def turn_clockwise(self):
        return cube([self.facelist[1],self.facelist[2],self.facelist[3],self.facelist[0],self.facelist[4],self.facelist[5]])

    def turn_backwards(self):
        return cube([self.facelist[5],self.facelist[1],self.facelist[4],self.facelist[3],self.facelist[0],self.facelist[2]])

    def print_cube(self):
        facedict={}
        facedict['front']=self.facelist[0]
        facedict['right']=self.facelist[1]
        facedict['back']=self.facelist[2]
        facedict['left']=self.facelist[3]
        facedict['up']=self.facelist[4]
        facedict['down']=self.facelist[5]
        print facedict

def isLegal(cubes): 
    islegal=True    
    n=len(cubes)   
    for i in range(0,4): 
        for j in range(1,n):
            for k in range(0,j):
                if cubes[j][i]==cubes[k][i]:
                    islegal=False
    return islegal

def positions(cube):
    positions=[]
    k=0
    while k<4:
        j=0
        while j<4:
            cube=cube.turn_clockwise()
            positions.append(cube)
            j=j+1
        cube=cube.turn_backwards()
        k=k+1
    cube=cube.turn_clockwise()
    cube=cube.turn_backwards()
    j=0
    while j<4:
        cube=cube.turn_clockwise()
        positions.append(cube)
        j=j+1
    cube=cube.turn_backwards()
    cube=cube.turn_backwards()
    j=0
    while j<4:
        cube=cube.turn_clockwise()
        positions.append(cube)
        j=j+1    
    return positions

def getSolution(cubes):
    positions1=positions(cubes[0])
    positions2=positions(cubes[1])    
    positions3=positions(cubes[2])
    positions4=positions(cubes[3])
    for i in range(len(positions1)):
        cubes[0]=positions1[i]
        for j in range(len(positions2)):
            cubes[1]=positions2[j]
            for k in range(len(positions3)):
                cubes[2]=positions3[k]
                for l in range(len(positions4)):
                    cubes[3]=positions4[l]
                    if isLegal(cubes):
                        for cube in cubes:
                            cube.print_cube()
                        break
                if isLegal(cubes):
                    break
            if isLegal(cubes):
                break
        if isLegal(cubes):
            break

if __name__ == '__main__':
    #0:front,1:right,2:back,3:left,4:up,5:down
    cube1=cube(['blue','yellow','red','blue','green','green'])
    cube2=cube(['green','red','yellow','blue','red','yellow'])
    cube3=cube(['red','yellow','green','blue','green','yellow'])
    cube4=cube(['yellow','red','blue','red','green','red'])

    cubes=[cube1,cube2,cube3,cube4]

    getSolution(cubes)
...