Results 1 to 5 of 5
Like Tree1Likes
  • 1 Post By JosAH

Thread: knight's tour problem

  1. #1
    Kareem Mesbah is offline Member
    Join Date
    Sep 2012
    Posts
    15
    Rep Power
    0

    Default knight's tour problem

    Hi

    I've made an application that simulates knight's moves on a chessboard
    the program takes a specific move of the eight possible moves and applies it by setting the appropriate element in the array board to 1 which already means that this square has been visited.
    I also created an array accessibility that determines the accessibility of each square, for example the four corner squares have the accessibility value of 2 because there are only two squares that can be reached from each square of the four corner squares.

    I am aiming now to improve this application and make it able to make decisions and make moves toward the lowest accessibility squares so that I've to make a tour with the knight that consists of 64 moves and the knight must land of each square on the board only once.

    but actually I don't know how to do this. so I'll be thankful if there are more hints.

    my code (I've the main method in a separate class):

    Java Code:
    public class Chessboard {
    
    	public int currentRow = 0;
    	public int currentCol = 0;
    	private int[][] board = new int[8][8];
    	private int[] horizontal = new int[8];
    	private int[] vertical = new int[8];
    	public int totalMoves = 0;
    	private int[][] accessibility = new int[8][8];
    
    	//constructor
    	public Chessboard () {
    		// initialize board
    		for (int row = 0; row < board.length; row++) {
    			for (int col = 0; col < board[row].length; col++) {
    				board[row][col] = 0;
    			}// end nested for
    		}// end for
    		
    		board[currentRow][currentCol] = 1;
    			
    		// initialize moves
    		horizontal[ 0 ] = 2;
    		vertical[ 0 ] = -1;
    		
    		horizontal[ 1 ] = 1;
    		vertical[ 1 ] = -2;
    		
    		horizontal[ 2 ] = -1;
    		vertical[ 2 ] = -2;
    		
    		horizontal[ 3 ] = -2;
    		vertical[ 3 ] = -1;
    		
    		horizontal[ 4 ] = -2;
    		vertical[ 4 ] = 1;
    		
    		horizontal[ 5 ] = -1;
    		vertical[ 5 ] = 2;
    		
    		horizontal[ 6 ] = 1;
    		vertical[ 6 ] = 2;
    		
    		horizontal[ 7 ] = 2;
    		vertical[ 7 ] = 1;
    		
    		//initializing accessibility 
    				for (int row = 2; row <= 5; row++) {
    					for (int col = 2; col <= 5; col++) {
    						accessibility[row][col] = 8;
    					}
    				}
    				
    				for (int col = 2; col <= 5; col++) {
    					accessibility[1][col] = 6;
    					accessibility[6][col] = 6;
    					accessibility[0][col] = 4;
    					accessibility[7][col] = 4;
    				}
    				
    				for (int row = 2; row <= 5; row++) {
    					accessibility[row][0] = 4;
    					accessibility[row][7] = 4;
    					accessibility[row][1] = 6;
    					accessibility[row][6] = 6;
    				}
    				
    				accessibility[0][0] = 2;
    				accessibility[0][7] = 2;
    				accessibility[7][0] = 2;
    				accessibility[7][7] = 2;
    			
    				accessibility[0][1] = 3;
    				accessibility[0][6] = 3;
    				accessibility[1][0] = 3;
    				accessibility[1][7] = 3;
    				accessibility[6][0] = 3;
    				accessibility[6][7] = 3;
    				accessibility[7][1] = 3;
    				accessibility[7][6] = 3;
    				
    				accessibility[1][1] = 4;
    				accessibility[1][6] = 4;
    				accessibility[6][1] = 4;
    				accessibility[6][6] = 4;
    		
    	}// end constructor
    	
    	
    	
    	public void makeMove (int moveNumber) {
    
    		currentCol += horizontal[moveNumber];
    		currentRow += vertical[moveNumber];
    		
    		if ((currentRow > 7 || currentCol > 7) || (currentCol < 0) || (currentRow <0) ) {
    			//prevent landing out
    			currentCol -= horizontal[moveNumber];
    			currentRow -= vertical[moveNumber];
    		}
    		else {
    			
    			if (board[currentRow][currentCol] == 0) {
    				board[currentRow][currentCol] = 1;
    				totalMoves++;
    				accessibility[currentRow][currentCol] = 9;
    			}
    			else {
    				//prevent visiting the place more than once
    				currentCol -= horizontal[moveNumber];
    				currentRow -= vertical[moveNumber];
    			}
    		}
    		
    	}// end makeMove
    	
    	public void displayBoard () {
    		
    		for (int row = 0; row < board.length; row++) {
    			for (int col = 0; col < board[row].length; col++) {
    				System.out.printf("pos[%d][%d] = %d\n", row, col, board[row][col]);
    			}// end nested for
    		}// end for
    	}// end displayBoard
    }

  2. #2
    SJF
    SJF is offline Senior Member
    Join Date
    Oct 2012
    Posts
    108
    Rep Power
    0

    Default Re: knight's tour problem

    Are you just trying to move through the board once and only once? Then want a list of the moves it performed to get there?
    I might suggest a stack for this, but based on the current setup, you'll need an array that can hold your 64 locations and an array keeping track of the last move made from each location.
    This is a brute-force method, but would work like this:

    Start somewhere, mark it visited. start your list with that place
    count = 0
    while not done:
    If N-N-E available and not visited and not N-N-E from here before (separate array/list)
    mark moved[HERE] = N-N-E
    move N-N-E
    mark new current visited, add to list of moves
    count ++
    Else If N-N-W available .....

    ...

    Else if S-S-W (OR LAST IN CHOICE OF MOVES) not available
    count --
    BACK UP

    ...

    if count == 63 done = true!

  3. #3
    Kareem Mesbah is offline Member
    Join Date
    Sep 2012
    Posts
    15
    Rep Power
    0

    Default Re: knight's tour problem

    I tried a similar way by performing the eight possible moves and checking whether the location is available or not if available I mark it as not available and try another location
    if not i stay at the same place and try different move. but my problem is to make the knight make a decision to move toward the square that has the lowest accessibility(has the least number of squares around it that can be reached only from it). I don't know how to do this for sorry.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

    Default Re: knight's tour problem

    Quote Originally Posted by Kareem Mesbah View Post
    I tried a similar way by performing the eight possible moves and checking whether the location is available or not if available I mark it as not available and try another location
    if not i stay at the same place and try different move. but my problem is to make the knight make a decision to move toward the square that has the lowest accessibility(has the least number of squares around it that can be reached only from it). I don't know how to do this for sorry.
    That's the 'Warnsdorff's rule' for a night tour; it solves the entire tour in linear time and you never have to back track.

    kind regards,

    Jos
    Kareem Mesbah likes this.
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Kareem Mesbah is offline Member
    Join Date
    Sep 2012
    Posts
    15
    Rep Power
    0

    Default Re: knight's tour problem

    Quote Originally Posted by JosAH View Post
    That's the 'Warnsdorff's rule' for a night tour; it solves the entire tour in linear time and you never have to back track.

    kind regards,

    Jos
    thank you very much :)

Similar Threads

  1. A Knight's Tour
    By danthegreat in forum New To Java
    Replies: 1
    Last Post: 10-12-2011, 11:25 PM
  2. Replies: 1
    Last Post: 08-03-2011, 01:30 PM
  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
  •