# Thread: knight's tour problem

1. Member
Join Date
Sep 2012
Posts
15
Rep Power
0

## 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. Senior Member
Join Date
Oct 2012
Posts
108
Rep Power
0

## 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. Member
Join Date
Sep 2012
Posts
15
Rep Power
0

## 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. ## Re: knight's tour problem

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

5. Member
Join Date
Sep 2012
Posts
15
Rep Power
0

## Re: knight's tour problem

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 :)

#### Posting Permissions

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