This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.

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:

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

Joined: May 14, 2004
Posts: 4

posted

0

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 ]

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.

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

Joined: May 14, 2004
Posts: 4

posted

0

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.