Las Vegas Does N-Queens
Timothy J. Rolfe
This is available in the Word format mandated by ACM SIGCSE inroads
Published in inroads (bulletin of the ACM SIG on Computer Science Education), Vol. 38, No. 2 (June 2006), pp. 37-38.
Abstract
Keywords
Introduction
Finding a single solution for the problem of placing n queens on an n by n grid can be done in O(n) time by the deterministic algorithm reported by Hoffman, Loessi and Moore in their article in the 1969 Mathematics Magazine [1]. It was referenced in 1991 by Bernhardsson in a note to the ACM SIGART Bulletin [2]. Bernhardsson was responding to a 1990 article by Sosič and Gu in the ACM SIGART Bulletin [3], presenting a probabilistic algorithm that was reported to run in polynomial time. Sosič and Gu later published an expansion of their work in IEEE Transactions on Systems, Man, and Cybernetics [4].
This paper presents alternative probabilistic algorithms that are simpler than Sosič and Gu’s algorithm and thus may be useful in teaching probabilistic algorithms. One is based on starting from a random permutation vector but then doing a controlled swap of row positions within the vector based on collisions without explicitly computing and tracking the collisions within the present working vector. The other is based on retaining a boolean matrix indicating row positions under attack from above, and then positioning successive queens in random positions not under attack.
The first algorithm was developed in the context of building a problem set for the Pacific Northwest regional ACM International Collegiate Programming Contest [5] and provided one of the two independent judges’ solutions to the problem. It was correctly solved by four out of 87 teams
Algorithm One
The board is represented by a permutation vector giving the positions of the n queens in the n rows. This means that there are necessarily no attacks either horizontally or vertically; one only needs to check for the two diagonal attacks. These can be tracked by the vectors first introduced by Niklaus Wirth in his 1971 article in the Communications of the ACM [6] and later included in his Algorithms and Data Structures [7]. One vector flags the diagonals of constant (row–col); the other flags the diagonals of constant (row+col).
repeat
set valid to true
shuffle the current permutation vector
set the two diagonal vectors to all false
mark the row 0 queen in the two diagonal vectors
for row = 1 to n-1
set test = row+1
while this queen is on an in-use diagonal
if test = n
set valid to false
break out of the while loop
else
swap positions row and test
increment test
end if/else
end while
if not valid
break out of the for loop
mark this row’s queen in the diagonal vectors
end for
loop until valid
The implementation of this algorithm (in the context of the ACM ICPC problem statement) is available on the author’s web site [8]. The following table reflects computations on a Dell desktop computer with Intel Pentium-4 3.80GHz CPU under Windows-XP Professional and Java version 1.5.0_04.
|
Computation of 1000-Queens Solutions |
||||
|
Time (seconds) |
12.016 |
37.937 |
2.047 |
30.094 |
|
Permutation Vectors Used |
55,518 |
175,805 |
9,490 |
138,681 |
Parallel Execution
This algorithm also supports parallel execution. One simply needs to insure that the parallel threads or processes are using different seeds for their random number generators. Then one needs to establish a method of communicating among the threads the fact that one of them has obtained a valid solution. In the author’s Java implementation, this was achieved by having a static variable within the thread class initialized to null, and then set to the first successful solution. All threads in their computations check the state of that variable and exit immediately when it is found to be non-null. The parallel code is in the same location on the author’s web site [8] as the single-processor code.
Algorithm Two
This is a significantly slower algorithm than the first, and was suggested by the start-up of Sosič and Gu’s Queen Search 3 algorithm in their IEEE Transactions article. Retain information about cells within the rows of the board that are under attack from above. Starting from the top, randomly position the queen in each row in one not currently under attack. If there are no such positions, discard that trial solution and begin a new trial solution.
repeat
set valid to true
boolean matrix blocked[n][n] set to all false
for row = 0 to n–1
randomly select col as an unblocked cell
if there is NO unblocked cell
set valid to false and break from for loop
save col as part of the solution vector
for all rows below the current row
mark as blocked the col cell
also diagonal cells blocked by [row][col]
end for
end for
loop until validThough significantly slower than Algorithm One, Algorithm Two (nicknamed GridSearch) does execute rapidly enough that it meets the timing criterion from the regional programming contest mentioned above (problem size up to 300, and program completion within 120 seconds). Indeed, it is possible that this may have been among the solutions submitted.
The C implementation of this algorithm is also on the above mentioned web site [8]. A Java implementation would also support parallel execution in threads similar to that for Algorithm One.
The following table reflects computations on a Dell computer with Intel Pentium-4 3.00GHz CPU under Ubuntu Linux version 2.6.12-8-686-smp and gcc version 3.4.5.
|
Computation of 1000-Queens Solutions |
||||
|
Time |
39.250 |
426.600 |
1508.570 |
563.920 |
|
Trials |
1,323 |
14,025 |
49,466 |
18,574 |
Acknowledgement
The author heard of a probabilistic algorithm to obtain a single solution to the n-queens problem involving row swaps from Dr. Ray Hamel. Algorithm One was developed based on that, though it turned out differing significantly from the algorithm that Ray described.
References