# 8 Queens

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 06-15-2007
8 Queens
Goal of 8 Queens
On an 8 by 8 board, place 8 chess queens so that no queen attacks any other queen. A queen can attack horizontally, vertically, or diagonally.

Contest
Write an algorithm that will find a solution to the 8 queens problem.

Rules
There will be one queen in each column. The algorithm must decide the row that each queen should be in.
Since this problem lends itself to artifical intelligence, your intelligent agent cannot know anything else about the problem other than the definition. This means that it cannot know the solution. However, heuristics are allowed.[/edit]
The algorithm can place the queens on the board in the correct pattern or it can start with all the queens on the board and move them to the correct pattern. If the algorithm starts with the queens on the board, it must either use an algorithm to place them or start with the queens in random rows in each column.

Judging
I will add this later
• 06-15-2007
Rashakil Fol
Your 'rules' don't much sense to me. Here's my solution:
Code:

`head (queens 8)`
See sig for details.

Edit: here's an alternate solution, in C:
Code:

```void queens8(void) {     puts("[(1,4),(2,2),(3,7),(4,3),(5,6),(6,8),(7,5),(8,1)]"); }```
• 06-15-2007
pianorain
Quote:

Originally Posted by Rashakil Fol
Edit: here's an alternate solution, in C:
Code:

```void queens8(void) {     puts("[(1,4),(2,2),(3,7),(4,3),(5,6),(6,8),(7,5),(8,1)]"); }```

I thought of that same solution, but I think he's got it covered in this part:
Quote:

Originally Posted by Brad0407
If the algorithm starts with the queens on the board, it must either use an algorithm to place them or start with the queens in random rows in each column.

• 06-15-2007
Perspective
This is the most standard programming languages homework assignment around. I'm surprised the spec doesn't say to write it in Lisp.
• 06-15-2007
Rashakil Fol
Quote:

Originally Posted by pianorain
I thought of that same solution, but I think he's got it covered in this part:
Quote:

If the algorithm starts with the queens on the board, it must either use an algorithm to place them or start with the queens in random rows in each column.

This is where I am not understanding him. What does it mean for an algorithm to start with the queens on the board? Mine doesn't, I guess, so that rule doesn't apply to my algorithm. And if by some definition it did, I am in fact using an algorithm to place the queens ("place the first at (1,4), another at (2,2)," and so on). Unless Brad would care to suggest some unorthodox definition of 'algorithm'...
• 06-18-2007
abachler
I think he means 'calculation' when he says 'algorithm'. This smells awfully like a homework assignment..

so here is my solution -

Code:

```x = 0; while(!solution(x)) x++;```
now you just need to write the BOOL solution() function and have it return whether X is a valid solution.

oh, and on a 3.2 GHz processor, it will only take a month to find a solution (maybe less), since there are only 178,462,987,637,760 (thats 178 trillion) possibilities, and more than 1 is valid.
• 06-18-2007
Guess maybe this contest was too hard...
If there are no actual attempt in a week, I'll post a solution. Maybe a few.
• 06-18-2007
Daved
I'm not sure anybody understands what you're asking.
• 06-18-2007
Happy_Reaper
Or, rather, why Rashakil Fol's answer isn't correct.
• 06-18-2007
AverageSoftware
This puzzle is straight out of The 7th Guest. The bishop puzzle is much harder, and would make a much better algorithm.

If you haven't played The 7th Guest, a pox upon you!
• 06-18-2007
abachler
Quote:

Originally Posted by Brad0407
If there are no actual attempt in a week, I'll post a solution. Maybe a few.

Is that when its due?

Quote:

Originally Posted by abachler
it will only take a month to find a solution

I misspoke, theres a simple optimization that lets you brute force it in 40,320 tries or less.
• 06-18-2007
@nthony
Isn't this problem the "Hello World" of learning recursion? (that and string permutations)
• 06-18-2007
abachler, I don't even start college until August and won't be taking an A.I. class for at least a year after that. You jumping to conclusions is slightly insulting and annoying. You got your first solution from 64*63*62*61*60*59*58*57. However, any fool would write the loops like this:
Code:

```for (Q1 = 0; Q1 < 57; Q1++) {                for (Q2 = Q1; Q2 < 58; Q2++)         {                 for (Q3 = Q2; Q3 < 59; Q3++)                 {                         for (Q4 = Q3; Q4 < 60; Q4++)                         {                                 for (Q5 = Q4; Q5 < 61; Q5++)                                 {                                         for (Q6 = Q5; Q6 < 62; Q6++)                                         {                                                 for (Q7 = Q6; Q7 < 63; Q7++)                                                 {                                                         for (Q8 = Q7; Q8 < 64; Q8++)                                                         {                                                                                                                         }                                                 }                                         }                                 }                         }                 }         } }```
That's 10.4 billion. Then you realized that when you place the queens, you can do it one column at a time and check that no queens are in the same row giving you 8*7*6*5*4*3*2*1. This can still be easily beaten with a hill-climbing algorithm starting in random places.
• 06-19-2007
pianorain
How is this a contest and not a 'please write this function for me'? How would we compete with one another? The lack of details makes this look exactly like any of the 'do my homework' threads, regardless of an actual lack of assignment.

I think it's safe to say that when there's a wiki page that explains several different methods on how to solve the problem and several alternate variations of the problem that have also been studied, this one's been done. Try making this interesting.
• 06-19-2007
Darryl
Here's some solutions that list all 92 solutions http://www.cppworld.com/forum/index.php?showtopic=852
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last