Knight's Tour - Python 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 &lt;= (row + dx) &lt; sq and 0 &lt;= (col + dy) &lt; sq:
            new_position = (position + (sq * dx)) + dy
            if new_position not in visited and 0 &lt;= new_position &lt; (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)
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)))