# A Knight's Tour

• 10-12-2011, 11:09 PM
danthegreat
A Knight's Tour
An old guy named Euler proposed a problem regarding the movemesnt of knight chess pieces on a chess board. Euler proposed the challenge of putting the knight piece on every square of an empty chessboard (aka a matrix) and to touch all 100 squares once and only once..

I need help with my program. I have tried printing variables but I cannot keep track of how the array index could possibly be going out of bounds. Anyone know? Here's mah code!

Code:

/*
* Program that moves a "knight" around an empty chessboard to touch each of the squares once and only once.
*/
import java.util.*;
public class Ansher_knighttour
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
Random randGen = new Random();

int[][] matrix = new int[10][10];
int[] possibleMoves;
int row_start;
int col_start;
int random;
int counter=0;
int move;

System.out.print("Enter row # to start: ");
row_start=keyboard.nextInt();

System.out.print("Enter column # to start: ");
col_start=keyboard.nextInt();

matrix[row_start][col_start]='K';

int counte;
int counte_track=0;

do
{
int[] vertical={row_start+1,row_start+2, row_start+2, row_start+1, row_start-1, row_start-2, row_start -2, row_start-1};
int[] horizontal={col_start-2, col_start-1, col_start+1, col_start+2, col_start+2, col_start+1, col_start-1,col_start-2};

possibleMoves=possibleMoves(row_start, col_start, matrix, vertical, horizontal);
counte=possibleMoves.length;
random=randGen.nextInt(possibleMoves.length)+1;
counter++;

move=possibleMoves[random];
counte_track++;

System.out.println(move);

[B]        row_start=vertical[move];
col_start=horizontal[move];[/B]

matrix[row_start][col_start]=counter;

}while(counte!=counte_track);

displayResults(matrix);

}

public static void displayResults(int [][] matrix)
{
int curMax=Integer.MIN_VALUE;

System.out.print("    ");
for(int i3=1; i3<=matrix.length; i3++)
{
System.out.print(i3 + "  ");
}

System.out.println("");
for(int i=0; i<matrix.length; i++)
{

System.out.print(i+1);
for(int i2=0; i2<matrix[i].length; i2++)
{
if(matrix[i][i2]>curMax)
{
curMax=matrix[i][i2];
}
if(matrix[i][i2]>=0 && matrix[i][i2]<=9)
{
System.out.print("  " + matrix[i][i2]);
}
else
{
System.out.print("  " + matrix[i][i2]);
}
}
System.out.println("");
}

System.out.println(curMax + " squares were visited.");

}

public static int[] possibleMoves(int row, int col, int[][] matrix, int[] vertical, int[]horizontal)
{

int[] possibleMoves=new int[9];

for(int i=0; i<vertical.length;i++)
{
if(vertical[i]>=0 && vertical[i]<matrix.length || horizontal[i]>=0 && horizontal[i]<matrix.length)
{
possibleMoves[i]=vertical[i];

}
else
{
possibleMoves[i]=-1;
}
}

int counter=0;

for(int i2=0; i2<possibleMoves.length; i2++)
{
if(possibleMoves[i2]>0)
{
counter++;
}
}

int[] possibleMovesFINAL=new int[counter];

int counter2=-1;

for(int i3=0; i3<possibleMoves.length; i3++)
{
if(possibleMoves[i3]>0)
{

counter2++;
possibleMovesFINAL[counter2]=possibleMoves[i3];
}
}

return possibleMovesFINAL;

}

}

Bolded is where my problem is. Also, I don't know how to keep track of where I have already been.
• 10-12-2011, 11:25 PM
danthegreat
Re: A Knight's Tour
Ok i tried this variation

Code:

/*  * Program that moves a "knight" around an empty chessboard to touch each of the squares once and only once.
*/
import java.util.*;
public class Ansher_knighttour
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
Random randGen = new Random();

int[][] matrix = new int[10][10];
int[] possibleMoves;
int row_start;
int col_start;
int random;
int counter=0;
int move;

System.out.print("Enter row # to start: ");
row_start=keyboard.nextInt();

System.out.print("Enter column # to start: ");
col_start=keyboard.nextInt();

matrix[row_start][col_start]='K';
//Loop should start here.

int num=0;

do
{
int[] vertical={row_start+1,row_start+2, row_start+2, row_start+1, row_start-1, row_start-2, row_start -2, row_start-1};
int[] horizontal={col_start-2, col_start-1, col_start+1, col_start+2, col_start+2, col_start+1, col_start-1,col_start-2};

possibleMoves=possibleMoves(row_start, col_start, matrix, vertical, horizontal);

[B]                random=randGen.nextInt(possibleMoves.length);[/B]
[B]        [/B]
[B]                System.out.println(possibleMoves[random]);[/B]
[B]                [/B]
[B]                if(possibleMoves[random]!=-1)[/B]
[B]                {[/B]
[B]                        counter++;[/B]
[B]                        move=possibleMoves[random];[/B]
[B]                        possibleMoves[random]=-1;[/B]
[B]                [/B]
[B]                        row_start=vertical[move];[/B]
[B]                        col_start=horizontal[move];[/B]
[B]                        matrix[row_start][col_start]=counter;                [/B]
[B]                }[/B]
[B]                else[/B]
[B]                {[/B]
[B]                        num++;[/B]
[B]                }[/B]
[B]                [/B]
[B]                }while(counter<=100 || num!=possibleMoves.length);[/B]

displayResults(matrix);

}

public static void displayResults(int [][] matrix)
{
int curMax=Integer.MIN_VALUE;

System.out.print("    ");
for(int i3=1; i3<=matrix.length; i3++)
{
System.out.print(i3 + "  ");
}

System.out.println("");
for(int i=0; i<matrix.length; i++)
{

System.out.print(i+1);
for(int i2=0; i2<matrix[i].length; i2++)
{
if(matrix[i][i2]>curMax)
{
curMax=matrix[i][i2];
}
if(matrix[i][i2]>=0 && matrix[i][i2]<=9)
{
System.out.print("  " + matrix[i][i2]);
}
else
{
System.out.print("  " + matrix[i][i2]);
}
}
System.out.println("");
}

System.out.println(curMax + " squares were visited.");

}

public static int[] possibleMoves(int row, int col, int[][] matrix, int[] vertical, int[]horizontal)
{

int[] possibleMoves=new int[9];

for(int i=0; i<vertical.length;i++)
{
if(vertical[i]>=0 && vertical[i]<matrix.length || horizontal[i]>=0 && horizontal[i]<matrix.length)
{
possibleMoves[i]=vertical[i];

}
else
{
possibleMoves[i]=-1;
}
}

int counter=0;

for(int i2=0; i2<possibleMoves.length; i2++)
{
if(possibleMoves[i2]>0)
{
counter++;
}
}

int[] possibleMovesFINAL=new int[counter];

int counter2=-1;

for(int i3=0; i3<possibleMoves.length; i3++)
{
if(possibleMoves[i3]>0)
{

counter2++;
possibleMovesFINAL[counter2]=possibleMoves[i3];
}
}

return possibleMovesFINAL;

}

}

this is what happens with output:
Enter row # to start: 3
Enter column # to start: 3
2
4
2
4
6
1
4
6
4
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at Ansher_knighttour.main(Ansher_knighttour.java:58)

for some reason it doesn't it never reaches the end of the loop. sigh.