Eight Queens Problem...Tried Everything.

This is a discussion on Eight Queens Problem...Tried Everything. within the C++ Programming forums, part of the General Programming Boards category; Hey guys I purposely signed up on these forums because I have an interest in programming as a whole, and ...

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    3

    Eight Queens Problem...Tried Everything.

    Hey guys I purposely signed up on these forums because I have an interest in programming as a whole, and because I aspire to be a game programmer. I'm taking college courses now in C++, as well as teaching myself along the way.

    I know that many of you have probably heard of the eight queens problem. Placing eight queens on a chessboard such that none of them interfere with the other. There are a total of 92 possible solutions, and my CS professor wants us to solve it three different ways.

    He told us the three ways he wants it in:

    Dumb solution: Using eight "for" loops working like an odometer to represent each column.

    Smarter solution: Using 4 goto statements: "NR(Next Row), NC(Next Column), Backtrack(backtracking) and print(to print out the board).

    Smartest and most Compact solution: Using a 1D array of 8 to determine where to place the queens, acting like how a lock combination would work.

    The thing is, he showed us and gave us the basic gist of how to do it, showed us how to do all of the tests to check the row, and diagnols, but I cannot for the life of me figure out how to properly code the DUMB solution.

    Repeat: Yes...I cannot figure out how to do the dumb one. The smarter ones are easier to understand because well...that's why they're the smart solutions to the problem! But I can't figure out how to use eight for loops to solve this.

    Note: It is the beginning of the class, he assumes that we do not know about pointers or classes yet. Knowledge that he wants us to use, and ONLY this knowledge: Input, Output, Functions, Arrays.

    He did not even use functions for any of these. So really, for the dumb solution it should only use: Input, Output, Arrays.

    Also guys, I'm not asking for you to do my HW, I read the Homework topic at the top of the board, and I do NOT want anyone to solve it completely for me. It's just that I'm at my wits end with this program, I have stayed up 5 nights in a row till about 3am trying to figure this out, and it's now 3 days overdue. Help me become a better programmer and make everything clear to me please. I have a feeling that I just need someone to tell me what's wrong, or to see somebody else's take on it for a nail to fit right into place in my head.





    Here is my code:

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int arr[8][8] = {0};
    	int r, c;
    	int counter;
    	c = 7;
    	
    	//Eight "for" loops working like an odometer.
    	for(int i0 = 0; i0 < 8; i0++){
    		c = 0;
    		for(int i1 = 0; i1 < 8; i1++){
    			c = 1;
    			for(int i2 = 0; i2 < 8; i2++){
    				c = 2;
    				for(int i3 = 0; i3 < 8; i3++){
    					c = 3;
    					for(int i4 = 0; i4 < 8; i4++){
    						c = 4;
    						for(int i5 = 0; i5 < 8; i5++){
    							c = 5;
    							for(int i6 = 0; i6 < 8; i6++){
    								c = 6;
    								for(int i7 = 0; i7 < 8; i7++){
    									r = i7;
    									counter = 0;
    									arr[i0][0] = 1;
    									arr[i1][1] = 1;
    									arr[i2][2] = 1;
    									arr[i3][3] = 1;
    									arr[i4][4] = 1;
    									arr[i5][5] = 1;
    									arr[i6][6] = 1;
    									arr[i7][7] = 1;
    									
    									//row test
    									for(int i = 0; i < c; i++){
    										if(arr[r][i] == 1){
    											counter = 1;
    											for(int j = 0; j < 8; j++){
    												for(int q = 0; q < 8; q++){
    													arr[j][q] = 0;
    												}
    											}
    											if(c < 7)
    												c++;
    											
    										}
    									}
    									
    									//up diagnol test
    									for(int i = 1; (r - i) >= 0 && (c - i) >=0;i++){
    										if(arr[r - i][c - i] == 1){
    											counter = 1;
    											for(int j = 0; j < 8; j++){
    												for(int q = 0; q < 8; q++){
    													arr[j][q] = 0;
    												}
    											}
    											if(c < 7)
    												c++;
    					
    										}
    									}
    									
    									//down diagnol test
    									for(int i = 1; (r + i) < 8 && (c - i) >= 0;i++){
    										if(arr[r + i][c - i] == 1){
    											counter = 1;
    											for(int j = 0; j < 8; j++){
    												for(int q = 0; q < 8; q++){
    													arr[j][q] = 0;
    												}
    											}
    											if(c < 7)
    												c++;
    								
    										}
    									}
    									
    									//if none of the tests failed, print.
    									if(counter = 0){
    										for(int j = 0; j < 8; j++){
    											for(int q = 0; q < 8; q++){
    												cout << arr[j][q];
    											}
    											cout << endl;
    										}
    									}
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    }
    Oh, forgot to say, with this code this way, it won't print ANY solutions..so I Have a strong feeling that I messed up on the execution of the tests. The hardest part for me is figuring out how to test it each time it goes through the next row in the for loop.

    If anyone wants to take a shot at it be my guest, I'm really at my wits end here.

    Also: If I change the if(counter = 0) to if(counter == 0), it'll print out EVERYTHING. So Maybe it's something I've done wrong with either the tests, or the counter I put in as a means of checking to see if it passed all the tests.
    Last edited by Kiros_Xannon; 09-26-2009 at 09:31 PM. Reason: Forgot some information

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Code:
    if(counter = 0)
    This is why we have compiler warnings.

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    3
    umm, yeah that doesn't help I believe I put in my edit that if I change it to ==, it just prints everything out. So I'm still not getting the result of printing eight solutions out.

  4. #4
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    The "smartest" solution is pretty easy. You have a vector(an array if you will), where the x coordinate is the index, and the content is the y coordinate. Doing this, finding out whether or not a queen will interfere with a given position is pretty easy.

    E.g.:

    Code:
    int array[8];
    
    array[0] = 4; // one queen is at (0, 4)
    With that said, you should definitely take a look at Backtracking - Wikipedia, the free encyclopedia. This problem is, in most CS classes afaik, solved with backtracking, which teaches recursion(Depending on implementation) and some nifty CS problems.

    This problem is a very good candidate for backtracking due to the fact that you can determine whether or not a partial solution can become a whole solution. E.g, if you have put queens on the board up until 5, on the x-axis, and then discover that you can't put another queen on the board without it being interfered with, you know that continuing that partial solution is pointless and you abandon it.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Kiros_Xannon View Post
    umm, yeah that doesn't help I believe I put in my edit that if I change it to ==, it just prints everything out. So I'm still not getting the result of printing eight solutions out.
    That's probably because r is 12349812, as opposed to some number between 0 and 7.

  6. #6
    Registered User
    Join Date
    Sep 2009
    Posts
    3
    Quote Originally Posted by tabstop View Post
    That's probably because r is 12349812, as opposed to some number between 0 and 7.
    Um, could you explain? I can't see where r is messing up/not doing what I expect it to be doing.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Kiros_Xannon View Post
    Um, could you explain? I can't see where r is messing up/not doing what I expect it to be doing.
    I apologize; I looked for r to be initialized in the only place it made sense to initialize it and didn't see it further up. Your row check must check all the rows, not just the row you placed the last queen in. Furthermore you must check all the columns in the row. Further furthermore you must expect to find one queen; you need to be worried about finding two.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Queens problem
    By Dashing Boy in forum C++ Programming
    Replies: 14
    Last Post: 10-15-2007, 12:12 PM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM

Tags for this Thread


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