Results 1 to 5 of 5
  1. #1
    frank17 is offline Member
    Join Date
    Jan 2010
    Posts
    1
    Rep Power
    0

    Default help on Knights tour

    Hi
    I am kinda new to java and need some help with a homework problem(Knights tour). This is what i have so far and would appreciate the help in debugging my code

    Java Code:
    public class KnightsMovement {
    	 int [][]board = new int [8][8] ;
    	 int  moves=1 ;// amount of moves
    	 int x=4,y=3;//position
    	 int len=8, with=8;//size of board
    
    	public void setBoard(){
    		 for(int i=0;i<len;i++)// makes all values in board 0
    			 for(int j=0;j<with;j++)
    				 board[i][j]=0;
    	}
    	
    
    	 
    	public boolean place(){ //call recursive method
    
    		return place(x,y, moves);
    		}
    	
        public boolean  place(int x, int y, int  moves){//recursive method
         if (x<0|| x>= with|| y<0|| y<=len){
        		return false;
        	}
         else if (board[x][y]>0){
     		return false;
     	}
        	else if ( moves==(len*with)){
        		board[x][y]=moves;
        		for(int i=0;i<len;i++)
        			for (int j=0;j<with;j++)
        				System.out.println(""+board[i][j]);
        		return true;
        	}
        	
            
        else{
        	board[x][y]= moves;
        	 moves++;
        	if (place(x-2, y-1, moves) || place(x-2, y+1,  moves) || place(x-1, y+2,  moves)
    				 || place(x+1, y+2, moves) || place(x+2, y+1, moves) || place(x+2, y-1,  moves) 
    				 || place(x+1, y-2,  moves) || place(x-1, y-2,  moves)){
    				return true;
    			}
    	else{
    		board[x][y] = 0;
    	 return false;
            }
    	  
      }
        }
    
    }
    Last edited by Fubarable; 01-30-2010 at 06:43 PM. Reason: Code tags added

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by frank17 View Post
    Hi
    I am kinda new to java and need some help with a homework problem(Knights tour). This is what i have so far and would appreciate the help in debugging my code
    I added code tags to your post to help make the code more readable. Now it's your turn to give us more info. So far you've just dropped in your code with the above statement that tells us nothing about what works, what doesn't work, what you need help with.

    Please read this link to see how you can make your question easier to answer:
    Smart Questions

    Much luck!

  3. #3
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    frank17, what is your recursive method trying to do? For a start, I made it more object orientated.

    Java Code:
    public class KnightsMovement {
    		
    	private int[][] board;
    	private final int LENGTH = 8, WIDTH = 8; // size of board
    
    	public KnightsMovement() {
    		 board = new int[WIDTH][LENGTH];
    		 setBoard();
    	}
    
    	private void setBoard() {
    		 for(int i=0;i<LENGTH;i++)
    			 for(int j=0;j<WIDTH;j++)
    				 board[i][j]=0;
    	}
    	
    	public void printBoard() {
    		for (int i=0; i<LENGTH;i++) {
    			for (int j=0; j<WIDTH; j++)
    				System.out.printf("%02d ",board[i][j]);
    			System.out.println();
    		}
    
    	}
    	
    	//recursive method
    	public boolean place(int x, int y, int moves) {
    		
    		//if the coordinate is not valid,
    		//return false.
    		if (x < 0 || x >= WIDTH || y < 0 || y >= LENGTH)
    			return false;
    		
    		//if the coordinate is not empty,
    		//return false.
    		else if (board[y][x] > 0)
    			return false;
    
    		//this is the base case.
    		else if (moves == (LENGTH*WIDTH)) {
    			board[y][x] = moves;
    	    	        printBoard();
    	    	        return true;
    	    	}
    	    	
    	        
    		else {
    			
    		    //print current position and move.
    	    	    System.out.printf("Current State: (%d,%d,%d)%n", x,y, moves);
    			
    		    board[y][x] = moves;
    		    moves++;
    		    	
    		    if (place(x-2, y-1, moves) || place(x-2, y+1,  moves) || place(x-1, y+2,  moves)
    		    		|| place(x+1, y+2, moves) || place(x+2, y+1, moves) || place(x+2, y-1,  moves) 
    		    		|| place(x+1, y-2,  moves) || place(x-1, y-2,  moves))
    		    		
    		    	return true;
    		    else {
    		    	board[y][x] = 0;
    		    	return false;
    		    }
    	    }
    	}
    }
    Driver program:
    Java Code:
    public class KnightsMovementDriver {
    	public static void main(String[] args) {
    		KnightsMovement test = new KnightsMovement();
    		test.place(3,4,1);
    	}
    }
    Output:

    Java Code:
    Current State: (3,4,1)
    Current State: (1,3,2)
    Current State: (0,5,3)
    Current State: (1,7,4)
    ...Goes on until I exit out of Eclipse. Consequently, it crashes.
    Last edited by Lil_Aziz1; 01-30-2010 at 09:32 PM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  4. #4
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    If you really want to track what's happening, you can replace System.out.printf(..); with
    Java Code:
    printBoard(); 
    System.out.println();
    Your output would look like this:

    Java Code:
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 01 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 02 00 00 00 00 00 00 
    00 00 00 01 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 02 00 00 00 00 00 00 
    00 00 00 01 00 00 00 00 
    03 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    00 00 00 00 00 00 00 00 
    ...Goes on until I exit out of Eclipse. Consequently, it crashes.
    Last edited by Lil_Aziz1; 01-30-2010 at 09:31 PM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    There exists a very nice and very simple heuristics for the Knight Tour: given a current position, register all its possible moves and for each destination cell register how many moves you can make from there. Move to the cell with the least number of moves left. It'll never crash and it'll always find a solution and it's fast.

    kind regards,

    Jos

Similar Threads

  1. Knights Tour.
    By atl2 in forum New To Java
    Replies: 1
    Last Post: 02-06-2008, 07:31 PM
  2. 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
  •