Thread: 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.

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.