USING PYTHON

The Knight Tour. A knight in chess is a piece that can move either two squares horizontally (in either direction) followed by one square vertically (in either direction), or one square horizontally (in either direction) followed by two squares vertically (in either direction), provided that it lands on the chessboard. A knights tour is a sequence of legal moves by a knight starting at some square and visiting each square of the chessboard exactly once. A knights tour is called reentrant (or closed) if there is a legal move that takes the knight from the last square of the tour back to the starting square. See the figure below for an example (taken from the internet) of a closed knight tour on a regular 8 8 chessboard. (The numbers indicate the order in which the squares are visited.)

In this problem, you need to use recursion to write a backtracking program that takes n as input, and outputs a reentrant/closed knight tour on an n n chessboard if such a tour exists; otherwise, it outputs that no such tour exists. To output the tour, you need to output the (ordered) sequence of squares visited by the knight. You are not required to output all the existing tours; you only need to output one.

First, label the rows and columns of the chessboard with positive integers (1, 2, 3, ...). A square is then referred to by a pair (x, y), where x is the row

number and y is the column number determining the square. You may find it helpful to follow the following steps in your implementation:

(i) Write a function that takes as input n and the coordinates of a square (x, y), and returns a list of all possible squares that a knight can reach from square (x, y) in one legal move.

(ii) Write a backtracking recursive function that takes as input a square (x, y), in addition to (possibly) other parameters/arguments, and com- putes a closed knight tour starting at (x, y) if such a tour exists. Your function should use the function developed in (i) above.