The Knights Tour is an ancient and famous chess puzzle. The object is to move a knight from one square to another on an otherwise empty chess board until it has visited every square exactly once. Write a program that solves this puzzle using a depth-first search. Its best to make the board size variable so that you can attempt solutions for smaller boards. The regular 88 board can take years to solve on a desktop computer, but a 55 board takes only a minute or so. Refer to the section Depth-First Search and Game Simulations in this chapter. It may be easier to think of a new knight being created and remaining on the new square when a move is made. This way, a knight corresponds to a vertex, and a sequence of knights can be pushed onto the stack. When the board is completely filled with knights (the stack is full), you win. In this problem the board is traditionally numbered sequentially, from 1 at the upper-left corner to 64 at the lower-right corner (or 1 to 25 on a 55 board). When looking for its next move, a knight must not only make a legal knights move, it must also not move off the board or onto an already-occupied (visited) square. If you make the program display the board and wait for a keypress after every move, you can watch the progress of the algorithm as it places more and more knights on the board, and then, when it gets boxed in, backtracks by removing some knights and trying a different series of moves. Well have more to say about the complexity of this problem in the next chapter. This is what I have:

import java.io.*;

class KnightStackX { private int[] st; private int top;

public KnightStackX() // constructor { st = new int[KnightGraph.AREA]; // make array top = -1; }

public void push(int j) // put item on stack { st[++top] = j; }

public int pop() // take item off stack { return st[top--]; } public int peek() // peek at top of stack { return st[top]; }

public boolean isEmpty() // true if nothing on stack- { return (top == -1); } public boolean isFull() { return (top == st.length-1); } public boolean oneItem() //is there only one item left in the stack? { return (top == 0); }

} // end class KnightStackX

//placed in Vertex to remember which vertices //were visited from that Vertex class VisitedStackX { private int[] st; private int top;

public VisitedStackX() // constructor { st = new int[8]; // make array top = -1; }

public void push(int j) // put item on stack { st[++top] = j; }

public int pop() // take item off stack { return st[top--]; } public int peek() // peek at top of stack { return st[top]; }

public boolean isEmpty() // true if nothing on stack- { return (top == -1); } public boolean isFull() { return (top == st.length-1); }

} // end class KnightStackX

class KnightVertex { public char label; // label (e.g. A) public boolean wasVisited; public VisitedStackX justVisited; public int lastVisited;

public KnightVertex() // constructor { label = '-'; wasVisited = false; justVisited = new VisitedStackX(); lastVisited = -1; }

} // end class KnightVertex

class KnightGraph { public static final int SIZE = 5; public static final int AREA = SIZE*SIZE; private KnightVertex vertexList[]; // list of vertices private int adjMat[][]; // adjacency matrix private int nVerts; // current number of vertices private KnightStackX theStack;

public KnightGraph() { vertexList = new KnightVertex[AREA]; // adjacency matrix adjMat = new int[AREA][AREA]; nVerts = AREA; for(int j=0; j

public void addPossibleMoves(int i, int j) { int currentRow = i*SIZE; int currentCol = j; int currentVertex = currentRow+currentCol; //if the move is in the board if(i-1>=0) { if(j-2>=0) addEdge(currentVertex, currentVertex-SIZE-2); if(j+2=0) addEdge(currentVertex, currentVertex+SIZE-2); if(j+2=0) { if(j-1>=0) addEdge(currentVertex, currentVertex-(SIZE*2)-1); if(j+1=0) addEdge(currentVertex, currentVertex+(SIZE*2)-1); if(j+1

public void displayVertex(int v) { System.out.print(vertexList[v].label); } public void displayBoard() { System.out.println(".................................."); for(int i = 0; i < SIZE; i++) { for(int j = 0; j < SIZE; j++) System.out.print(vertexList[i*SIZE+j].label); System.out.println(); } System.out.println(".................................."); }

//modified to allow specification of starting vertex public boolean dfs(int start) throws IOException // depth-first search { vertexList[start].label = 'S'; //denote start with S vertexList[start].wasVisited = true; // mark it theStack.push(start); // push it while( !theStack.isEmpty() ) // until stack empty, { int m = theStack.peek(); vertexList[m].label = 'M'; //displayBoard(); //getChar(); if(theStack.isFull()) //we won { for(int j=0; j

public int getNextVertex(int v) { for(int j = vertexList[v].lastVisited+1; j < nVerts; j++) if(adjMat[v][j]==1 && vertexList[j].wasVisited == false) return j; return -1; } public void getChar() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); br.readLine(); } // returns an unvisited vertex adj to v public int getAdjUnvisitedVertex(int v) { for(int j=0; j

class KnightApp { public static void main(String[] args) throws IOException { KnightGraph theGraph = new KnightGraph(); System.out.println("CREATED GRAPH"); boolean solutionFound = false; theGraph.displayMatrix(theGraph.getAdjMat()); for(int i = 0; i < KnightGraph.AREA; i++) { solutionFound = theGraph.dfs(i); if(solutionFound) System.out.println("FOUND A SOLUTION STARTING AT (" + (i/KnightGraph.SIZE) + ", " + (i%KnightGraph.SIZE) + ")"); else System.out.println("NO SOLUTION FROM (" + (i/KnightGraph.SIZE) + ", " + (i%KnightGraph.SIZE) + ")"); } } // end main() } // end class KnightApp ////////////////////////////////////////////////////////////////

My Output: CREATED GRAPH 0000000100010000000000000 0000000010101000000000000 0000010001010100000000000 0000001000001010000000000 0000000100000100000000000 0010000000001000100000000 0001000000000101010000000 1000100000100010101000000 0100000000010000010100000 0010000000001000001000000 0100000100000000010001000 1010000010000000001010100 0101010001000001000101010 0010101000000000100000101 0001000100000000010000010 0000001000001000000000100 0000010100000100000000010 0000001010100010000010001 0000000101010000000001000 0000000010001000000000100 0000000000010000010000000 0000000000101000001000000 0000000000010101000100000 0000000000001010100000000 0000000000000100010000000 0 7 4 13 2 5 16 23 14 3 6 15 12 9 18 21 10 1 8 19 22 11 20 17 24 FOUND A SOLUTION STARTING AT (0, 0) NO SOLUTION FROM (0, 1) 2 5 12 9 18 21 10 1 8 19 22 15 6 3 14 23 16 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (0, 2) NO SOLUTION FROM (0, 3) 4 7 0 11 2 5 12 9 18 21 10 1 8 19 22 15 6 3 14 23 16 13 24 17 20 FOUND A SOLUTION STARTING AT (0, 4) NO SOLUTION FROM (1, 0) 6 3 12 15 22 19 8 1 10 21 18 9 2 5 16 23 14 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (1, 1) NO SOLUTION FROM (1, 2) 8 1 10 21 12 19 22 15 6 3 14 23 16 5 2 9 18 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (1, 3) NO SOLUTION FROM (1, 4) 10 1 8 19 12 21 18 9 2 5 16 23 14 3 6 15 22 11 0 7 4 13 24 17 20 FOUND A SOLUTION STARTING AT (2, 0) NO SOLUTION FROM (2, 1) 12 1 8 19 22 15 6 3 14 23 16 5 2 9 18 21 10 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (2, 2) NO SOLUTION FROM (2, 3) 14 3 6 15 12 23 16 5 2 9 18 21 10 1 8 19 22 11 0 7 4 13 24 17 20 FOUND A SOLUTION STARTING AT (2, 4) NO SOLUTION FROM (3, 0) 16 5 2 9 12 23 14 3 6 15 22 19 8 1 10 21 18 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (3, 1) NO SOLUTION FROM (3, 2) 18 9 2 5 12 21 10 1 8 19 22 15 6 3 14 23 16 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (3, 3) NO SOLUTION FROM (3, 4) 20 11 0 7 4 13 2 5 16 23 12 9 18 21 10 1 8 19 22 15 6 3 14 17 24 FOUND A SOLUTION STARTING AT (4, 0) NO SOLUTION FROM (4, 1) 22 15 6 3 12 19 8 1 10 21 18 9 2 5 16 23 14 7 0 11 20 17 24 13 4 FOUND A SOLUTION STARTING AT (4, 2) NO SOLUTION FROM (4, 3) 24 13 2 5 16 23 12 9 18 21 10 1 8 19 22 15 6 3 14 17 20 11 0 7 4 FOUND A SOLUTION STARTING AT (4, 4)

But this is how it should look like: Hint:

public static void main(String[] args) throws IOException

{

int N; // board size

int nMoves = 0; // number moves made

// or taken back

Knight thisKnight; // current knight

int pos; // position

N = Board.getN(); // get board size

StackK knightStack = new StackK(N*N); // make stack

System.out.print("Enter the beginning square (1 to " +

N*N + "): ");

System.out.flush();

pos = getInt(); // make first knight

thisKnight = new Knight(pos);

nMoves++;

while( knightStack.getDepth()+1 < (N*N) )

{

/* // Activate these to pause after each move

String dummy = getString(); // await keystroke

Board.display();

*/

/* // activate these to display the stack on every move

System.out.print(nMoves + ": ");

for(int j=0; j

System.out.print(

knightStack.getKnight(j).getPos() + " ");

System.out.println("(" + thisKnight.getPos() + ") ");

*/

pos = thisKnight.getNextPos();

nMoves++;

if(pos == -1) // if this knight

{ // can't move

thisKnight.destroy(); // destroy it

if( knightStack.isEmpty() )

{

System.out.println("FAILURE");

break; // program over

}

else

{ // get knight from stack

thisKnight = knightStack.pop();

}

}

else // successful move

{

knightStack.push(thisKnight);

thisKnight = new Knight(pos);

}

} // end while(...

// if we get here, success!

Board.display(); // display board

System.out.println("Moves & takebacks=" + nMoves);

// display stack

for(int j=0; j

System.out.print(

knightStack.getKnight(j).getPos() + " ");

// display current move

System.out.println("(" + thisKnight.getPos() + ") ");

} // end main()

Result:

Enter board size (8 for 8x8 board): 5

Enter the beginning square (1 to 25): 5

X X X X X

X X X X X

X X X X X

X X X X X

X X X X X

Moves & takebacks=551

5 14 25 18 9 20 23 16 7 4 15 24 17 6 3 10 19 22 13 2 11 8 1 12 (21)

Or

Enter board size (8 for 8x8 board): 8

Enter the beginning square (1 to 64): 1

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X

Moves & takebacks=6484066

1 11 5 15 32 47 64 54 39 24 30 40 55 61 46 31 16 22 7 13 23 8 14 29 44 38 48 63 53 59 49 34 19 4 21 6 12 2 17 27 37 52 58 41 35 20 10 25 42 57 51 36 26 9 3 18 28 43 33 50 60 45 62 (56) Where am I wrong and can you help me fix it?