8 Queens

This is a discussion on 8 Queens within the Contests Board forums, part of the Community Boards category; Goal of 8 Queens On an 8 by 8 board, place 8 chess queens so that no queen attacks any ...

  1. #1
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341

    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.
    [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
    Last edited by Brad0407; 06-15-2007 at 09:38 PM.
    Don't quote me on that... ...seriously

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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)]");
    }
    Last edited by Rashakil Fol; 06-15-2007 at 01:49 PM.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by Rashakil Fol View Post
    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 View Post
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    This is the most standard programming languages homework assignment around. I'm surprised the spec doesn't say to write it in Lisp.

  5. #5
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by pianorain View Post
    I thought of that same solution, but I think he's got it covered in this part:
    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'...
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    Last edited by abachler; 06-18-2007 at 10:20 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #7
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Guess maybe this contest was too hard...
    If there are no actual attempt in a week, I'll post a solution. Maybe a few.
    Don't quote me on that... ...seriously

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    I'm not sure anybody understands what you're asking.

  9. #9
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Or, rather, why Rashakil Fol's answer isn't correct.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  10. #10
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    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!
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Brad0407 View Post
    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 View Post
    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.
    Last edited by abachler; 06-18-2007 at 04:56 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  12. #12
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    Isn't this problem the "Hello World" of learning recursion? (that and string permutations)

  13. #13
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    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.
    Don't quote me on that... ...seriously

  14. #14
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  15. #15
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Here's some solutions that list all 92 solutions http://www.cppworld.com/forum/index.php?showtopic=852
    Last edited by Darryl; 06-19-2007 at 08:44 AM.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Queens, problem with searching 2D array
    By Sentral in forum C++ Programming
    Replies: 35
    Last Post: 03-11-2009, 04:12 PM
  2. Problems with the eight queens problem
    By Wicket in forum C++ Programming
    Replies: 1
    Last Post: 06-12-2008, 09:29 AM
  3. 8 Queens problem
    By Dashing Boy in forum C++ Programming
    Replies: 14
    Last Post: 10-15-2007, 12:12 PM
  4. and this is my solution for the 8 queens puzzle
    By negevy in forum C Programming
    Replies: 1
    Last Post: 09-01-2005, 11:45 AM
  5. 8 Queens
    By PutoAmo in forum C Programming
    Replies: 2
    Last Post: 03-24-2003, 03:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21