Solving the 24-queens Problem using MPI on a PC Cluster
Kenji Kise, Takahiro Katagiri, Hiroki Honda, Toshitsugu Yuba · 2004
The N-queens is a problem to place N queens on an N N chessboardsuchthatnoqueencanattackanother. We designed a sequential program which attains an improvement in speed of from 7% to 14% compared to current programs. The proposed program is parallelized using MPI, and the numberof solutions for the 24-queensproblem is calculated forthefirst time. The mainfindingsof the present study are as follows: (1) The optimization of memory reference and control structure increases speed from 7% to 14% in the sequential program. (2) A master-worker scheme is effective for parallelization. (3) The Hyper-threading technology of the Pentium4 processor provides an increases in speed of approximately 30%. (4) In the solution of a real problem, it is important to consider the efficiency of the entire system.