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

Como resolver o quebra-cabeça "Solitaire peg puzzle" ou "Resta-um" usando backtracking?

+1 voto
1,078 visitas
perguntada Mai 21, 2016 em Ciência da Computação por Saulo (436 pontos)  

[Solitaire peg puzzle] Esse quebra cabeça é jogado em um tabuleiro com 15 pequenos buracos arranjados conforme um triângulo equilátero, conforme figura a seguir:

\(
\begin{array}{ccccccccc}
~ & ~ & ~ & ~ & \bullet & ~ & ~ & ~ & ~ \\[-2mm]
~ & ~ & ~ & ~ & 0 & ~ & ~ & ~ & ~ \\
~ & ~ & ~ & \bullet & ~ & \bullet & ~ & ~ & ~ \\[-2mm]
~ & ~ & ~ & 1 & ~ & 2 & ~ & ~ & ~ \\
~ & ~ & \bullet & ~ & \bullet & ~ & \bullet & ~ & ~ \\[-2mm]
~ & ~ & 3 & ~ & 4 & ~ & 5 & ~ & ~ \\
~ & \bullet & ~ & \bullet & ~ & \bullet & ~ & \bullet & ~ \\[-2mm]
~ & 6 & ~ & 7 & ~ & 8 & ~ & 9 & ~ \\
\bullet & ~ & \bullet & ~ & \circ & ~ & \bullet & ~ & \bullet \\[-2mm]
10 & ~ & 11 & ~ & 12 & ~ & 13 & ~ & 14
\end{array}
\)

Na situação inicial, todos os buracos, menos um (o doze), estão preenchidos com pinos. Um movimento permitido no jogo é um pino pular um outro que é seu vizinho para ir parar no lado oposto. Esse movimento remove o pino que foi saltado do tabuleiro. Projeto um programa usando backtracking para resolver os seguintes problemas:
(a) Ache a menor sequência de movimentos que elimina todos os pinos menos um.
(b) Ache a menor sequência de movimentos que elimina todos os pinos menos um e o pino final vai parar no buraco 12.
Discuta a sua solução para o problema.

Compartilhe

1 Resposta

+1 voto
respondida Mai 21, 2016 por Saulo (436 pontos)  

A solução deste problema utilizará a técnica de backtracking (capítulo 12.1 do livro "Introduction to the Design and Analysis of Algorithms", de Anany Levitin). Para eliminar todos os pinos menos um, deve-se eliminar 14 pinos e, portanto, efetuar 13 movimentos. A solução é dada pelos seguintes passos:
1) Escolhe-se o nó raiz, que representa o estado inicial do tabuleiro antes da busca pela solução;
2) Para cada movimento possível no estado atual do tabuleiro, move-se um pino e mantém-se o novo estado do tabuleiro. Se tem-se apenas um pino sobrando, e a posição do pino remanescente é a desejada, então chegou-se na solução final. Se há mais de um pino sobrando, então: (a) se existem movimentos possíveis, a solução é promissora, então este tabuleiro será usado para a próxima rodada na busca pela solução; (b) se não existem mais movimentos possíveis, retorna-se (ou "backtracks") para o último estado que tinha uma solução promissora e tenta-se outro movimento.

Para eliminar a exploração desnecessária de nós, podemos ainda usar a simetria do problema. O algoritmo não precisa explorar situações que são simétricas, pois fornecerão a mesma solução.

O código-fonte encontra-se abaixo. Seguem alguns comentários sobre o mesmo:
- A classe "TriangleSolitairePegBoard" implementa o tabuleiro, que possui uma lista de buracos (classe "Hole"). A posição inicial padrão que não possui pino é a 12, mas pode-se facilmente alterar isto por meio da variável "initialHolePositionWithoutAPeg". Esta classe possui os seguinte métodos principais: "getAllPossibleMoves", que retorna uma lista com todos os movimentos possíveis (posições de origem e destino); "movePeg", que movimenta um pino de uma posição de origem para outra de destino; "pegsLeft", que retorna a quantidade de pinos remanescentes; "isSymmetric", que retorna se o tabuleiro é simétrico com relação à outro tabuleiro, abrangendo tanto a simetria do tabuleiro (o estado que ele se encontra), quanto a simetria dos movimentos necessários para chegar no estado.
- A classe "Hole" implementa o buraco do tabuleiro, que possui uma referência para o tabuleiro, a sua posição no tabuleiro e se possui um pino (variável "peg"). O método "getPossibleJumps" retorna os movimentos válidos do buraco, sendo que o buraco "i" chama o método "__getPossibleJumps_i" que possui apenas os movimentos válidos do buraco "i". O método "isJumpAllowed" verifica se a movimentação no buraco é válida, ou seja, se o buraco possui um pino, se a posição de destino está vazia e se a posição que está sendo pulada possui um pino.
- A classe "Node" implementa um nó, que possui um tabuleiro em um estado determinado. Pode-se usar a variável "lastPegPosition" para definir a posição desejada do último pino (ou -1 caso seja qualquer uma). O método "isSolution" retorna se o estado atual do tabuleiro é uma solução, ou seja, se, em 13 movimentos, existe apenas um pino sobrando e, se for o caso, se o pino encontra-se na posição desejada. O método "isPromissing" indica se o tabuleiro atual é uma possível solução.
- No main, a variável "solutionsLimit" limita a quantidade de soluções que o usuário deseja obter se for um número inteiro positivo (ou -1 caso queira retornar todas as soluções possíveis). No caso em questão, vamos mostrar apenas 1 solução fazendo "solutionsLimit=1". A variável "lastPegPosition" indica posição final desejada se for um número inteiro maior ou igual a zero (ou -1 caso queira se retornar a primeira solução que se encontre, sem importar a posição final do último pino). Para a letra (a), vamos usar "lastPegPosition=-1"; para a letra (b), vamos usar "lastPegPosition=12".

Código-fonte em Python:

from collections import deque
import copy

class TriangleSolitairePegBoard:
    def __init__(self, initialHolePositionWithoutAPeg = 12):
        self.holes = list(Hole(self, i, int(i!=initialHolePositionWithoutAPeg)) for i in range(15))

        self.__initialHolePositionWithoutAPeg = initialHolePositionWithoutAPeg

        self.__pegRemovalHistory = list()

        self.__symmetricPositionMap = dict()
        self.__initSymmetricPositionMap()

        return

    def __getitem__(self, key):
        if ((key >= 0) and (key < len(self.holes))):
            return self.holes[key]
        return None

    def __initSymmetricPositionMap(self):
        self.__symmetricPositionMap[0] = 0
        self.__symmetricPositionMap[1] = 2
        self.__symmetricPositionMap[2] = 1
        self.__symmetricPositionMap[3] = 5
        self.__symmetricPositionMap[4] = 4
        self.__symmetricPositionMap[5] = 3
        self.__symmetricPositionMap[6] = 9
        self.__symmetricPositionMap[7] = 8
        self.__symmetricPositionMap[8] = 7
        self.__symmetricPositionMap[9] = 6
        self.__symmetricPositionMap[10] = 14
        self.__symmetricPositionMap[11] = 13
        self.__symmetricPositionMap[12] = 12
        self.__symmetricPositionMap[13] = 11
        self.__symmetricPositionMap[14] = 10
        return

    def movePeg(self, originHolePosition, targetHolePosition):
        if (self.holes[originHolePosition].isJumpAllowed(targetHolePosition)):
            jump = self.holes[originHolePosition].getJumpPossibility(targetHolePosition)
            jumpedHolePosition = jump[1]
            self.holes[originHolePosition].peg = 0
            self.holes[jumpedHolePosition].peg = 0
            self.holes[targetHolePosition].peg = 1

            self.__pegRemovalHistory.append((originHolePosition, targetHolePosition))

        return

    def getAllPossibleMoves(self):
        possibleJumps = list()
        for originHole in self.holes:
            allowedJumps = originHole.getAllowedJumps()

            if (len(allowedJumps) > 0):
                for allowedJump in allowedJumps:
                    targetHolePosition = allowedJump[0]
                    possibleJumps.append((originHole.position, targetHolePosition))

        return possibleJumps

    def areThereAnyMovesLeft(self):
        return len(self.getAllPossibleMoves()) > 0

    def __str__(self):
        boardStr = ' '*4 + str(self.holes[0]) + ' '*4 + '\n'
        boardStr += ' '*3 + str(self.holes[1]) + ' ' + str(self.holes[2]) + ' '*3 + '\n'
        boardStr += ' '*2 + str(self.holes[3]) + ' ' + str(self.holes[4]) + ' ' + str(self.holes[5]) + ' '*2 + '\n'
        boardStr += ' ' + str(self.holes[6]) + ' ' + str(self.holes[7]) + ' ' + str(self.holes[8]) + ' ' + str(self.holes[9]) + ' ' + '\n'
        boardStr += str(self.holes[10]) + ' ' + str(self.holes[11]) + ' ' + str(self.holes[12]) + ' ' + str(self.holes[13]) + ' ' + str(self.holes[14])
        return boardStr

    def pegsLeft(self):
        pegs = 0
        for hole in self.holes:
            pegs += hole.peg
        return pegs

    def firstPegPosition(self):
        for hole in self.holes:
            if (hole.peg == 1):
                return hole.position
        return -1

    def printHistory(self):
        board = TriangleSolitairePegBoard(self.__initialHolePositionWithoutAPeg)
        print "Situacao inicial"
        print board
        print ""

        for move in self.__pegRemovalHistory:
            print "Mover o pino de ", move[0], " para ", move[1]
            board.movePeg(move[0], move[1])
            print board
            print ""
        return

    def clone(self):
        board = TriangleSolitairePegBoard(self.__initialHolePositionWithoutAPeg)
        for k in range(len(board.holes)):
            board.holes[k].peg = self.holes[k].peg

        board.__pegRemovalHistory = copy.deepcopy(self.__pegRemovalHistory)

        return board

    def isSymmetric(self, otherBoard):
        positionsAreSymmetric = (self.holes[0].peg == otherBoard.holes[0].peg) and \
            (self.holes[1].peg == otherBoard.holes[2].peg) and (self.holes[2].peg == otherBoard.holes[1].peg) and \
            (self.holes[3].peg == otherBoard.holes[5].peg) and (self.holes[5].peg == otherBoard.holes[3].peg) and \
            (self.holes[4].peg == otherBoard.holes[4].peg) and \
            (self.holes[6].peg == otherBoard.holes[9].peg) and (self.holes[9].peg == otherBoard.holes[6].peg) and \
            (self.holes[7].peg == otherBoard.holes[8].peg) and (self.holes[8].peg == otherBoard.holes[7].peg) and \
            (self.holes[10].peg == otherBoard.holes[14].peg) and (self.holes[14].peg == otherBoard.holes[10].peg) and \
            (self.holes[11].peg == otherBoard.holes[13].peg) and (self.holes[13].peg == otherBoard.holes[11].peg) and \
            (self.holes[12].peg == otherBoard.holes[12].peg)

        movementsAreSymmetric = False
        if (positionsAreSymmetric and (len(self.__pegRemovalHistory) == len(otherBoard.__pegRemovalHistory))):
            movementsAreSymmetric = True
            for k in range(len(self.__pegRemovalHistory)):
                move = self.__pegRemovalHistory[k]
                otherMove = otherBoard.__pegRemovalHistory[k]

                movementsAreSymmetric = movementsAreSymmetric and \
                    (self.__symmetricPositionMap[move[0]]==otherMove[0]) and (self.__symmetricPositionMap[move[1]]==otherMove[1]) and \
                    (move[0]==self.__symmetricPositionMap[otherMove[0]]) and (move[1]==self.__symmetricPositionMap[otherMove[1]])

                if (not movementsAreSymmetric):
                    break

        return positionsAreSymmetric and movementsAreSymmetric

class Hole:
    def __init__(self, board, position, peg = 0):
        self.board = board
        self.position = position
        self.peg = peg
        self.__possibleJumps = list()
        self.__jumpPossibilitiesMap = dict()
        return

    def getPossibleJumps(self):
        getPossibleJumpsFunction = getattr(self, '_getPossibleJumps_'+str(self.position))
        return getPossibleJumpsFunction()

    def getJumpPossibility(self, targetHolePosition):
        for jump in self.getPossibleJumps():
            if (jump[0] == targetHolePosition):
                return jump
        return (-1,-1)

    def getJumpedPosition(self, nextPosition):
        return self.getJumpPossibility(nextPosition)[1]

    def getAllowedJumps(self):
        allowedJumps = list()
        if (self.peg == 1):
            possibleJumps = self.getPossibleJumps()
            for possibleJump in possibleJumps:
                targetHolePosition = possibleJump[0]
                jumpedHolePosition = possibleJump[1]
                if ((self.board.holes[targetHolePosition].peg==0) and (self.board.holes[jumpedHolePosition].peg==1)):
                    allowedJumps.append(possibleJump)
        return allowedJumps

    def isJumpAllowed(self, targetHolePosition):
        if (self.peg == 1):
            possibleJump = self.getJumpPossibility(targetHolePosition)
            targetHolePosition = possibleJump[0]
            jumpedHolePosition = possibleJump[1]
            return ((self.board.holes[targetHolePosition].peg==0) and (self.board.holes[jumpedHolePosition].peg==1))
        return False

    def __str__(self):
        if (self.peg == 1):
            return 'x'
        else:
            return 'o'

    def _getPossibleJumps_0(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((3,1))
            self.__possibleJumps.append((5,2))
        return self.__possibleJumps

    def _getPossibleJumps_1(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((6,3))
            self.__possibleJumps.append((8,4))
        return self.__possibleJumps

    def _getPossibleJumps_2(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((7,4))
            self.__possibleJumps.append((9,5))
        return self.__possibleJumps

    def _getPossibleJumps_3(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((0,1))
            self.__possibleJumps.append((5,4))
            self.__possibleJumps.append((10,6))
            self.__possibleJumps.append((12,7))
        return self.__possibleJumps

    def _getPossibleJumps_4(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((11,7))
            self.__possibleJumps.append((13,8))
        return self.__possibleJumps

    def _getPossibleJumps_5(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((0,2))
            self.__possibleJumps.append((3,4))
            self.__possibleJumps.append((12,8))
            self.__possibleJumps.append((14,9))
        return self.__possibleJumps

    def _getPossibleJumps_6(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((1,3))
            self.__possibleJumps.append((8,7))
        return self.__possibleJumps

    def _getPossibleJumps_7(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((2,4))
            self.__possibleJumps.append((9,8))
        return self.__possibleJumps

    def _getPossibleJumps_8(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((1,4))
            self.__possibleJumps.append((6,7))
        return self.__possibleJumps

    def _getPossibleJumps_9(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((2,5))
            self.__possibleJumps.append((7,8))
        return self.__possibleJumps

    def _getPossibleJumps_10(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((3,6))
            self.__possibleJumps.append((12,11))
        return self.__possibleJumps

    def _getPossibleJumps_11(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((4,7))
            self.__possibleJumps.append((13,12))
        return self.__possibleJumps

    def _getPossibleJumps_12(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((3,7))
            self.__possibleJumps.append((5,8))
            self.__possibleJumps.append((10,11))
            self.__possibleJumps.append((14,13))
        return self.__possibleJumps

    def _getPossibleJumps_13(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((4,8))
            self.__possibleJumps.append((11,12))
        return self.__possibleJumps

    def _getPossibleJumps_14(self):
        if (len(self.__possibleJumps)==0):
            self.__possibleJumps.append((5,9))
            self.__possibleJumps.append((12,13))
        return self.__possibleJumps

class Node:
    def __init__(self, board, lastPegPosition = -1, level = 0):
        self.level = level
        self.board = board
        self.lastPegPosition = lastPegPosition
        return

    def isSolution(self):
        return (self.level == 13) and (self.board.pegsLeft() == 1) and self.__lastPegPositionConditionHolds()

    def __lastPegPositionConditionHolds(self):
        return (self.lastPegPosition < 0) or ((self.lastPegPosition >= 0) and (self.lastPegPosition == self.board.firstPegPosition()))

    def isPromissing(self):
        return (self.level < 13) and self.board.areThereAnyMovesLeft()

if __name__ == '__main__':
    solutionsLimit = 1
    lastPegPosition = 12

    solutions = list()
    queue = deque()
    queue.append(Node(TriangleSolitairePegBoard(), lastPegPosition))

    while ((len(queue) > 0) and ((solutionsLimit<=0) or ((solutionsLimit>0) and (len(solutions)<solutionsLimit)))):
        currentNode = queue.popleft()

        numberOfPromissingStates = 0
        for move in currentNode.board.getAllPossibleMoves():
            originHolePosition = move[0]
            targetHolePosition = move[1]
            nextBoard = currentNode.board.clone()
            nextBoard.movePeg(originHolePosition, targetHolePosition)

            nextBoardIsSymmetricToAnotherBoard = False
            for k in range(numberOfPromissingStates):
                if (nextBoard.isSymmetric(queue[-k].board)):
                    nextBoardIsSymmetricToAnotherBoard = True
                    break

            if (not nextBoardIsSymmetricToAnotherBoard):
                nextNode = Node(nextBoard, lastPegPosition, currentNode.level + 1)
                if (nextNode.isSolution()):
                    solutions.append(nextNode)
                    if ((solutionsLimit > 0) and (len(solutions) >= solutionsLimit)):
                        break
                elif (nextNode.isPromissing()):
                    queue.append(nextNode)
                    numberOfPromissingStates += 1

    solutionCount = 0
    for node in solutions:
        solutionCount += 1
        print "Solucao ", solutionCount
        node.board.printHistory()
        print "------------------------------------------"

Saída do programa, letra (b):

Solucao  1
Situacao inicial
    x    
   x x   
  x x x  
 x x x x 
x x o x x

Mover o pino de  3  para  12
    x    
   x x   
  o x x  
 x o x x 
x x x x x

Mover o pino de  0  para  3
    o    
   o x   
  x x x  
 x o x x 
x x x x x

Mover o pino de  2  para  7
    o    
   o o   
  x o x  
 x x x x 
x x x x x

Mover o pino de  6  para  1
    o    
   x o   
  o o x  
 o x x x 
x x x x x

Mover o pino de  9  para  2
    o    
   x x   
  o o o  
 o x x o 
x x x x x

Mover o pino de  11  para  4
    o    
   x x   
  o x o  
 o o x o 
x o x x x

Mover o pino de  12  para  5
    o    
   x x   
  o x x  
 o o o o 
x o o x x

Mover o pino de  1  para  8
    o    
   o x   
  o o x  
 o o x o 
x o o x x

Mover o pino de  2  para  9
    o    
   o o   
  o o o  
 o o x x 
x o o x x

Mover o pino de  14  para  5
    o    
   o o   
  o o x  
 o o x o 
x o o x o

Mover o pino de  5  para  12
    o    
   o o   
  o o o  
 o o o o 
x o x x o

Mover o pino de  13  para  11
    o    
   o o   
  o o o  
 o o o o 
x x o o o

Mover o pino de  10  para  12
    o    
   o o   
  o o o  
 o o o o 
o o x o o

------------------------------------------
...