C++

Forum

 
Nqueens Problem!!!

Pages: 123
lethien204 (22)
This assignment is done. All of suggestions and explaination are given in the comment.

This is the main function!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
/*******************Programming Assignment 2***************/
/*****************YOU MUST NOT EDIT THIS FILE**************/
/**********place n Queens on a nxn chess board************/


#include <iostream>
#include <vector>
#include "nqueens.cpp"


using namespace std;

vector<vector<int> > nQueens(int);

void PrintSolutions(const vector<vector<int> >&, int);

int main() {
	
	int BoardSize;
	cout << "enter the board size ";
	cin >> BoardSize;
	
	vector<vector<int> > solutions = nQueens(BoardSize);

	PrintSolutions(solutions, BoardSize);

}

void PrintSolutions(const vector<vector<int> >& solutions, int BoardSize){
	cout << endl << "Total number of solutions for board size " << BoardSize << "X" << BoardSize << " are " << solutions.size() << endl << endl;
	for (unsigned int j = 0; j < solutions.size(); j++) {
		cout << j + 1;
		for (int i = 0; i < BoardSize; i++)
			cout << " (" << i + 1 << "," << solutions[j][i] + 1 << ")";
		cout << endl;
	}
	cout << endl << endl;
}




This is the CODE need to modify!!!! 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/*******************Programming Assignment 2******************/
/*****************YOU MUST EDIT THIS FILE*********************/
/********************Complete function nQueens****************/

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > nQueens(int BoardSize) {
	vector<vector<int> > solutions;

	// you MUST change this function. It is not doing anything now 

	return solutions;
}


}

Last edited on
Duthomhas (13206)
I'm always amazed at how often the N-Queens problem is assigned to a first programming class students.

(Sorry, I'm not at a PC I can use to look at your code right now. Later tonight I will be.)
lethien204 (22)
thanks for your replied. I will wait for u. :D
Duthomhas (13206)
I'm curious as to why my post was reported?
SesameBacon (6)
I have the exact same assignment...
And I'm happy to say that my code is very similar to yours @lethien204 but I too get an error when I try to run it.
@Duoas, if you can help us that would be wonderful! :)
lethien204 (22)
I'm sorry Duoas, I was an accident. I tended to click reply, but I dont know why I click REPORT. Sorry about that :D
lethien204 (22)
SesameBacon: do you have any ideas :D
SesameBacon (6)
@lethien204 I'm not sure. I've been stuck on this for about 4 days. :(
Duthomhas (13206)
Sorry, my family needed me. Give me a few and I'll figure out where you're indexing out of bounds.
SesameBacon (6)
Take your time! :)
lethien204 (22)
There is an update in my code. Check it out!!!!
Duthomhas (13206)
Flippin forum timeout! I wanna go to bed!

Here's a short version of my post.

You are not allocating space for your solution.

1
2
3
4
5
6
 
vector<vector<int> > nQueens(int BoardSize)
{
  vector<vector<int> > solutions;
  vector<int> v1D( BoardSize );  // <-- this is a solution
  int current_row=0;  // <-- you don't need this variable

A 'solution' is an array of N elements such that:

    v1D[ row ] = column, where (row, column) is the location of a queen

The code in SAFE() is fine.

The remaining code is mixing up between nQueens() and SOLVE().

Your code is using a brute-force solution. The trick is to consider how you move from one possible solution to the next.

You put a queen in the first place in the first row.
In the next row, you put a queen in the first possible place.
Etc.

1 0 0 0
0 0 1 0
0 0 0 0 hmm, couldn't find a position to put a queen. We need to go BACK a row and adjust the column of the last queen.

1 0 0 0
0 0 0 1
0 1 0 0 hey, it worked
0 0 0 0 oh no! it didn't work! back again:

1 0 0 0
0 0 0 1
0 0 0 0 still didn't work for this row. Back again

1 0 0 0
0 0 0 0 didn't work for this row either. back again

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0 hey, a solution!

Having found a solution, solutions.push_back() it.

Then KEEP GOING.

0 1 0 0
0 0 0 1
1 0 0 0
0 0 0 0 no solution. go back.

0 1 0 0
0 0 0 1
0 0 0 0 go back

...


You need to fix your code to do this properly. You really only need a single function (in addition to SAFE()) to do this.

Hope this helps.
SesameBacon (6)
Hmmmm, I still get an error while running your code, @lethien204.
lethien204 (22)
@@SesameBacon: my code still have a lot of mistakes:(
@@Douas: Thanks for your info, it's really helpful for me;however, I still get a problem. My code doesn't backtrack. That's will be great if u can help me again!!!!!. I already update a new code. Thankssssssssssssssssssssssssss
lethien204 (22)
Nobody can solve it :(((((((((
SesameBacon (6)
@lethien204 Hey dude, I've been getting some ideas from your code and am now getting the exact same error now. I did some Debugging and it seems that your v1D[current_row]=i is causing the error... Not sure if you know what's up with that.
Duthomhas (13206)
You have the same problem. You need to allocate N elements before you can index them.

1
2
3
4
 
vector<vector<int> > nQueens(int BoardSize)
{
  vector<vector<int> > solutions;
  vector<int> column_solutions( BoardSize );

When I run the code it produces: 

Total number of solutions for board size 4X4 are 1

1 (1,1) (2,1) (3,1) (4,1)

That's a list of (row,column), so what it is saying is that your solution is:

    +---+---+---+---+
    | Q |   |   |   |
    +---+---+---+---+
    | Q |   |   |   |
    +---+---+---+---+
    | Q |   |   |   |
    +---+---+---+---+
    | Q |   |   |   |
    +---+---+---+---+

Which is, obviously, not correct. (A 4x4 board has exactly two solutions, and they are a mirror image.


You need to think through the way the algorithm works. We'll start just by thinking of the first row. We already know that each row has exactly one queen in it. So, let's try a queen in every position in the first row and see if it works.

    Pass 1              Pass 2              Pass 3              Pass 4
    +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
    | Q |   |   |   |   |   | Q |   |   |   |   |   | Q |   |   |   |   |   | Q |
    +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+

So far, so good -- you can put a queen in every spot. Now, for each possible position of the queen there, you need to try the same thing with the rows below the first.

This is where we can generalize -- where the recurrence comes in. For the row below, we'll try to put a queen in every position, just like we did in the first. The only difference is that we'll automatically reject positions where there cannot be a queen.

Again, for each valid position for a queen in the second row, we'll try all the positions for the third row. And so on until we do all the rows.


So, what are the ending conditions?

If we find a valid position for a queen in the current row, try all the positions for the next row.

If there is no next row (we are on the last row), then we've found a complete solution. Append it to the list of solutions.

But what happens if we don't find a valid position in the current row?

We need to back up. Go back the the previous row and try the next solution.

Q--- Q--- Q--- Q--- Q--- Q--- Q--- Q---
Q--- -Q-- --Q- --Q- --Q- --Q- --Q- --Q-
---- ---- ---- Q--- -Q-- --Q- ---Q ----Q hmm, no valid solution.
---- ---- ---- ---- ---- ---- ---- ----

Q---
---Q  here, on the previous row, we'll try the next queen position. See?
----
----

(For here on out, I'll avoid drawing every possible position for the queens, and only draw the valid positions for the rows above the one we're commenting on.)

Q---
---Q
-Q--
----Q argh, all the way at the end (row 3), all out of positions

Q---
---Q
----Q out of positions on row 2
----

Q---
----Q out of positions on row 1[tt]
----
----

-Q--  next position on row 0
---Q  good on row 1
Q---  good on row 2
--Q-  good on row 3. Hey, row 3 is the last row! This is a valid solution!

Having found a valid solution, we solutions.push_back(v1D);.

But we're not done! Keep going!

-Q--
---Q
Q---
----Q  no good on row 3

-Q--
---Q
----Q  no good on row 2
----

-Q--
----Q  no good on row 1
----
----

--Q-
Q---
---Q
-Q--  hey, another good one on row 3 --> another valid solution. But, we're not done! Nope. Keep going.

--Q-
Q---
---Q
----Q  no good on row 3

--Q-
Q---
----Q  no good on row 2
----

--Q-
----Q  no good on row 1
----
----

---Q
<snip>

----Q  no good on row 0. Since we have exhausted all possibilities on row 0, we're done.
----
----
----

I've got to go. Hope this helps.

[edit] Edited a little for readability.
Last edited on
SesameBacon (6)
I'm not quite sure what you're telling me to change... Where does the problem lie in the code? I'm very confused. :/
lethien204 (22)
I just got home from work, totally tired now. Will get back to u guys tmr. Thanks Douas for helping me. @@SesameBacon: I will tell u if I figure the problem out. Good luck guys
lethien204 (22)
Douas: sorry for my bad, I don"t understand allocating my elements.
vector<vector<int> > nQueens(int BoardSize)
{
vector<vector<int> > solutions;

is there any thing wrong with this code. This code is actually fixed from my professor, so I have to continue writing a function below it. The BoardSize will be called from the main function, when I input BoardSize number. Also when I run the code above, I see it shows 2 solutions for
size 4 and 2 incorrect solutions. So is it any problem with my safe function???. Anyway, I will think about the algorithm and update my code tmr. Thankssssssssssss
Pages: 123