2
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ I've spent hours debugging trying to resolve it, but failed. So the code is not working as expected, which makes the question off-topic here. \$\endgroup\$ – 409_Conflict Nov 20 '17 at 14:51
  • \$\begingroup\$ @MathiasEttinger I hadn't even noticed that... , but this is one of those cases where it seems to work. If we do not focus on the bug, but on the code itself, is it on-topic then? \$\endgroup\$ – Ludisposed Nov 20 '17 at 15:09
  • 1
    \$\begingroup\$ @Ludisposed Unfortunately it's in black and white that they only want us to fix the bug - "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. " And so violates the "To the best of my knowledge, does the code work as intended?" reason. \$\endgroup\$ – Peilonrayz Nov 20 '17 at 15:15
  • \$\begingroup\$ Thanks for the comments. I've tried StackOverflow before coming here, which wasn't very helpful, 2 mins 2 downvotes and suggested to close... Just wondered, where is appropriate to put this kind of question? @Peilonrayz \$\endgroup\$ – Logan Nov 20 '17 at 22:29
  • \$\begingroup\$ @Logan stackoverflow seems appropriate. Maybe the wording wasn't clear enough? \$\endgroup\$ – 409_Conflict Nov 21 '17 at 8:45
2
\$\begingroup\$

I don't have much to say about this, only a few small nitpicks.

  1. self.height might be a better name, (width and height) make more sense to me. But this might be subjective.
  2. At is_ligit_move() you could use, elem in range(), because range is special. See this excellent description by @Graipher for more details.
  3. 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!

\$\endgroup\$
1
\$\begingroup\$

Few more observations:

  • there is a typo: avaiable_moves -> available_moves
  • available_moves() might become a generator:

    def available_moves(self, cell):
        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):
                yield elem
    
  • to take it further, that tmp variable could be replaced with a bit more robust cell combination generation mechanism:

    def available_moves(self, cell):
        row, column = cell
        for offset_row, offset_column in product((1, -1), (2, -2)):
            for new_cell in [(row + offset_row, column + offset_column),
                             (column + offset_column, row + offset_row)]:
                if self.is_legit_move(new_cell):
                    yield new_cell
    

    Don't forget to add the import statement from itertools import product.

    Note that product((1, -1), (2, -2)) part should be pre-calculated and be configured as a constant, no reason to re-do it every time available_moves() is called.

  • I would also question the if next_cell not in path part. Since path is a tuple, checking for next_cell presence/absence would take \$O(n)\$ time-complexity wise, where n for a chess board is 64 which for 8x8 board is probably not a problem. But, for a general board, it would possibly make more sense to sacrifice some space and introduce a seen set of visited cell (presence check would then take constant time) and use it to check if you've already visited a set or not

\$\endgroup\$
  • \$\begingroup\$ Great addidtions, but why not in range()? Instead of x <= row <= y. I liked the new available_moves much smoother \$\endgroup\$ – Ludisposed Nov 20 '17 at 14:37
  • \$\begingroup\$ @Ludisposed ah, yeah, in range() would be a better option, removed that part from the answer. Thanks. \$\endgroup\$ – alecxe Nov 20 '17 at 14:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.