The KT problem (just in case you are not familiar with it)
involves finding a path by which a knight can visit every square
on the chess board exactly once, returning to the square it
originally started from. Very many such routes exist but they are
difficult to discover by hand.





1  .  .  .  6 
.  .  K  .  . 
0  .  .  .  7 
.  2  .  5  . 
Knight's 8 potential moves as defined in the algorithm's MoveDef object
We evaluate each potential move in turn. Having recorded a new move into the array we recursively call our Move method to commence evaluation of the moves now open to us from the new square. If a move turns out to be a deadend then we simply exit the current Move method and we fall back into the underlying previous move position. The Move method when returned to clears the last (now finished branch) move and continues to search for the next one. In this way we build up and tear down the solution search tree. We know that we have found a possible solution when our search depth (or jumpnum) reaches the number of squares on the board. However we need to confirm that the knight could reach the initial square from the final square so that we can say that it has completed the tour. The Move method then exits so that further possible solutions can be explored from branches below.
Not all solutions are unique as there will always be identical solutions around all the lines of symmetry; horizontal, vertical, diagonal and rotational. We can use this feature to avoid undertaking some unnecessary early search branches. We should always start the search from one corner (0, 0). Now from a corner square there are only two possible initial jumps, labelled 5 and 7 in the diagram above (the solution gets rendered in the SE quadrant). Given that we would only repeat solutions around a diagonal line of symmetry if we search with both move 5 and 7 as an initial move we can reduce the solution time by half if we only ever commence with move 5. An implication of this is that the last move of the tour must always be to the square that we would end up on if we make move 7 from (0,0). So we can further enhance the algorithm by reserving this square (2, 1) so that solution trees don't use this square until the last ever move. This optimization gives a 5 fold improvement in overall solution time.
Although we make an attempt at avoiding duplication of solutions from diagonal symmetry (because it works in our favour with regards to solution time) we are not protected from accidentally reproducing solutions which are in reality repeats of previous solutions about a particular line of symmetry; horizontal, vertical, the other diagonal or rotational. It would be possible to store all unique solutions as they are discovered and to compare with each 'normalized' new one to confirm that it is indeed unique. The algorithm doesn't do this at present it, there isn't really much need.
There is a further technique for pruning search trees at a point
at which we make a move that clearly blocks a solution path.
For every unvisited square which we could have reached with this
jump, but didn't because we made a different move, we consider if
an imaginary knight situated on these squares can now reach
another vacant square. If it can not then clearly this unvisited
square is now isolated because if the imaginary knight can't get
out, none can get in. Hence this square has been isolated from the
rest of the board by this move and consequently this particular
solution tree is now doomed. We are not going to catch all doomed
solution trees this way because we only detect isolated squares
not isolated regions. To detect regions would just bloat the
solution time too much. In fact this optimization is of marginal
value because for each jump it adds an extra 2 levels of jump
evaluation (up to 42 extra squares to consider). We have to scan
for the other squares we could have reached (which is (8  the
actual square we went to  the square we came in from) * (8  the
square we had been on > 6x7 = 42). In fact as we only
rediscover that the square we had been on is used by inspection
we have 6x8 = 48 extra squares to consider. So if the algorithm
for pruning found no solutions to deprecate the algorithm would
run about 50 times slower. For a 6x6 chess board the following is
a list of how many solution branches get pruned at each level with
this algorithm (depth and branches pruned).








































































We therefore need to restrict the range in which we run the
pruning test. Early pruning is advantageous because it removes
otherwise long branches, however it can be seen that there are not
many low level pruning opportunities. There are very many pruning
opportunities in the middle depth range, except there are very
many iterations run at these levels so the overhead of running the
test is greatly multiplied. There are two parameters hard coded in
the source Glb.PRUNE_START & Glb.PRUNE_END,
adjusting these in conjunction with different javac optimization
techniques will give different levels of performance
improvement (not all beneficial).
The threads are managed by an object called ThreadManager. The ThreadManager acts as a synchronization object for all thread interactions. To ensure that we don't corrupt the output file by writing two solutions simultaneously even the PrintBoard() method has to be implemented in this object. The assignment of threads to tasks is handled by 2 methods within this object. ReportForWork() is called by threads which have exhausted the solution branch that they had been following and have consequently fallen out of the bottom of the recursive Move() method stack. HireHelp() is called by threads which are exploring new solution branches and have had one or more out of work threads attached to them.
In ReportForWork() a newly redundant thread scans the currentDepth of all
threads to find out which one is functioning at the lowest
depth. It chooses the thread currently working at the lowest
depth because that shall be the most likely able to offer it the
longest career opportunity. The thread adds it's self to the
linked list of other optimistic helper threads which may have
attached themselves to this particular thread, then calls wait.
When a thread which is busy evaluating moves discovers that a
thread has tagged itself to it then instead of making the next
move itself it calls HireHelp() to obtain a thread to do it for it. HireHelp() pulls
the first thread off the helperThread list. It copies it's current private view of
the chess board over to the new thread's private copy and
presets the square it wants the thread to start at. Each thread
has a KnightsMove class of it's own for such private state
storage. The hiring thread then calls the new hire's inbuilt interrupt() method
to wake the thread up. If a thread with tagged helpers hits a
roadblock then it will donate all it's own helpers to the thread
which it itself nominates to join. When on a call to ReportForWork() it
is discovered that all threads are laid up we know that the
solution search is finished and that the entire program should
terminate.
If you are able to make any improvements to this code or find any bugs please let me know. Also I would be interested in any feedback with regards to execution speed and the best pruning parameters for different classes of machine or JVM. If I get a significantly varied set of data points I shall publish them.
The source code is supplied to be used by the individuals who download it from this site and may not be redistributed for profit. The source may be modified or redistributed for any legal nonprofit purpose provided reference to the original authorship is maintained.
As is traditional  ENJOY.