Knight's Tour - Python
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 &lt;= x &lt; sq and 0 &lt;= y &lt; 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 &lt;= x &lt; sq and 0 &lt;= y &lt; 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)))