Win a copy of The Java Performance Companion this week in the Performance forum!

# recursion

renata wong
Greenhorn
Posts: 4
I wrote a method, which, using backtracking, is to produce all the possible move sequences of a knight from a corner square to all the other corner squares each time. There are two conditions:
1) Every corner square must be visited exactly once by the knight,
2) Every non-corner square may be visited at most once by the knight or not at all.
All squares on the board are 'false' at the beginning. Each square acquires the value 'true' whenever visited by the knight (after backtracking it is again false).Hence, the starting corner square will automatically be 'true'.

After the first sequence of moves, the method should go back one or more steps and try to find another possible way for the knight, and so on, itll it find all the sequences. The problem is, that this method produces only one move sequence each time and it stops.

Does anyone know, how to get ALL the possible move sequences by starting the programm only once?

Below is a simplified version of the method I wrote:

int[] xMoves = {0, 1, 1, -1, -1, 2, 2, -2, -2};
int[] yMoves = {0, 2, -2, 2, -2, 1, -1, 1, -1};

public void setKnight(int x, int y)
{
boolean jumped = false;
board[x][y] = true; // the particular field is visited

int movesList = 0; // List of moves = 8

while(movesList < 8)
{
movesList++;
if(!cornersReached() && squareExists(x + xMoves[movesList], y + yMoves[movesList]) && squareIsFree(x + xMoves[movesList], y + yMoves[movesList]))
{
jumped = true;
setFieldVisited(x + xMoves[movesList], y + yMoves[movesList]);
setKnight(x + xMoves[movesList], y + yMoves[movesList]);
}
}

if (jumped == false)
{
board[x][y] = false;
}

}
}

[ June 05, 2004: Message edited by: renata wong ]
[ June 05, 2004: Message edited by: renata wong ]

Tim West
Ranch Hand
Posts: 539
The board, and the knight's possible moves, together create an undirected graph. Your method of traversal treats it a bit like a tree, though - I assume that you won't let the knight jump onto a square it's already visited before.

Basically, I think you're describing a depth-first search through an undirected graph. Googling round for the obvious terms should lead to some algorithms. It's a nontrivial task, I think you'd do well to read up on some theory before jumping in to coding. YMMV, though.

Cheers,

--Tim

renata wong
Greenhorn
Posts: 4
Hello Tim,

Thanks for reply. You are right, the knight cannot step on a square that is visited. It was assumed in the method squareIsFree().

The problem is already solved, or at least seems to be. There had been a few, but crucial, steps to be changed in the algorithm. And it works now. I think, it shows all the possible results. But I wonder whether it is possible to get over 3000 results for a chessboard of 25 squares (5 * 5)?

Thanks once more time,
Renata
[ June 11, 2004: Message edited by: renata wong ]

Stefan Wagner
Ranch Hand
Posts: 1923
Well - it's running for some minutes since I replaced the (missing) InOut.getInt () with '8' for Fieldsize.

Could you edit your post, and surround the code with [ code] - tags [ /code]?
Makes it much more readable (I hope).

renata wong
Greenhorn
Posts: 4
Hello,

Is it better now?

There sould be a notification "ENDE" when all the results are found. I tried it with a board size 5 and it run for about 30 seconds and then gave the notification ENDE. So, the algorithm seems to work.

Renata

Stefan Wagner
Ranch Hand
Posts: 1923
Is it better now?
Can't you see it?

Much better!
Well - the longest line is damaging te page in some way, making it too wide.
Moving the comment 'Index der Zugmï¿½glichkeiten...' to a separate line would heal it.

And it worked for 5 too on my system, for 6 I had to stop it after some minutes, because the log-file grew and grew, and for 8 the process of printing didn't even start in half an hour.
I didn't expect such a duration

Should buy a small cluster for this kind of work ...

renata wong
Greenhorn
Posts: 4
8,121,130,233,753,702,400

That is the estimate number of all possible move sequences of a knight on a 8*8 chess board, when the knight has to visit every square of the board. I suppose there should be even more solutions for the knight visiting the 4 edges exactly once and the other squares at most once.

For the board 6*6 there should be about 10 thousand possible sequences.

The article is here: http://www.behnel.de/knight.html
[ June 11, 2004: Message edited by: renata wong ]