Thread: 8 Queens

  1. #16
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Wow...you're right. It is fun.
    Code:
    #include<stdlib.h>
    #include<stdio.h>
    int OO(int O0O,int*OOO,int O00){for(OOO=malloc(sizeof
    (int)*O0O),O00=0;O00<O0O;OOO[O00]=O00<O0O/2?O0O&#37;12==3
    ||O0O%12==9?O00!=O0O/2-!0?O00*2+4:2:O00*2+2:O0O%12==2
    ?O00==O0O/2?3:O00==O0O/2+1?1:O00==O0O-1?5:(O00-O0O/2)
    *2+3:O0O%12==3||O0O%12==9?O00==O0O-2?!0:O00==O0O-1?3:
    (O00-O0O/2)*2+5:O0O%12==+8?(O00-O0O/2)&!0?(O00-O0O/2)
    *2-!0:(O00-O0O/2)*2+3:(O00-O0O/+2)*2+1,O00++);for(O00
    =0;O00<+O0O;O00++)printf("{%d, %d} ",O00+1,OOO[+O00])
    ;printf("\n");free(OOO);return!+1;}int O(int O0O,char
    *OO0[],int*OOO,int O00){O0O=O0O<+2?8:atoi(OO0[+O00]);
    return(O0O<O00||(O0O>O00&&O0O<4)?O00:OO(O0O,OOO,O00))
    ;}int main(int O0,char*OO[]){return O(O0,OO,NULL,1);}
    Brings a whole other meaning to the phrase "code block". Not only does it solve the 8 queens problem, but it solves n-queens in general, for n == 1 and n >= 4.

    Next step: to use C++ templates to provide the solution at compile time.
    Last edited by pianorain; 06-19-2007 at 10:09 AM.
    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

  2. #17
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Thats cool

    Now can you draw a queen out of the code?

  3. #18
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    The program I came up with finds a solution in 1,485,540 moves just using a recursive trial and error method. I didn't do any algorithm research or anything. I'm sure it can be improved.
    If you understand what you're doing, you're not learning anything.

  4. #19
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by Brad0407 View Post
    You jumping to conclusions is slightly insulting and annoying.
    then it served its purpose.
    You got your first solution from 64*63*62*61*60*59*58*57.
    No, actually I got it from X! / (X-Y)! , the standard permutations formula, you just wrote it out the long way.
    However, any fool would write the loops like this:
    but you arent just any fool ...
    That's 10.4 billion.
    care to explain this result?

    Then you realized that
    so now you are a mind reader
    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.
    AKA X! where X = 8;
    This can still be easily beaten with a hill-climbing algorithm starting in random places.
    oh please great and wonderful master, please dein to cast pearls before swine and enlighten the great unwashed masses with your wisdom

  5. #20
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    >> oh please great and wonderful master, please dein to cast pearls before swine and enlighten the great unwashed masses with your wisdom

    A hill climbing algorithm is one of the simplist feasible to solve this problem. I was implying that even simple AI could beat a brute force attack.

    When I started this thread, I was hoping a few people would have a knowledge of knowledge based searching and that they would put different types of search to the test ex. hill climbing, genetic algorithms, local beam search.

    The 8 queens problem is obviously a well-known problem and that's why I chose it. I didn't realize that colleges often use it for projects or assignments so I wasn't expecting people to assume that it was an assignment.
    Don't quote me on that... ...seriously

  6. #21
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    >> care to explain this result
    First of all, I was being dumb when I wrote than loop because it should look like this:
    Code:
    for (Q1 = 0; Q1 < 57; Q1++)
    {	
    	for (Q2 = Q1 + 1; Q2 < 58; Q2++)
    	{
    		for (Q3 = Q2 + 1; Q3 < 59; Q3++)
    		{
    			for (Q4 = Q3 + 1; Q4 < 60; Q4++)
    			{
    				for (Q5 = Q4 + 1; Q5 < 61; Q5++)
    				{
    					for (Q6 = Q5 + 1; Q6 < 62; Q6++)
    					{
    						for (Q7 = Q6 + 1; Q7 < 63; Q7++)
    						{			
    							for (Q8 = Q7 + 1; Q8 < 64; Q8++)
    							{
    								
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    }
    You wouldn't place a second queen in spot 0 if you placed the first queen in spot 1 because you would know that at some previous point, you placed the first queen in spot 0 and the second queen in spot 1. You would be sure that the second queen is in a higher spot than the first queen. Because one queen is indistinguishable from another, order doesn't matter. Therefore, you would not use a permutation but rather a combination which is what this loop does. The result is 4,426,165,368 cycles. 4.4 billion. The 10.4 billion was a result of rushed coding.

    To pianorain:
    I'll give you props, that is pretty funny. :-D
    Don't quote me on that... ...seriously

  7. #22
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    A genetic algorithm is a particularly poor way to solve this problem. It would perform no better than a brute force without considerable thought given to the chromosome design and genetic operations. Crossover and mutation just wouldn't cut it; you'd need some sort of design such that you could rank the fitness of each allele separately to preserve good genetic material. I've seen an implementation of a genetic algorithm for the 8 queens problem. I wasn't terribly impressed. I have a feeling that few programmers would choose to use one of the methods you suggested to solve this one, especially when the problem can be solved using simpler means.
    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

  8. #23
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Ok, write a solution to the problem that uses simpler means and I'll try to write a genetic algorithm that out performs it.
    Don't quote me on that... ...seriously

  9. #24
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Already done; see my previous solution. n-queens can be solved in linear time. A genetic algorithm can't even come close to that.
    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

  10. #25
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Genetic algorithms are only suitable for certain classes of problems, of which 8 queens is not one. While you can use a GA to solve any problem that has a finite solution space, it is inefficient to do so. Its just not the most appropriate tool. You could also say that perceptrons could solve 8 queens, and they can, but not efficiently. ultimately, direct brute force with optimizations is the fastest most efficient way to 'solve' this problem. The fact that 8 queens is a solved problem specifically makes it useful for calculating the efficiiency of new solution methods.

  11. #26
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by Brad0407 View Post
    Ok, write a solution to the problem that uses simpler means and I'll try to write a genetic algorithm that out performs it.
    I have already given the simplest solution for the 8 queens problem. And it runs in constant time.

    Edit: Oh I see you've modified the problem statement. Now define precisely what it means to "know" the solution, so I can get around it with an easy loophole.
    Last edited by Rashakil Fol; 06-20-2007 at 09:00 AM.
    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.

  12. #27
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    My original solution
    Code:
    x = 0;
    while(!solution(x)) x++;
    is still the simplest, and in fact it will solve any problem with an enumerated solution space

    the poster is just too lazy to write the simple function of determining if x is a solution or not, and since I strongly suspect this is a homework assignment, Ill wait until
    Quote Originally Posted by Brad0407 View Post
    If there are no actual attempt in a week, I'll post a solution. Maybe a few.
    passes, then ill post a solution
    Last edited by abachler; 06-20-2007 at 09:14 AM.

  13. #28
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    >> the poster is just too lazy to write the simple function of determining if x is a solution or not
    Code:
    bool Solution(int Queens[8])
    {
    	int i, j, k;
    	for (i = 0; i < 8; i++)
    	{
    		// Check for queens in the same row
    		for (j = Queens[i] - (Queens[i] &#37; 8); j < Queens[i]; j++)
    			for (k = 0; k < 8; k++)
    				if (Queens[k] == j)
    					return false;
    				
    		for (j = Queens[i] - (Queens[i] % 8) + 7; j > Queens[i]; j--)
    			for (k = 0; k < 8; k++)
    				if (Queens[k] == j)
    					return false;
    			
    		// Check for queens in the same column
    		for (j = Queens[i] - 8; j >= 0; j -= 8)
    			for (k = 0; k < 8; k++)
    				if (Queens[k] == j)
    					return false;
    	
    		for (j = Queens[i] + 8; j < 64; j += 8)
    			for (k = 0; k < 8; k++)
    				if (Queens[k] == j)
    					return false;
    
    		// Check for queens diagonally
    		if ((Queens[i] % 8) != 0)
    		{
    			for (j = Queens[i] - 9; j >= 0; j -= 9)
    			{
    				for (k = 0; k < 8; k++)
    					if (Queens[k] == j)
    						return false;
    				if ((j % 8) == 0)
    					break;
    			}
    
    			for (j = Queens[i] + 7; j < 64; j += 7)
    			{
    				for (k = 0; k < 8; k++)
    					if (Queens[k] == j)
    						return false;
    					
    				if ((j % 8) == 0)
    					break;
    			}
    		}
    
    		if ((Queens[i] % 8) != 7)
    		{
    			for (j = Queens[i] - 7; j >= 0; j -= 7)
    			{
    				for (k = 0; k < 8; k++)
    					if (Queens[k] == j)
    						return false;
    				
    				if ((j % 8) == 7)
    					break;
    			}
    			for (j = Queens[i] + 9; j < 64; j += 9)
    			{
    				for (k = 0; k < 8; k++)
    					if (Queens[k] == j)
    						return false;
    		
    				if ((j % 8) == 7)
    					break;
    			}
    		}
    	}
    	return true;
    }
    That may or may not work. I haven't tried it. It takes the input of the 8 queens with a single integer to represent each. A queen in location (0, 0) would be represented as 0. A queen in location (5, 4) would be represented as 37.
    [edit]Tested[/edit]
    Last edited by Brad0407; 06-20-2007 at 10:50 AM. Reason: corrections to code
    Don't quote me on that... ...seriously

  14. #29
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    And of course, a brute force solution:
    Code:
    int main()
    {
    	int Queens[8], i;
    	int SolutionCount = 0;
    	for (Queens[0] = 0; Queens[0] < 8; Queens[0]++)
    		for (Queens[1] = 8; Queens[1] < 16; Queens[1]++)
    			for (Queens[2] = 16; Queens[2] < 24; Queens[2]++)
    				for (Queens[3] = 24; Queens[3] < 32; Queens[3]++)
    					for (Queens[4] = 32; Queens[4] < 40; Queens[4]++)
    						for (Queens[5] = 40; Queens[5] < 48; Queens[5]++)
    							for (Queens[6] = 48; Queens[6] < 56; Queens[6]++)
    								for (Queens[7] = 56; Queens[7] < 64; Queens[7]++)
    									if (Solution(Queens))
    									{
    										for (i = 0; i < 8; i++)
    											printf("(&#37;d,%d) ", Queens[i] / 8, Queens[i] % 8);
    										printf("\n");
    										SolutionCount++;
    									}
    	printf("Found %d solutions.\n", SolutionCount);
        return 0;
    }
    Last edited by Brad0407; 06-20-2007 at 10:54 AM.
    Don't quote me on that... ...seriously

  15. #30
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Faster check for solution:
    Code:
    bool Solution(int Queens[8])
    {
    	int i, j, k;
    	for (i = 0; i < 8; i++)
    	{
    		for (j = 0; j < i; j++)
    		{
    			// Same row
    			if ((Queens[i] / 8) == (Queens[j] / 8))
    				return false;
    
    			// Same column
    			if (((Queens[i] - Queens[j]) &#37; 8) == 0)
    				return false;
    
    			// Diagonally
    			if (abs((Queens[i] / 8) - (Queens[j] / 8)) == abs((Queens[i] % 8) - (Queens[j] % 8)))
    				return false;
    		}
    
    		for (j = i + 1; j < 8; j++)
    		{
    			// Same row
    			if ((Queens[i] / 8) == (Queens[j] / 8))
    				return false;
    
    			// Same column
    			if (((Queens[i] - Queens[j]) % 8) == 0)
    				return false;
    
    			// Diagonally
    			if (abs((Queens[i] / 8) - (Queens[j] / 8)) == abs((Queens[i] % 8) - (Queens[j] % 8)))
    				return false;
    		}
    	}
    	return true;
    }
    Don't quote me on that... ...seriously

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, 04:45 AM