# knight's tour problem

Printable View

• 10-26-2012, 04:57 PM
Kareem Mesbah
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):

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 }```
• 10-27-2012, 03:16 AM
SJF
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!
• 10-27-2012, 11:05 AM
Kareem Mesbah
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.
• 10-27-2012, 03:12 PM
JosAH
Re: knight's tour problem
Quote:

Originally Posted by Kareem Mesbah
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
• 10-27-2012, 11:12 PM
Kareem Mesbah
Re: knight's tour problem
Quote:

Originally Posted by JosAH
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 :)