Python - Knight's tour recursive function 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 &gt;= 0 and row &lt;= self.width-1) and (col &gt;=0 and col &lt;= 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
I don't have much to say about this, only a few small nitpicks.


self.height might be a better name, (width and height) make more sense to me. But this might be subjective.
At is_ligit_move() you could use, elem in range(), because range is special. See this excellent description by @Graipher for more details.
At available_moves you could use list comprehension instead of the res variable


So your res would be this:

return [elem for elem in possible_moves if self.is_legit_move(elem)]

It does the same but looks a little cleaner. See PEP202 for more information.



Overall I think you have crafted a nice piece of code!