| Projects |
|---|
|
Software
AJZaurusUSB
NQP (N-Queens Problem) |
| Links |
|---|
|
Handheld-Linux Letux OpenMoko http://www.oesf.org http://www.macrumors.com http://www.osxentwicklerforum.de |
| Information |
|---|
|
Impressum Contact |
The N-Queens Problem (NQP)
New: Discussion Forum: http://www.dsitri.de/phpBB2/viewforum.php?f=8
Posed for 8 Queens in 1850 by Carl Friedrich Gauß (according to [gu91]
by Nauck), the N-Queens problem is as follows:
|
|
Solutions
Solutions exist for N=1 and any N>3. One of the 92 solutions for N=8 is shown here:
Solvers
Although solutions can be found by construction for N=1 and all N>3, many researchers have tried to find solutions by different methods with different success to demonstrate the properties of the methods (divide and conquer, search methods, neural networks). The following table summarizes what the authors have achieved.
| author | method | max. N solved | year | references |
|---|---|---|---|---|
| Gauß, Nauck | trial and error | 8 | 1850 | [dudn89], [gu91] |
| several | systematic construction | all N>3 | >1850 | [abyu89], [bern91], [lore93], [shag92], [sogu91] |
| Stone, Stone | depth first search | 96 | 1987 | [stst87] |
| Page, Tagliarini | Hopfield network | 10 | 1987 | [tapa87] |
| Kajura, Akiyama, Anzai | Boltzmann machine | 1000 | 1989 | [kaa89] |
| Adorf, Johnston | GDS | 1024 | 1989 | [ador89], [adjo90], [joad89] |
| Abramson, Yung | divide and conquer | all N>39 | 1989 | [abyu89] |
| Sosic, Gu | local search, conflict minimization | 3000000 | 1990 | [sogu90], [sogu91a], [sogu91b] |
| Chen, Wu | Parallel PROLOG | ? | 1991 | [chwu91] |
| Nakagawa, Kitagawa | SDNN | 3000 | 1991 | [naki91], ... |
| Miller | depth first search | 64 | 1992 | [mill92] |
| Shagrir | Hopfield Network | 100 | 1992 | [shag92] |
| Mandziuk, Macukow | Hopfield Network | 8 | 1992 | [mama92] |
| Mandziuk | Hopfield Network | 80 | 1995 | [mand95] |
| Ali, Turner, Homifar | Genetic Algorithm | 200 | 1992 | [hta92] |
| Minton, Johnston, Philips, Laird | heuristic repair | 1000000 | 1992 | [mjpl90], [mjpl92] |
| Takefuji | Minimum network | 100 | 1992 | [take92] |
| Lorenz | GDS | 6001 | 1993 | [lore93] |
| Schaller | DBNN | 200 | 1994 | [scha94], [scha95] |
Links to other locations discussing the N-Queens Problem
- Peter Alfeld
- John F. Chionglo
- Tim Duncan - appears to be invalid
- Rok Sosic
Suggestions, Corrections, Additions
If you have any suggestions for, corrections of, additions to this page, please contact me.Oct 2001
H.-M. Adorf (adorf@interval-logic.com) sent me some more references:- Campbell, P. J. (1977). "Gauss and the Eight Queens Problem: A Study in Miniature of the Propagation "" Historia Mathematica 4: 397--404.
- Polya, G. (1918). Über die "doppelt-periodischen" Lösungen des n-Damen-Problems. Mathematische Unterhaltungen und Spiele II. W. Ahrens: 364--374.
- Hoffmann, E. J., J. C. Loessi, et al. (1969). "Constructions for the Solution of the n Queens Problem." Mathematics Magazine 42: 66--72.
- Bruen, A. and R. Dixon (1975). "The n-Queens Problem." Discr. Math. 12: 393--395.
Jan 2002
I found the following message from comp.soft-sys.matlabView:
From: Roger Stafford (roger.ellie@mindspring.com)
Subject: Re: Help! Please!
Newsgroups: comp.soft-sys.matlab
Original Date: 2001-06-18 17:32:15 PST
... [cut out by the editor] ...
You might take a look at some of these web sites:
http://www.dsitri.de/wiki?page=NQP
http://www.cs.mcgill.ca/~ramadan/projects/605/project-summery.html
http://www.pvv.org/~hgs/java/queens/help.html
http://www.cwi.nl/~arrayas/abstracts.html
http://www.gams.com/modlib/libhtml/queens.htm
http://www.mactech.com/articles/mactech/Vol.13/13.12/TheEightQueensProblem/index.html
http://bridges.canterbury.ac.nz/features/eight.html
http://www-personal.umich.edu/~smueller/mathpsyc/queens/index.html
Roger Stafford