Results 1 to 2 of 2

Thread: A Knight's Tour

  1. #1
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default 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!

    Java 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.
    Last edited by danthegreat; 10-12-2011 at 11:12 PM.

  2. #2
    danthegreat is offline Member
    Join Date
    Sep 2011
    Location
    Washington DC
    Posts
    51
    Rep Power
    0

    Default Re: A Knight's Tour

    Ok i tried this variation

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

Similar Threads

  1. Replies: 1
    Last Post: 08-03-2011, 01:30 PM
  2. Limited seats to Open Source Enterprise search Tour
    By petermatilda in forum Java Software
    Replies: 0
    Last Post: 10-13-2010, 05:41 AM
  3. help on Knights tour
    By frank17 in forum New To Java
    Replies: 4
    Last Post: 01-30-2010, 11:00 PM
  4. Knights Tour.
    By atl2 in forum New To Java
    Replies: 1
    Last Post: 02-06-2008, 07:31 PM
  5. Knights Tour problem
    By goorioles747 in forum New To Java
    Replies: 1
    Last Post: 11-26-2007, 03:54 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •