knights tour algorithm
Hi, was hopin someone could point me in the right direction where i have gone wrong. The program compiles and takes the user input but doesnt seem to be able to find a complete tour.
All help is appreciated
//Solving the Knights tour Problem : Moving a knight on an otherwise
//empty chessboard until it has visited each square exactly once
import java.io.*;
class Graph{
// Adjacency matrix which represents chessboard
privatestaticint board [][];
privateint boardsize;
public Graph (int boardsize)//constructor
{
board =newint [boardsize][boardsize];
//Set adj matrix to 0
for (int i=0; i<boardsize; i++)
for (int j=0; j><boardsize; j++)
board [i][j] = 0;
}//end constructor
//Is proposed move on the board
privatestaticboolean onBoard(int row,int col){
return (row >=0 && row < boardsize && col>=0 && col < boardsize);
}
//Is square available to move to
privatestaticboolean available (int row,int col){
return (board[row][col]== 0);
}
//Main method - Does the searching for a solution from a given start point
privatestaticboolean doTour(int row,int col,int moveNum){
int nr=0, nc=0;
//Can the knight move to proposed square?
if (!onBoard(row, col) || !available(row, col))
returnfalse;
//Record move
board[row][col] = moveNum;
//Has a solution been found?
if(moveNum == boardsize*boardsize)
returntrue;
for (int i=0;i<8;i++)
{
switch (i)
{
case 0: nr= row-2; nc= col+1;
break;
case 1: nr = row-2; nc=col-1;
break;
case 2: nr = row +2; nc =col+1;
break;
case 3: nr = row+2; nc = col-1;
break;
case 4: nr = row+1; nc=col+2;
break;
case 5: nr = row+1; nc = col-2;
break;
case 6: nr = row-1; nc = col+2;
break;
case 7: nr = row-1; nc = col-2;
break;
}
if (doTour (nr,nc,moveNum+1))
returntrue;
}
//all eight possible moves tried no success
//unrecord move and backtrack
board[row][col] = 0;
returnfalse;
}
publicstaticvoid main(String [] args)
{
InputStreamReader stdin =new InputStreamReader(System.in);
BufferedReader console =new BufferedReader(stdin);
int initX = 0,initY = 0, boardsize = 0;//
String s1,s2, s3;
try
{
System.out.print("Enter starting row ");
s1 = console.readLine(); initX = Integer.parseInt(s1);
System.out.print("Enter starting column ");
s2 = console.readLine(); initY = Integer.parseInt(s2);
System.out.print("Enter boardsize");
s3 = console.readLine(); boardsize = Integer.parseInt(s3);
}
catch(IOException ioex)
{
System.out.println("Input error");
System.exit(1);
}
catch(NumberFormatException nfex)
{
System.out.println("\"" + nfex.getMessage() +"\" is not numeric");
System.exit(1);
}
Graph theGraph =new Graph(boardsize);
//Begin tour
if (doTour(initX, initY,1))
{ System.out.println ("tour successful contents are: ");
for (int i=0; i < boardsize;i++)
{
for (int j=0;j<boardsize;j++)
System.out.print(board[i][j]+"**");
System.out.println();
}
}
else System.out.println ("Tour not possible from (" + initX +"," + initY +")");
}
}
[>
