Parallel algorithm to solve a Knight’s Tour problem variation(Matthew McGowan)

The included source code implements a variation of the Knight’s Tour problem that counts the number of possible tours of a given length in parallel, as described in the included problem description text file. The algorithm enumerates legal, acyclic paths that are half of the given length and then matches up the endpoints of different half tours to identify and count the number of tours that will return the knight to the original square. After some analysis, it is determined that the matching of the half tours was the most compute intense portion of the algorithm. This recursive computation is parallelized through Java threads by spawning tasks at different levels of the recursion (in order to not have too many tasks with little or no work to be done). Several coding and memory access optimizations that were implemented are included in the write-up. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application.

DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

There are downloads available under the Creative Commons License license. Download Now

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.