8 Queens

[Brad0407]

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.
[edit]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

[Rashakil Fol]

Your 'rules' don't much sense to me. Here's my solution:

head (queens 8)

See sig for details.

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

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

[pianorain]

Originally Posted by Rashakil Fol

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

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:

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.

[Perspective]

This is the most standard programming languages homework assignment around. I'm surprised the spec doesn't say to write it in Lisp.

[Rashakil Fol]

Originally Posted by pianorain

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

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'...

[abachler]

I think he means 'calculation' when he says 'algorithm'. This smells awfully like a homework assignment..

so here is my solution -

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.

[Brad0407]

Guess maybe this contest was too hard...
If there are no actual attempt in a week, I'll post a solution. Maybe a few.

[Daved]

I'm not sure anybody understands what you're asking.

[Happy_Reaper]

Or, rather, why Rashakil Fol's answer isn't correct.

[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!

[abachler]

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?

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.

[@nthony]

Isn't this problem the "Hello World" of learning recursion? (that and string permutations)

[Brad0407]

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:

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.

[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.

[Darryl]

Here's some solutions that list all 92 solutions http://www.cppworld.com/forum/index.php?showtopic=852