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

Como resolvo o problema conhecido como knight's tour usando backtracking?

+2 votos
46 visitas
perguntada Mai 24, 2017 em Ciência da Computação por IgorNascimento (51 pontos)  

Como resolvo o problema conhecido como knight's tour usando backtracking?

Compartilhe

1 Resposta

+2 votos
respondida Mai 24, 2017 por IgorNascimento (51 pontos)  
editado Jul 5, 2017 por IgorNascimento

O knight's tour é o problema do xadrez que consiste em transportar uma peça com movimentos exclusivos da peça cavalo ao longo de todo o tabuleiro, 8x8.

Os movimentos do cavalo são feitos em formato de "L" para qualquer direção e sentido.
Para gerar todos os movimentos possíveis é necessário identificar 3 etapas:

  1. escolha da direção de movimentação: vertical (V) ou horizontal (H);
    A imagem será apresentada aqui.
  2. escolha do sentido de movimentação condicionada a (1): cima (V), baixo (V), direita (H) e esquerda (H);
  3. avanço em 2 casas do tabuleiro;
    A imagem será apresentada aqui.
  4. determinação da movimentação oposta a primeira direção (1). Ex.: Se (1) é (V), então (4) é (H);
    A imagem será apresentada aqui.
  5. escolha do sentido de movimentação condicionada a (4): cima (V), baixo (V), direita (H) e esquerda (H);
  6. avanço em 1 casas do tabuleiro;
    A imagem será apresentada aqui.

A primeira parte da rotina deve adicionar todas as posições de movimentos possíveis a partir de uma posição 'x' e 'y' a um objeto na estrutura de pilha contendo as visitas a serem feitas , representado por 'myStack', limitados em um tabuleiro de dimensão 'k' :

def movs_knight(x,y,k,myStack):
    for v in range(0,2):              # vertical = 0 , horizontal = 1
        for s in range(0,2):          #  cima ou direita = 0 , baixo ou esquerda = 1
            for p in range(0,2):      #  cima ou direita = 0 , baixo ou esquerda = 1
                x1 = x+(1-v)*((-1)**(s))*2 + v *((-1)**(1- p))*1 
                y1 = y+(v)*((-1)**(1-s))*2 + (1-v) *((-1)**(1 - p))*1
                if(x1 > -1 and x1 < k  and y1 > -1 and y1 < k):
                    myStack.push([x1 , y1])

A segunda parte da rotina estabelece a estrutura de backtracking para que os movimentos passem por todos as casas do tabuleiro. Os parâmetros:

  1. 'x' e 'y' indicam o ponto atual do cavalo;
  2. 'k' é a dimensão do tabuleiro;
  3. 'myStack' é o objeto pilha;
  4. 'tabuleiro' é uma matriz que guarda a ordem de visita das 'casas' no preenchimento do tabuleiro, sendo 0 as não visitadas;
  5. 'cont' é a ordem de visita atual;
  6. 'cor' é um parâmetro para colorir o 'gif';
  7. 'size' é o tamanho da aresta de cada quadrado, 'casa', do tabuleiro.

A função é:

def knight(x,y,k,myStack,tabuleiro,cont,cor,size):
    escreve(size,cont,x,y,cores[cor]) 
    tabuleiro[x,y] = str(cont)
    movs_knight(x,y,k,myStack)
    for i in range(0,len(myStack)):
        x0 = myStack.top()[0] 
        y0 = myStack.top()[1] 
        if tabuleiro[x0,y0] == 0:
            knight(x0,y0,k,myStack,tabuleiro,cont+1,cor,size)
            myStack.pop()
        else:
            myStack.pop()
    return(tabuleiro)

Nesse ponto, definir uma classe de objeto tipo pilha:

class Stack:
    def __init__(self):
        self.__stack=[]
    def __len__(self):
        return len(self.__stack)
    def is_empty(self):
        return len(self.__stack)==0
    def push(self,element):
        self.__stack.append(element)
    def pop(self):
        if(self.is_empty()):
            raise('Stack is empty')
        else:
            return self.__stack.pop()
    def top(self):
        if(self.is_empty()):
            raise('Stack is empty')
        else:
            return self.__stack[-1]

A programação a seguir cria o tabuleiro de xadrez:

def square(size,alternative,color):
    greg.color(color)
    greg.begin_fill()
    for i in range(4):
        greg.fd(size)
        greg.lt(90)
    greg.end_fill()
    greg.fd(size)

def row(size,alternative,color1,color2,dim):
    for i in range(int(dim)):
        if(alternative==True):
            square(size,alternative,color1)
            alternative = False
        else:
            square(size,alternative,color2)
            alternative = True      

Nesse ponto, ao final da criação do tabuleiro, é chamada a função com os movimentos do cavalo. Imagem utilizada para ilustrar os movimentos do cavalo foram baixadas no site e editadas.

Os parâmetros gerais de chamada são:

  1. size: tamanho do quadrado
  2. alternative: boolean que identifica a primeira cor do tabuleiro sendo color1
  3. color1: cor número 1 (preto)
  4. color1: cor número 1 (branco)
  5. dim: tamanho do tabuleiro
  6. x0 e y0, posição inicial de saída do cavalo

O função que realiza o processo total é:

def chessboard(size,alternative,color1,color2,dim,x0,y0):
    greg.pu()
    greg.goto(-(size*4),(size*4))
    for i in range(dim):
        row(size,alternative,color1,color2,dim)
        greg.bk(size*dim)
        greg.rt(90)
        greg.fd(size)
        greg.lt(90)
        if(alternative==True):
            alternative = False
        else:
            alternative = True
    wn.addshape("horse.gif")
    greg.shape("horse.gif")
    greg.shapesize(1, 1, 0)
    cont = 1
    myStack=Stack()
    tabuleiro     = np.zeros((dim,dim),dtype='int')
    cor = 0 #red
    tabuleiro     = knight(x0,y0,dim,myStack,tabuleiro,cont,cor,size) # Alteração para o comentário de Cauê em (05/07/2017)

A função a seguir registra o caminho feito pelo cavalo:

def escreve(size,number,x0,y0,color):
    greg.penup() 
    greg.goto(-(size*4) + size/2 + x0*size,(size*4)  + size/2 - y0*size )
    greg.pencolor(color)
    greg.width(2)
    greg.pendown()
    greg.fd(size/2)
    greg.write(str(number), font=("Arial", 15, "normal"), align="right")
    greg.rt(180)
    greg.fd(size/2)
    greg.rt(180)

A programação a seguir apresenta as bibliotecas utilizadas e a chamada geral para solução do problema.

import numpy as np
import turtle 
cores = ['red','yellow','pink','green','blue','gray']

if __name__ == '__main__': 

    wn = turtle.Screen()
    wn.bgcolor('lightblue')
    wn.title('Chessboard')
    greg=turtle.Turtle()
    greg.speed(10)
    chessboard(50,True,'black','white',8,0,0)

A imagem a seguir apresenta a ilustração final do processo, sendo os números a sequência ordenada dos movimentos no tabuleiro.
A imagem será apresentada aqui.

Para acessar a gif animado clique aqui.

comentou Jun 19, 2017 por Peng Yaohao (101 pontos)  
Ótima solução: bem detalhada, inteligível mesmo para quem nunca jogou xadrez. O gif final ficou bem elucidativo.

Os elementos da solução foram bem apresentados, essa é uma aplicação bem divertida da estrutura de pilha (stack); talvez seria interessante discutir um pouco sobre a estratégia do backtracking em si - a ideia de se poder voltar atrás até a última "escolha errada" (nesse caso, a inexistência de movimentos válidos para casas ainda não visitadas, sem que todas tenham sido visitadas), e conservar o que estiver certo, isso ilustra bem a ideia de uma pilha (LIFO: *last in, first out*).

O *knight tour* é um caso específico do problema de se encontrar um **ciclo Hamiltoniano** - ou seja, um caminho no qual todos os vértices de um grafo são visitados uma vez. Há uma variante mais exigente do *knight tour* que exige um ciclo fechado, no qual o cavalo volta para a casa de saída após visitar todas as casas do tabuleiro; por exemplo, a solução apresentada no gif foi um ciclo aberto (da casa "64" não seria possível voltar para a casa "1" com apenas um movimento).

Uma discussão mais aprofundada sobre a existência de ciclos fechados e/ou abertos do *knight tour* pode ser encontrada em http://gaebler.us/share/Knight_tour.html . O autor faz as demonstrações utilizando indução.
comentou Jul 5, 2017 por Caue (226 pontos)  
Você poderia colocar ao final da resposta o código completo? Fiquei com dificuldade de executar o código. Por exemplo, o método knight definido acima recebe 8 parâmetros, porém na chamada dele no método chessboard são passados 10 parâmetros.
comentou Jul 5, 2017 por IgorNascimento (51 pontos)  
Segue programação completa para tabuleiro de 8 casas:

import numpy as np
import turtle
cores = ['red','yellow','pink','green','blue','gray']

def movs_knight(x,y,k,myStack):
    for v in range(0,2):              # vertical = 0 , horizontal = 1
        for s in range(0,2):          #  cima ou direita = 0 , baixo ou esquerda = 1
            for p in range(0,2):      #  cima ou direita = 0 , baixo ou esquerda = 1
                x1 = x+(1-v)*((-1)**(s))*2 + v *((-1)**(1- p))*1
                y1 = y+(v)*((-1)**(1-s))*2 + (1-v) *((-1)**(1 - p))*1
                if(x1 > -1 and x1 < k  and y1 > -1 and y1 < k):
                    myStack.push([x1 , y1])
                    
                    
def knight(x,y,k,myStack,tabuleiro,cont,cor,size):
    escreve(size,cont,x,y,cores[cor])
    tabuleiro[x,y] = str(cont)
    movs_knight(x,y,k,myStack)
    for i in range(0,len(myStack)):
        x0 = myStack.top()[0]
        y0 = myStack.top()[1]
        if tabuleiro[x0,y0] == 0:
            knight(x0,y0,k,myStack,tabuleiro,cont+1,cor,size)
            myStack.pop()
        else:
            myStack.pop()
    return(tabuleiro)

class Stack:
    def __init__(self):
        self.__stack=[]
    def __len__(self):
        return len(self.__stack)
    def is_empty(self):
        return len(self.__stack)==0
    def push(self,element):
        self.__stack.append(element)
    def pop(self):
        if(self.is_empty()):
            raise('Stack is empty')
        else:
            return self.__stack.pop()
    def top(self):
        if(self.is_empty()):
            raise('Stack is empty')
        else:
            return self.__stack[-1]
def square(size,alternative,color):
    greg.color(color)
    greg.begin_fill()
    for i in range(4):
        greg.fd(size)
        greg.lt(90)
    greg.end_fill()
    greg.fd(size)

def row(size,alternative,color1,color2,dim):
    for i in range(int(dim)):
        if(alternative==True):
            square(size,alternative,color1)
            alternative = False
        else:
            square(size,alternative,color2)
            alternative = True

def chessboard(size,alternative,color1,color2,dim,x0,y0):
    greg.pu()
    greg.goto(-(size*4),(size*4))
    for i in range(dim):
        row(size,alternative,color1,color2,dim)
        greg.bk(size*dim)
        greg.rt(90)
        greg.fd(size)
        greg.lt(90)
        if(alternative==True):
            alternative = False
        else:
            alternative = True
    wn.addshape("horse.gif")
    greg.shape("horse.gif")
    greg.shapesize(1, 1, 0)
    cont = 1
    myStack=Stack()
    tabuleiro     = np.zeros((dim,dim),dtype='int')
    cor = 0 #red
    tabuleiro     = knight(x0,y0,dim,myStack,tabuleiro,cont,cor,size)
    
    
def escreve(size,number,x0,y0,color):
    greg.penup()
    greg.goto(-(size*4) + size/2 + x0*size,(size*4)  + size/2 - y0*size )
    greg.pencolor(color)
    greg.width(2)
    greg.pendown()
    greg.fd(size/2)
    greg.write(str(number), font=("Arial", 15, "normal"), align="right")
    greg.rt(180)
    greg.fd(size/2)
    greg.rt(180)
    
if __name__ == '__main__':

    wn = turtle.Screen()
    wn.bgcolor('lightblue')
    wn.title('Chessboard')
    greg=turtle.Turtle()
    greg.speed(10)
    chessboard(50,True,'black','white',8,0,0)
...