# Thread: help on Knights tour

1. Member
Join Date
Jan 2010
Posts
1
Rep Power
0

## 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 07:43 PM. Reason: Code tags added

2. Originally Posted by frank17
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.

Smart Questions

Much luck!

3. 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 10:32 PM.

4. 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 10:31 PM.

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

#### Posting Permissions

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