Eight Queens Problem...Tried Everything.

Kiros_Xannon · 09-26-2009, 09:25 PM

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.

tabstop · 09-26-2009, 09:28 PM

Code:

if(counter = 0)

This is why we have compiler warnings.

Kiros_Xannon · 09-27-2009, 11:24 AM

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.

IceDane · 09-27-2009, 11:51 AM

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.

tabstop · 09-27-2009, 01:17 PM

Quote:

Originally Posted by Kiros_Xannon

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.

Kiros_Xannon · 09-27-2009, 02:29 PM

Quote:

Originally Posted by tabstop

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.

tabstop · 09-27-2009, 02:46 PM

Quote:

Originally Posted by Kiros_Xannon

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.

09-26-2009, 09:25 PM	#1
Kiros_Xannon 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
Kiros_Xannon is offline

09-26-2009, 09:28 PM	#2
tabstop and the Hat of Guessing Join Date: Nov 2007 Posts: 8,740	Code: if(counter = 0) This is why we have compiler warnings.
tabstop is offline

09-27-2009, 11:24 AM	#3
Kiros_Xannon 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.
Kiros_Xannon is offline

09-27-2009, 11:51 AM	#4
IceDane Ex scientia vera Join Date: Sep 2007 Posts: 426	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."
IceDane is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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