Solving N-Queens Counting Problem by Using Improved Parallelized Backtracking Algorithm
Xiaohong Huang · Computer Engineering and Applications Journal · 2006
Traditional backtracking algorithm has been improved by rotating the chessboard matrix and put into solving N-queens counting problem in computer cluster.In order to improve the backtracking algorithm,the chessboard matrix can be rotated clockwise 90°,180° and 270°.The improved backtracking algorithm can solve the 16-queens counting problem in 15 s by only one CPU.The efficiency is 4.69 time faster.By locating the queens in the first three lines,the N-queens counting problem can be distributed into thousands of tasks and computed by a computer cluster with 28 CPU.The 20-queens counting problem can be computed in 8 min and the 21-queens counting problem can be computed in 1 hour and 8 minutes.The program can be used as a benchmark program for computer clusters.