Question

Create an alternate KtR that solves knight's tour problem for an 8 by 8 board by randomly picking a move from 0 to 7 and if legal make the move. If not legal, try doing this 100 times and if no legal moves after 100 tries abort the game as a failure.
If you make 64 moves print the board. Use every possible square on the board so you should have 64 solutions (one for every square).
it should be ok for an 8 by 8
I got to modify this code:

Answer 1

import javax.swing.JOptionPane;

public class KtH {
private Board b;
private int ctr=0; // this counts the moves the knight makes
private int [] lastMove=new int[2]; // we need a 1 x 2 array to store (x,y) the pos. of last move
private int h[]={-2,-2,-1,-1,1,1,2,2}; // this is the change in column
private int v[]={-1,1,2,-2,2,-2,1,-1}; // this is change in row
private int adj[][]; // adjacency matrix keeping track of # of moves left from every square on board b
private int r,c,dim;


public KtH(int dim, int r, int c){
adj=new int [dim][dim];
b=new Board(dim); // instantiate a Board object b to dimension dim x dim
b.setElement(r, c, ++ctr); // set the board at position (r,c) to 1
lastMove[0]=r;
lastMove[1]=c;
this.r=r;
this.c=c;
this.dim=dim;
computeAdjMatrix(); // recalculate the number of moves left at each square

start(); // start the game
}

// overload the constructor

public KtH(int dim){
// this will start the game automatically in the upper left corner of the board
this(dim,0,0); // this calls the previous constructor
}
// default constructor follows
public KtH() {
this(8); // this calls the constructor above
}
private void start(){
// note the first move has been made prior to entering start
for (int i=1; i<adj[0].length * adj[0].length; i++) // this will step thru all the moves
if (!nextMove())
{
System.out.println("game aborted for start position " + "("+ r+ ","+ c+ ")");
System.out.println("the number of moves was " + ctr);
break;
}
//b.printBoard();

}

private void computeAdjMatrix(){

// start with a nested for loop that runs thru all rows and cols

for (int i=0; i<adj[0].length; i++)
for (int j=0; j<adj[0].length; j++)
adj[i][j]=numberOfMoves(i,j); // pass the row and col to the method

}

private int numberOfMoves(int r, int c){
int ctr=0;
if (b.getElement(r, c)!=0)
return 0; // if the square in question was visited then return 0
// compute the number of legal moves between 0 and 8
// a simple for loop running thru the 8 possible legal moves

for (int i=0; i<8; i++) // step thru the moves
if (legal(r,c, i)==true )
ctr++;

return ctr;

}
private boolean legal(int r, int c, int m)
{
// (r,c) is position and m is the mth move
// return true if a legal move
// m must be between 0 and 7

if (((r + v[m])> dim-1) || ( r+v[m]<0))
return false; // off the board

if (((c + h[m])> dim-1) || ( c+h[m]<0))
return false; // off the board

if (b.getElement(r + v[m], c + h[m])>0)
return false;

return true;
}
private boolean nextMove(){
// use the heuristic to find the next move
// which is the legal move with the lowest adjacency matrix value
// in case of a tie, simply pick the first of the moves

int small=9; // larger than any possible adj matrix value
int move=8; // an impossible move value

for (int i=0; i<8; i++)
if (legal(lastMove[0],lastMove[1],i)) // is this a legal square?
if (adj[lastMove[0]+ v[i]][lastMove[1]+h[i]] < small)
{move = i;
small=adj[lastMove[0]+ v[i]][lastMove[1]+h[i]];
}

if (move<8) // we found a move to make
// make the move
{int r=lastMove[0]+ v[move];
int c=lastMove[1]+ h[move];
b.setElement(r, c, ++ctr); // set the board at position (r,c) to 1
lastMove[0]=r;
lastMove[1]=c;
computeAdjMatrix();
return true;
}
else
return false;
}
public static void main(String args[]){
// ask user for starting position
// int r=Integer.parseInt(JOptionPane.showInputDialog("enter the row"));
// int c=Integer.parseInt(JOptionPane.showInputDialog("enter the col"));
int r,c;
KtH h;
int dim=100;
for (r=0; r<dim; r++)
for ( c=0; c<dim; c++)
h=new KtH(dim,r,c); // begin the tour of an 8 by 8 board in lower right corner


}
}

Answer 2

if wonder abou the board here is:

Answer 3

public class Board {
private int b[][];
public Board(){
//default constructor
b=new int[8][8]; // a chess board
}

public Board(int d){ // input the dimension
//default constructor
b=new int[d][d]; // a d by d square matrix
}
public Board(int a[][]){
// create the dimension of the board equal to the dimension
// of the square matrix a and set elements of b equal to a
this(a.length); // call the constructor above to set dimenstion
for (int i=0; i<a.length; i++)
for (int j=0; j<a.length; j++)
setElement(i,j,a[i][j]);
}

public int getElement(int r, int c){
return b[r][c];
}

public void setElement(int r, int c, int v){
b[r][c]=v;
}
// write isEmpty method and isFull method and printBoard method

public boolean isFull(){
// is the entire board full?
for(int i=0; i<b.length; i++){
for(int j=0; j<b.length; j++){
if(b[i][j]==0)
return false;


}
}

return true;
}
public boolean isOccupied(int r, int c){
// is a particular square occupied
if(b[r][c]!=0) return false;
else return true;
}
public boolean isEmpty(){
// is the entire board empty
boolean empty=true;
for(int i=0; i<b.length-1; i++){
for(int j=0; j<b[i].length-1; j++){
if(b[i][j]!=0) empty=false;
}
}
return empty;
}
public boolean isEmpty(int r, int c){
// is a particular square empty?
if(b[r][c]==0) return true;
else return false;
}
public void printBoard(){
for(int i=0; i<b.length; i++){
for(int j=0; j<b[i].length; j++){
System.out.print(b[i][j] + " ");
}
System.out.println();
}
}


public void setRow(int r, int a[]){
// fill row r with array a
// precondition: dim of a = dim b
for (int i=0; i<a.length; i++)
b[r][i]=a[i];
}
}

Answer 4

using java alg

Answer 5

Holy code... Knights Tour dun dun dun :). I remember being asked this in my CS class as it was a programming competition Q in NYS.

Answer 6

you know what to do and which line i should change it @KonradZuse?