Talk:Eight queens puzzle

From Wikipedia, the free encyclopedia

This article is within the scope of WikiProject Chess, a collaborative effort to improve Wikipedia's coverage of chess. For more information, visit the project page, where you can join the project and/or contribute to the discussion.
Chess Portal
B This article has been rated as B-Class on the quality scale.
Mid This article has been rated as Mid-Importance on the importance scale.

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)

[edit] Similar to Sudoku?

Isnt this in some way similiar to solving sudoku? Each row/column may only have one queen, is like every row may only have the same value once. Sould we include Sudoku in the Related Related Problems section? 81.221.196.70 14:17, 4 May 2007 (UTC)

Both this problem and Sudoku are examples of Exact cover problems. I've added a sentence to that effect to the Related Problems section. Oliphaunt 09:28, 5 May 2007 (UTC)

[edit] Move solution to the bottom of the page and add a spoiler warning

I came to this page to learn about the problem and try to solve it myself (and to find out if a solution was possible). The solution appears right at the top, spoiling the puzzle for those who just want to try it. —Preceding unsigned comment added by 70.171.221.203 (talk) 22:44, 27 September 2007 (UTC)

[edit] comment moved from article

217.208.53.194 added the following comment to the article. I'm moving it here. Michael Slone (talk) 13:55, 11 February 2008 (UTC)

NOTE: This animation is incorrectly programmed. After finding a solution, the program returns to a previous placement of the second queen, instead of continuing with new placements from the found solution. Therefore, it gets stuck and repeatedly finds the same solution (with the first queen on A8 and the second on E7, after finding a solution it returns to placing the second queen on C7). Totally lousy programming and testing, in other words. —Preceding unsigned comment added by 217.208.53.194 (talk • contribs)

[edit] fastest algorith

Can anyone post the pseudocode version of the fastest algorithm that can find all unique solutions for n queens? 75.87.86.76 (talk) 23:05, 17 April 2008 (UTC)