Las Vegas Does N-Queens

Timothy J. Rolfe
Eastern Washington University
Computer Science Department
319F Computing & Engineering Bldg.
Cheney, Washington 99004-2493 USA
http://penguin.ewu.edu/~trolfe/
trolfe@ewu.edu

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
This paper presents two Las Vegas algorithms to generate single solutions to the n-queens problem. One algorithm generates and improves on random permutation vectors until it achieves one that is a successful solution, while the other algorithm randomly positions queens within each row in positions not under attack from above.

Keywords
n-queens problem; Las Vegas algorithm; probabilistic algorithm

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 . It was referenced in 1991 by Bernhardsson in a note to the ACM SIGART Bulletin . Bernhardsson was responding to a 1990 article by Sosič and Gu in the ACM SIGART Bulletin , 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 .

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  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  and later included in his Algorithms and Data Structures . 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 . 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  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 valid```

Though 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 .  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 Required 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

1. E. J. Hoffman, J. C. Loessi and R. C. Moore, "Constructions for the Solution of the m Queens Problem", Mathematics Magazine, Vol. XX (1969), p. 66-72.  Link through JSTOR.  The construction is essentially that of A.M.Yaglom and I.M.Yaglom, Neelementarnye Zadachi v Elementarnom Izlozhenii (Moscow, 1954), translated by James McCawley, Jr., revised and edited by Basil Gordon, Challenging Mathematical Problems with Elementary Solutions:  Volume I, Combinatorial Analysis and Probability Theory (1964, reprinted by Dover 1987), pp. 92-98.
2. Bo Bernhardsson, "Explicit Solutions to the N-Queens Problems for all N", ACM SIGART Bulletin, Vol. 2, No. 2 (Apr. 1991), p.7.  Link.
3. Rok Sosič and Jun Gu, "A Polynomial Time Algorithm for the N-Queens Problem", ACM SIGART Bulletin, Vol. 1, No. 3 (xx, 1990), pp. 7-11.  Link.
4. Rok Sosič and Jun Gu, "Fast Search Algorithms for the N-Queens Problem", IEEE Transactions on Systems, Man, and Cybernetics, Vo. 21, No. 6 (Nov/Dec 1991), pp. 1572-76.  Link.
5. http://www.acmcontest-pacnw.org/ProblemSet/2005/ Problem I.
6. Niklaus Wirth, "Program Development by Stepwise Refinement", Communications of the ACM, Vol. 14, No. 4 (April 1971), pp. 221-27, specifically p. 224.  Link.
7. Niklaus Wirth, Algorithms and Data Structures (Prentice-Hall, 1986), pp. 153–57.
8. http://penguin.ewu.edu/~trolfe/QueenLasVegas/