Figure $5$: Node $C$ is a dead end

Figure $6$: Backtrack to B

Figure $7$: Explore D

the complete graph of possible moves on an eight$-$by$-$eight board is above. There are exactly $336$ edges in the graph. The vertices corresponding to the edges of the board have fewer connections $($legal moves$)$ than the vertices in the middle of the board. Once again we can see how sparse the graph is$.$ If the graph was fully connected there would be $4,096$ edges. Since there are only $336$ edges, the adjacency matrix would be only $8\mathrm{.}2$ percent full.Solve the knight's tour problem using a version of $($DFS$)$ that forbids a node to be visited more than once to find a path that has exactly $63$ edges. Write this method recursively; a trace of the execution on a small graph is described below.

Figure $8$: Explore E

Figure $4$: Explore B Figure $10$: DONE

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$\frac{\frac{?}{?}}{n}\frac{\frac{?}{?}}{?}{k}^{{?}^{?}}NNk$ Building the Knight's Tour Graph

To represent the knight's tour problem as a graph we will use the following two ideas: Each square on the chessboard can be represented as a node in the graph. Each legal move by the knight can be represented as an edge in the graph. Figure above illustrates the legal moves by a knight and the corresponding edges in a graph.