I realize that there’re many implementations of Knight’s tour problem suggested across webs, without jumping to those suggested solutions (most in Java, I’m not proficient in Java), I managed to implement one myself using Python. It works and returns some results.
Description
A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.
For example:
board = Board(4,4) a = list(dfs_search([0,0], tuple())) Outputs:
# a[0] ([0, 0], [2, 1], [3, 3], [0, 2], [1, 0], [3, 1], [1, 2], [2, 0], [3, 2], [1, 1], [3, 0], [2, 3], [0, 3], [2, 2], [0, 1], [1, 3]) Most of the outputs are correct, which seems that the recursive function is actually working. The last few vertex, transit from [1,1] to [3,0] is problematic. I’ve spent hours debugging trying to resolve it, but failed. As the last resort, I bring the question here, hoping anyone could shed some light to my implementation.
This is my implemntaion of Knight’s tour problem using recusive functions.
def dfs_search(start, path): if not path: path = (start,) if len(path) == board.goal: yield path for next_cell in board.avaiable_moves(start): if next_cell not in path: path += (next_cell,) yield from dfs_search(next_cell, path) class Board(object): def __init__(self, width, length): self.width = width self.length = length self.goal = width * length def is_legit_move(self, cell): row, col = cell return (row >= 0 and row <= self.width-1) and (col >=0 and col <= self.length-1) def avaiable_moves(self, cell): ret = [] r, c = cell tmp = [[r+1, c-2], [r+2, c-1], [r+2, c+1], [r+1, c+2],\ [r-1, c-2], [r-2, c-1], [r-2, c+1], [r-1, c+2]] for elem in tmp: if self.is_legit_move(elem): ret.append(elem) return ret 
