3
\$\begingroup\$

Below is my recursive solution for the Knights Tour. The user can set the board size and the program will print the first legal knight's tour it finds.

As there are potentially millions of correct solutions to the knight's tour, only one solution is given.

def legal_moves(visited, position, sq):
    """Calculate legal moves"""
    legal_moves = [
        (-2, -1),
        (-2, 1),
        (-1, -2),
        (-1, 2),
        (1, -2),
        (1, 2),
        (2, -1),
        (2, 1),
    ]

    row = position // sq
    col = position % sq

    move_to = []
    for dx, dy in legal_moves:
        if 0 <= (row + dx) < sq and 0 <= (col + dy) < sq:
            new_position = (position + (sq * dx)) + dy
            if new_position not in visited and 0 <= new_position < (sq * sq):
                move_to.append(new_position)
    return move_to


def make_move(move_to, visited, current, route, sq):
    """Carry out the move"""
    for move in move_to:
        visited.add(current)
        new_route = route + f"{current}-"
        solution_found = next_move(visited, move, new_route, sq)
        visited.remove(current)
        if solution_found:
            return True
    return False


def next_move(visited, current, route, sq):
    """Find the next valid moves and instruct "make_move" to carry them out"""
    if len(visited) == (sq * sq) - 1:
        route += f"{current}"
        print(route)
        return True
    move_to = legal_moves(visited, current, sq)
    solution_found = make_move(move_to, visited, current, route, sq)
    if solution_found:
        return True


def start_tour(sq):
    """Calculate the knights tour for  grid sq*sq starting at all positions in range 0-sq"""
    for starting in range(sq * sq):
        visited = set()
        route = ""
        solution_found = next_move(visited, starting, route, sq)
        if solution_found:
            return
    print("No knights tour could be calculated")


if __name__ == "__main__":
    square_size = 8
    start_tour(square_size)

EDIT I have added a print_route function which is called from inside next_move in place of the current print statement as follows: print_route(route, sq)

def print_route(route, size):
    """Convert the 1D array into a 2D array tracking the movement on the knight"""
    import numpy as np

    steps = route.split("-")
    array = np.zeros(size * size)

    for index, item in enumerate(steps):
        array[int(item)] = index + 1
    array = array.reshape(size, size)

    print(array)
\$\endgroup\$
3
\$\begingroup\$

Starting position

If there is a route to be found, it will go through cell 0 and will be found at first iteration of start_tour. We can remove the loop and just have starting = 0.

Generating legal moves

Various details can be improved in the legal_moves function.

This is a good occasion to use a generator with the keyword yield.

We could compute row and col with a single call to divmod.

We could make computation of new position more straight-forward with intermediates variables for coordinates on each axis.

Because of the way new_position is computed, there is no need for the additional boundary check.

We'd get something like:

def generate_new_positions(visited, position, sq):
    """Yield legal moves"""
    generate_new_positions = [
        (-2, -1),
        (-2, 1),
        (-1, -2),
        (-1, 2),
        (1, -2),
        (1, 2),
        (2, -1),
        (2, 1),
    ]
    # position = row * sq + col
    row, col = divmod(position, sq)

    for dx, dy in generate_new_positions:
        x, y = row + dx, col + dy
        if 0 <= x < sq and 0 <= y < sq:
            new_pos = x * sq + y
            if new_pos not in visited:
                yield new_pos

Separation of concerns: printing vs returning a result

When a result is found, it is printed and a boolean (or None) is returned in the different functions. It would be easier to return either None or the result found and to have that result printed from a single point of the logic.

We'd have something like:

def make_move(move_to, visited, current, route, sq):
    """Carry out the move"""
    for move in move_to:
        visited.add(current)
        new_route = route + str(current) + "-"
        solution_found = next_move(visited, move, new_route, sq)
        visited.remove(current)
        if solution_found:
            return solution_found
    return None


def next_move(visited, current, route, sq):
    """Find the next valid moves and instruct "make_move" to carry them out"""
    if len(visited) == (sq * sq) - 1:
        route += str(current)
        return route
    move_to = generate_new_positions(visited, current, sq)
    return make_move(move_to, visited, current, route, sq)


def start_tour(sq):
    """Calculate the knights tour for grid sq*sq starting at all positions in range 0-sq"""
    starting = 0
    visited = set()
    route = ""
    return next_move(visited, starting, route, sq)


if __name__ == "__main__":
    for square_size in 3, 5, 6:
        ret = start_tour(square_size)
        print("No knights tour could be calculated" if ret is None else ret)

Also, formatting the string could be done in a single place as well. We could use lists for instance in all the logic.

def make_move(move_to, visited, current, route, sq):
    """Carry out the move"""
    for move in move_to:
        visited.add(current)
        new_route = route + [current]
        solution = next_move(visited, move, new_route, sq)
        visited.remove(current)
        if solution:
            return solution
    return None


def next_move(visited, current, route, sq):
    """Find the next valid moves and instruct "make_move" to carry them out"""
    if len(visited) == (sq * sq) - 1:
        return route + [current]
    move_to = generate_new_positions(visited, current, sq)
    return make_move(move_to, visited, current, route, sq)

def start_tour(sq):
    """Calculate the knights tour for grid sq*sq starting at all positions in range 0-sq"""
    starting = 0
    visited = set()
    route = []
    return next_move(visited, starting, route, sq)


if __name__ == "__main__":
    for square_size in 3, 5, 6:
        ret = start_tour(square_size)
        print("No knights tour could be calculated" if ret is None else "-".join((str(e) for e in ret)))

Reducing the duplicated information

We're maintaining a visited set and a route list: both containing roughtly the same data. Maybe we could recompute visited from the route when we need it.

def make_move(move_to, current, route, sq):
    """Carry out the move"""
    for move in move_to:
        solution = next_move(move, route + [current], sq)
        if solution:
            return solution
    return None

def next_move(current, route, sq):
    """Find the next valid moves and instruct "make_move" to carry them out"""
    if len(route) == (sq * sq) - 1:
        return route + [current]
    move_to = generate_new_positions(set(route), current, sq)
    return make_move(move_to, current, route, sq)

def start_tour(sq):
    """Calculate the knights tour for grid sq*sq starting at all positions in range 0-sq"""
    return next_move(0, [], sq)

Simplifying the logic

Having a function A calling a function B itself calling B can make things hard to understand properly because both A and B are hard to understand independently.

Here, we could get rid of make_move by integrating directly in next_move:

def next_move(current, route, sq):
    """Find the next valid moves and carry them out"""
    if len(route) == (sq * sq) - 1:
        return route + [current]
    for move in generate_new_positions(set(route), current, sq):
        solution = next_move(move, route + [current], sq)
        if solution:
            return solution
    return None

More simplification

In next_move, route is almost always used in the expression route + [current]. We could directly define this at the beginning of the function:

def next_move(current, route, sq):
    """Find the next valid moves and carry them out"""
    new_route = route + [current]
    if len(new_route) == (sq * sq):
        return new_route
    for move in generate_new_positions(set(new_route), current, sq):
        solution = next_move(move, new_route, sq)
        if solution:
            return solution
    return None

More importantly, it leads to the question: why do we provide a route AND an element to add to it instead of just having that element in the list.

def next_move(current, route, sq):
    """Find the next valid moves and carry them out"""
    if len(route) == (sq * sq):
        return route
    for move in generate_new_positions(set(route), current, sq):
        solution = next_move(move, route + [move], sq)
        if solution:
            return solution
    return None

def start_tour(sq):
    """Calculate the knights tour for grid sq*sq starting at all positions in range 0-sq"""
    start = 0
    return next_move(start, [start], sq)

Going further, we do not really the current argument anymore as we can compute it from route.

def next_move(route, sq):
    """Find the next valid moves and carry them out"""
    if len(route) == (sq * sq):
        return route
    current = route[-1]
    new_pos = generate_new_positions(set(route), current, sq)
    for move in new_pos:
        solution = next_move(route + [move], sq)
        if solution:
            return solution
    return None

def start_tour(sq):
    """Calculate the knights tour for grid sq*sq starting at all positions in range 0-sq"""
    start = 0
    return next_move([start], sq)

Final code

def generate_new_positions(visited, position, sq):
    """Yield legal moves"""
    generate_new_positions = [
        (-2, -1),
        (-2, 1),
        (-1, -2),
        (-1, 2),
        (1, -2),
        (1, 2),
        (2, -1),
        (2, 1),
    ]
    # position = row * sq + col
    row, col = divmod(position, sq)

    for dx, dy in generate_new_positions:
        x, y = row + dx, col + dy
        if 0 <= x < sq and 0 <= y < sq:
            new_pos = x * sq + y
            if new_pos not in visited:
                yield new_pos


def next_move(route, sq):
    """Find the next valid moves and carry them out"""
    if len(route) == (sq * sq):
        return route
    current = route[-1]
    new_pos = generate_new_positions(set(route), current, sq)
    for move in new_pos:
        solution = next_move(route + [move], sq)
        if solution:
            return solution
    return None


if __name__ == "__main__":
    for square_size in 3, 5, 6:
        ret = next_move([0], square_size)
        print("No knights tour could be calculated" if ret is None else "-".join((str(e) for e in ret)))
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Amazing thank you. It does make a lot of sense to use visited and route for the same purpose. I'm not sure why I didn't do this in the first place. I really like the way you return the function. It makes a lot more sense to me than returning the result of a function. Thanks \$\endgroup\$ – EML Jun 24 '19 at 22:09
2
\$\begingroup\$

Precomputed Moves

You are computing a lot of integer quotients and remainders. (@Josay's solution as well). You can reduce the amount of work done during the solving of the Knight's Tour by pre-computing the positions which can be reached from each square:

legal_moves = (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)
moves = [ [ (r+dr) * cols + (c+dc) for dr, dc in legal_moves
            if 0 <= r+dr < rows  and  0 <= c+dc < cols ]
          for r in range(rows) for c in range(cols) ]

I've used rows and cols here, to generalize from a square board to an NxM board. After this point, the logic doesn't change.

Now moves[0] is a list of all (both) positions that can be reached from square #0, moves[1] is a list of the 3 positions that can be reached from square #1, and so on. Note that you never need to deal with the dimension of the board again. No integer division or modulo remainders; just use the square's index number.

Visited

Your visited set is a nice way, to keep track of whether or not a position has been visited or not. In \$O(1)\$ time, you can tell if you've reached a visited location or not. @Josay's suggestion of using set(route) to recompute the set of visited locations removes the need for maintaining a separate global set() structure, but the cost is recreating the set(route) each move. This is at least \$O(N)\$ per move, a huge decrease in performance.

A different structure for keeping track of visited locations is to simply use an array of positions. If visited[move] is True, you've been there, if not, you haven't. This is faster that using a set(); you a just looking up an index. It is \$O(1)\$ with a very small constant.

Better: visited[move] = move_number. Initialize the array to 0 to start with every spot unvisited, and mark a 1 in the first move location, 2 in the second and so on. Set visited[move] = 0 when you back-track. No need to keep track of the route, as it is implicit in the visited[] array. print_route() amounts to reshaping the visited array into a 2D array, and printing it.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thank you for this reply. I am always dubious about using multi-line for loops and especially nested list comprehension because I have always read that if the code can be written in roughly the same number of lines with a similar space complexity (in my case it is O(1)) then it is better to use the more readable solution. Having said that I do think its a nice solution! \$\endgroup\$ – EML Jun 25 '19 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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