时间戳

首页 > 解决方案 > 经典骑士之旅问题，1 个单元未访问

python - 经典骑士之旅问题，1 个单元未访问

问题描述

我正在尝试使用 Backtracking 解决 Knight 的旅行，Knight 必须访问所有单元格无论如何我总是有 1 个单元格未被访问。4x4 chessBoard 大小的示例，我得到的输出为：

1 8 13 10

14 11 4 7

5 2 9 12

0 15 6 3

如您所见，最左下角的单元格始终未被访问。我该如何修复它以便它访问所有单元格。下面是我的代码：

import sys
from pandas import *
class knightTour:

    xMoves = [2, 1, -1, -2, -2, -1, 1, 2] 
    yMoves = [1, 2, 2, 1, -1, -2, -2, -1] 

    def KT(self,size):
        self.size=size
        visited = [[0 for i in range(size) ]for i in range(size)]

        visited[0][0]=1

        if(self.solveKT(visited,2,0,0)):
            self.printSolution(visited)
        else:
            print("No solution Found")
    
    def solveKT(self,visited,moveCount,x,y):
        if(moveCount == self.size**2):
            return True
        
        for i in range(8):
            nextX= x+self.xMoves[i]
            nextY= y+self.yMoves[i]



            if self.isValidMove(visited,nextX,nextY):
                
                visited[nextX][nextY] = moveCount

                if(self.solveKT(visited,moveCount+1,nextX,nextY)):
                    return True
                

                visited[nextX][nextY]=0
            
        return False

    def isValidMove(self,visited,x,y):
        n=len(visited)
        if x >= 0 and y >= 0 and x < n and y < n and visited[x][y]==0:
            return True
        else:
            return False
        
    def printSolution(self,visited):
        print(DataFrame(visited))
        
        # for i in range(len(visited)):
        #     print(visited[i])
        # print("\n")

obj=knightTour()
obj.KT(4)

标签： pythonalgorithmdata-structurespuzzleknights-tour

解决方案

更改这部分代码：

if(moveCount == self.size**2+1):
          return True

此外，对于从位置 [0][0] 开始的 4x4 板没有解决方案，但此代码适用于 8x8 板。

推荐阅读