You will submit a file KnightTour.java. I suggest that you use the given code for Graph.java in course code.

import Graph.*;

class KnightTour {

Graph chess; void buildGraph(int n){ .. // builds the graph of the second page. N is the size of the chess board }

List knightTour (int n, List path, int u, int limit)

// n, the current depth in the search tree

// path, a list of vertices visited up to this point;

// u, the vertex in the graph we wish to explore

// limit = number of squares in the chess board.

On a five-by-five board you can produce a path in a couple seconds on a reasonably fast computer. But what

happens if you try an eight-by-eight board? In this case, depending on the speed of your computer, you may have to

wait up to a half hour to get the results! The reason for this is that the knights tour problem as we have implemented

it so far is an exponential algorithm of size k^N, where N is the number of squares on the chess board, and k is a

small constant.

Luckily there is a way to speed up the eight-by-eight case so that it runs in under one second. The critical idea is to

select the vertex to go next that has the fewest available moves.

The problem with using the vertex with the most available moves as your next vertex on the path is that it tends to

have the knight visit the middle squares early on in the tour. When this happens it is easy for the knight to get

stranded on one side of the board where it cannot reach unvisited squares on the other side of the board. On the

other hand, visiting the squares with the fewest available moves first pushes the knight to visit the squares around

the edges of the board first. This ensures that the knight will visit the hard-to-reach corners early and can use the

middle squares to hop across the board only when necessary.