Talk:Eight queens puzzle
From Wikipedia, the free encyclopedia
Contents |
[edit] Algorithm Attribution
How about some attribution or reference for the simple algorithm? When was it discovered? Given the number of published algorithms using various kinds of search even for finding single solutions, it would seem that this has to be a fairly recent discovery? Or?
- Recent? Not really. The first proof of a simple algorithm for producing a solution to the n-queens problem for every n>=4 can be found here: Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B.G. Teubner, 1910.
- A proof in English can be found here: E.J. Hoffman, J.C. Loessi and R.C. Moore. Constructions for the Solution of the m Queens Problem. National Mathematics Magazine, March-April:66-72, 1969.
- PittBill 13:28, 20 Apr 2005 (UTC)
-
- I don't think any of those are on the Internet, so I can't check whether any of the published algorithms are simpler to follow or remember than the one in the article. If so, can you please replace the one in the article and give the source. If not, please leave it be. — 131.230.133.185 08:31, 13 Jun 2005 (UTC)
[edit] Paul Muljadi
Who is Paul Muljadi? From a quick Google search, I gather that he is a Chess buff & possibly one of the top players, but seeing how his name is mentioned in a couple of Wikipedia articles & he provides no personal information on his website (or even a clear way to navigate it), it would be nice to provide an article with a few sentences about him. -- llywrch 15:25, 24 Apr 2004 (UTC)
- I don't know who he is, but I know he's not a top player - he doesn't have a FIDE rating at all. I've never heard of him, myself. --Camembert
-
- I was being polite by saying "possibly one of the top players": I'd rather be corrected for thinking he was one, than being corrected for thinking that he was not one. For the record, I might be able to name a dozen famous chess players, but only if I could include Philip Marlowe. -- llywrch 22:59, 24 Apr 2004 (UTC)
- I came independently to the conlcusion that he was nobody in particular, that the "discoveries" described in the article were not mathematically interesting, and that he had probably placed them there himself out of vanity. I removed them, then saw this discussion on the talk page. -- Dominus 15:17, 25 Aug 2004 (UTC)
- The Integer Sequences link at the bottom of the article goes to Paul Muljadi's webpage, which announces his "discoveries". The reason I haven't removed the link is that Paul's page does list the fundamental solutions to the eight queens problem. PittBill 14:31, 28 Aug 2004 (UTC)
It seems that almost the same web page exist, here is the link: http://www.informationclub.com/encyclopedia/e/ei/eight_queens_puzzle.html
Also say:
Copyright ©2003 InformationClub.com This content from encyclopedia is licensed under the GNU Free Documentation License
--andrejj 18:55, 15 Aug 2004 (UTC)
I believe the InformationClub is copying their pages verbatim from the Wikipedia. Other entities have similar copies, such as http://www.wordiq.com and http://www.fact-index.com PittBill 23:08, 15 Aug 2004 (UTC)
[edit] Number of Solutions
- In general, the number of possible solutions of placing N queens on a N by N board, considering the symmetries as distinct solutions, is:
And then the formula is not given, only the values. -- WhiteDragon 06:26, 10 Feb 2005 (UTC)
That's because the formula is unknown. See [1] for more information on the numbers of possible solutions. PittBill 10:43, 10 Feb 2005 (UTC)
I do see WhiteDragon's point, and have removed the In general since the table only gives values for specific N's, not a general formula. PittBill 23:47, 12 Feb 2005 (UTC)
[edit] What is CLP(FD)?
What is CLP(FD)? PittBill 01:23, 6 Jun 2005 (UTC)
- Constraint logic programming over finite domains (http://www.google.com./search?btnI&q=CLP+FD). Fixed in article. — 131.230.133.185 08:31, 13 Jun 2005 (UTC)
[edit] Minimum-Conflicts Heuristic?
I think the part talking about the 'minimum-conflicts' heuristic is incorrect, because that heuristic gets trapped at local optimal solutions(i.e. no single move can improve the solution quality).
- It may get trapped, but not necessarily. It's the basic tradeoff between hillclimbing and exhaustive search. As mentioned, the gain is that the method can solve problem sizes way beyond the scope of an exhaustive search. The standard fix for 'stuck at local optimum' is to restart with a different random initial configuration.
[edit] C Program
I am missing either link or listing of brilliant sollution posted to Usenet. Philipz 09:07, 11 Sep 2005 (CEST)
#include <stdio.h>
static int count = 0;
void try(int row, int left, int right) {
int poss, place;
if (row == 0xFF) ++count;
else {
poss = ~(row|left|right) & 0xFF;
while (poss != 0) {
place = poss & -poss;
try(row|place, (left|place)<<1, (right|place)>>1);
poss &= ~place;
}
}
}
void main() {
try(0,0,0);
printf("There are %d solutions.\n", count);
}
[edit] Exact Cover
The eight-queens problem doesn't seem to be exact cover. A solution for a square larger than 1x1 can not use all the nontrivial diagonals (2x2 and 3x3 have no solutions, and for n > 3, 2n-3 > n). Should "such that every column has a 1 in precisely one of the chosen rows" be restated to "such that each of the first 2n columns has a 1 in precisely one of the chosen rows, and each other column has a 1 in at most one of the chosen rows."? Ralphmerridew 20:12, 17 January 2006 (UTC)
Maybe this should be more explicit, but it's easy to extend any problem of the form "these columns get exactly one 1 and these get at most one 1" to a normal exact cover by just adding a bunch of rows that are all zeros except for having a 1 in one of the "at most 1" rows. (Though it'll be more efficient to use an algorithm that understands the extended problem directly.) Glasser 14:04, 20 January 2006 (UTC)
[edit] Solution by Permutations in Python
Here's a simple implementation in Python that generates all 8-castles solutions by a permutations() generator, then filters diagonals by checking that the set of diagonals represented has 8 elements. I think this is a more clear solution of the problem in Python, but the article's current recursive solution is probably better for readers because it represents how the problem would be solved in most languages.
# Print all solutions to 8-queens problem. Public domain, Connelly Barnes 2006.
def permutations(L):
if len(L) <= 1:
yield list(L)
else:
for i in range(len(L)):
for p in permutations(L[:i]+L[i+1:]):
yield [L[i]] + p
def queens(n):
for L in permutations(range(n)):
if (len(set(i+L[i] for i in range(n))) == n and # Main diagonals
len(set(i-L[i] for i in range(n))) == n): # Skew diagonals
yield L
if __name__ == '__main__':
for sol in queens(8):
for col in sol:
print '.'*col + 'Q' + '.'*(8-1-col)
print
You can shorten the code significantly at the expense of clarity by using generator expressions.
- Connelly 00:29, 11 May 2006 (UTC)
[edit] 4-Queens Puzzle
..is it possible to cover a 8x8 chesstable with 4 queens?
The number of solutions for covering an n by n chessboard with 4 queens are as follows (including rotational and reflectional variants):
| n | Solutions | ||
| 5 | 5230 | ||
| 6 | 2744 | ||
| 7 | 86 | ||
| 8 | 0 |
Computed by a J program. Roger Hui 06:10, 19 May 2006 (UTC)
See the actual program. Roger Hui 17:24, 19 May 2006 (UTC)
[edit] Complexity
The statement
The GNU Prolog program below resolved a 100 queens problem in less than a tenth of a second.
is meaningless without a frame of reference. Giving at least the processor used for the test and the time of a slower algorithm would help matters greatly. Andrew J. MacDonald 03:51, 30 November 2006 (UTC)
[edit] Distinct–Unique
The article seems to be arbitrarily using the words "distinct" and "unique" with its own meanings. While it does help to make it less verbose, "unique" already has the usual meaning of being the only one of something, and it's absurd to speak of "unique solution 1, unique solution 2", etc. If at all there is a unique solution, there can be only of it. Does anyone have any suggestions on what to use in place of "unique"? ("Truly distinct", "distinct even after considering symmetries", "nonisomorphic",...) --Shreevatsa 17:49, 6 January 2007 (UTC)
