-
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.
-
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.
