Problem
The N-queens problem (Fig. 11.10) was introduced along with the managerworker approach to control decomposition in programing a multi-computer. Suppose N = 8. There are 92 possible solutions CO the 8-queens problem.
(a) Write a program that searches for a solution. First run the program on a sequential computer (such as on a workstation or even a personal computer). Record the time required to conduct die sequential search. A sequential search involves backtracking once an impossible configuration is exposed. The backtracking step systematically removes the current emplacements of the queens and then continues with a new emplacement
(b) Develop a parallel program to run on a message-passing multicomputer if one is available. Fora concurrent search for solutions to the N-queens problem, backtracking is not necessary because all solutions are equally pursued. A detected impossible configuration is simply discarded by the node. Observe the dynamics of the concurrent search activities and record the total execution time. Compare the measured execution time data and comment on speedup gain and other performance issues.
