C++

Forum

 
Nqueens Problem!!!

Pages: 123
anup30 (968)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
// n queen // code from rosettacode.org
#include <windows.h>
#include <iostream>
#include <string>
 
//--------------------------------------------------------------------------------------------------
using namespace std;
 
//--------------------------------------------------------------------------------------------------
class point
{
public:
    int x, y;
    point(){ x = y = 0; }
    void set( int a, int b ){ x = a; y = b; }
};
//--------------------------------------------------------------------------------------------------
class nQueens
{
public:
    void solve( int c )
    {
        _count = c; int len = ( c + 1 ) * ( c + 1 ); _queens = new bool[len]; memset( _queens, 0, len );
	_cl = new bool[c]; memset( _cl, 0, c ); _ln = new bool[c]; memset( _ln, 0, c );
	point pt; pt.set( rand() % c, rand() % c ); putQueens( pt, c ); displayBoard();
	delete [] _queens; delete [] _ln; delete [] _cl;
    }
 
private:
    void displayBoard()
    {
	system( "cls" ); string t = "+---+", q = "| Q |", s = "|   |";
	COORD c = { 0, 0 }; HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
	for( int y = 0, cy = 0; y < _count; y++ )
	{
	    int yy = y * _count;
	    for( int x = 0; x < _count; x++ )
	    {
		SetConsoleCursorPosition( h, c ); cout << t;
		c.Y++; SetConsoleCursorPosition( h, c );
		if( _queens[x + yy] ) cout << q; else cout << s;
		c.Y++; SetConsoleCursorPosition( h, c );
		cout << t; c.Y = cy; c.X += 4;
	    }
	    cy += 2; c.X = 0; c.Y = cy;
        }
    }
 
    bool checkD( int x, int y, int a, int b )
    {
	if( x < 0 || y < 0 || x >= _count || y >= _count ) return true;
	if( _queens[x + y * _count] ) return false;
	if( checkD( x + a, y + b, a, b ) ) return true;
	return false;
    }
 
    bool check( int x, int y )
    {
	if( _ln[y] || _cl[x] )        return false;
	if( !checkD( x, y, -1, -1 ) ) return false;
	if( !checkD( x, y,  1, -1 ) ) return false;
	if( !checkD( x, y, -1,  1 ) ) return false;
	if( !checkD( x, y,  1,  1 ) ) return false;
	return true;
    }
 
    bool putQueens( point pt, int cnt )
    {
	int it = _count;
	while( it )
	{
	    if( !cnt ) return true;
	    if( check( pt.x, pt.y ) )
	    {
		_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = true;
		point tmp = pt; if( ++tmp.x >= _count ) tmp.x = 0; if( ++tmp.y >= _count ) tmp.y = 0;
		if( putQueens( tmp, cnt - 1 ) ) return true;
		_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = false;
	    }
	    if( ++pt.x >= _count ) pt.x = 0;
	    it--;
	}
	return false;
    }
 
    int          _count;
    bool*        _queens, *_ln, *_cl;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
    nQueens n; int nq;
    while( true )
    {
	system( "cls" ); cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> nq;
	if( nq < 4 ) return 0; n.solve( nq ); cout << endl << endl;
	system( "pause" );
    }
    return  0;
}
//--------------------------------------------------------------------------------------------------


EDIT:
for background theory:
http://www.igorsevo.com/Article.aspx?article=Recursion%20tutorial,%20N-queens%20problem

this may also help:
http://www.ccodechamp.com/c-program-of-n-queens-problem-solution-using-backtracking/
Last edited on
Duthomhas (13206)
@anup30
Points to remember.

 • OP is a first time beginner.
 • He is modifying a program template his professor gave him.
 • That crap from rosetta code deliberate obfuscates the (junk) code (I was considering replacing it myself).
 • Suppose you are OP's professor, and your student turns something like that in. Instant F, right?
    (And potential for expulsion.)
 • 1st link: overload with concepts he doesn't understand yet.
 • 2nd link: more code that doesn't work like OP's assignment.

@lethien
I'm really trying to distill this problem down to as simple as possible, but I know it isn't a particularly easy problem to get your head around. The fact is that N-Queens is notoriously difficult to do well. We're working with a simple brute-force method here, which is enough to get you through the assignment but not overload you with stuff you haven't learned in a first term class.

sorry for my bad, I don"t understand allocating my elements.

Don't feel sorry. It is always good to say "I don't understand" about something. Some people look at me stupid when I say that, but more often than not, when I ask the question there were many others also thinking the question.

If you want to use an array of values, they must exist before you use them. A std::vector allows you to create an array of values of any size you want, but by default it does nothing -- there are no values.

You must first tell it how many values to create before you can use them.

1
2
 
vector <int> xs;  // a vector of values -- with no values
xs[ 2 ] = 7;  // Program fails and/or crashes -- cannot access memory that doesn't exist/belong to you

Let's fix the problem:
1
2
3
 
vector <int> xs( 12 );  // a vector of 12 distinct values -- the vector constructor creates them for you
xs[ 2 ] = 7;  // Works, because the third element of five elements exists
xs[ 5 ] = 9;  // Failure and/or crash, because the sixth element does not exist.

What this means for your code is that you have a vector of zero elements (v1D) but treat it as if it had BoardSize elements.

The technical time of the crash is not in your code -- it is in your professor's. The solutions vector is expected to be zero or more solutions (vectors of BoardSize elements), but your code is returning a vector that contains solutions with zero elements. When your professor's code tries to access an element of the first solution -- which isn't there -- it causes the program to crash.


A solution
A solution represents queens on a board. There are BoardSize rows on the board, so there must also be BoardSize queens on the board, and hence, BoardSize elements in a solution.

Each element is a lookup. For element 0 (row 0) the queen will be at the value's column. So, for a 4x4 board, a valid solution is a vector of the following values:

    { 1, 3, 0, 2 }

That is:
  at row 0, the queen is in column 1
  at row 1, the queen is in column 3
  at row 2, the queen is in column 0
  at row 3, the queen is in column 2

Get it?

You'll notice that when your professor prints the solution, he adds one to all those values, so you see a solution as
    (1,2) (2,4) (3,1) (4,3)
instead of
    (0,1) (1,3) (2,0) (3,2)


Is safe to place piece at (row,column)?
I'm not sure why you went and changed your SAFE() function when before I indicated to you that it worked correctly. Because now it does not. Here's what you had before (IIRC):

1
2
3
4
5
6
7
8
9
10
11
12
 
bool SAFE(vector<int> CHECK, int row, int column)
{
  for (int i = 0; i < row; i++)
  {
    if (CHECK[i] == column)
      return false;

    if (abs(v1D[i]-column) == abs(i-row))
      return false;
  }
  return true;
}

Try to follow through the code to see what it does for each of the (row,column) values in the solution. What does the above code return for (0,1)? For (1,3)? Etc.


An aside on names
Part of your confusion is evident in the names of things in the code. For example, a 'solution' has had the following different names in your code:

    v1D   CHECK   column_solutions

Of these, my favorite is the last, but why not just call it a 'solution'? Once you chose a name, try to use the same name for the same thing everywhere in your code. For example:

1
2
 
bool SAFE(vector<int> column_solutions, int row, int column)
{

Choosing a good name for a thing helps you not be confused about your code.


Finding a solution
You need to concentrate on how to place queens on the board.

You need to see what you are doing in action, I think. Here is a small program to help. I assume you are on Windows. (If you are not, let me know.)

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
 
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <thread>
#include <string>
using namespace std;

#ifdef _WIN32
  #ifndef NOMINMAX
  #define NOMINMAX
  #endif
  #include <windows.h>
  void goto_xy( int x, int y )
  {
    static HANDLE hStdOut = GetStdHandle( STD_OUTPUT_HANDLE );
    COORD coords = { (SHORT)x, (SHORT)y };
    SetConsoleCursorPosition( hStdOut, coords );
  }
#else
  #error Complain to Duoas that you are using unix.
#endif

void print( int x ) { for (int n = 0; n < 4; n++) { goto_xy( 0, 3-n );
cout << string( x % 4, '-' ) << "Q" << string( 4 - x % 4 - 1, '-' ) << 
string( 7, ' ' ) << "\n"; x >>= 2; } goto_xy( 0, 4 ); cout << string( 10, 
' ' ) << "\n"; } int main() { 

system("cls");  // don't do this, btw.

for (int x = 0; x < 0x100; x++) { print( x ); if ((x == 114) || (x == 141))
{ cout << "A solution!" << flush; this_thread::sleep_for( chrono::seconds( 1 ) 
); cout << "\r" << string( 11, ' ' ) << flush; } else  this_thread::sleep_for( 
chrono::milliseconds( 250 ) ); } cout << "all done. found two solutions.\n"; }

THIS ONLY SHOWS YOU HOW THINGS WORK. It does NOT solve the N-Queens problem, not even for a 4x4 board. Don't try to figure it out. It won't help you in your assignment.

Just watch the animation to see how your code should work through the possible solutions.

Then you can start thinking about how to use a 'solution' vector to help you do it.

Hope this helps.
lethien204 (22)
Thanks for all ur helps guys. @@Douas: I'm working with ur information now, the last day for this assignment. Will get back to u soon.
anup30 (968)
• He is modifying a program template his professor gave him.


my professor give us a nQueens problem. I already did my code


i don't get, OP was correcting his professors code.

it drew my attention because i am a fide rated chess player, i myself didn't have enough time to code it myself, or to test the rosettacode (i just saw the output in compiler). i also provided other two link - actually to get idea not to copy-paste the assignment.

however, i appreciate your your way of helping understand OPs own code. (lighten)
lethien204 (22)
@@anup30: it's an assignment from my professor. He gives us a main() function which is showed above. Then he create a function name
vector<vector<int>> nQueens(int BoardSize){
vector<vector<int>> solutions;

I NEED TO WRITE THE CODE TO RUN THE MAIN FUNCTION HERE!


return solutions;
}
So that's all I wanna say. Thanks @@anup30 for giving me some ideas to solve my problem.
@@Douas: I already fixed the crash problem, so the only thing I need to do right now is placing the queens correctly. The code is updated step by step, so if you still have time, that's will be great for me to have ur helps. Thanks :D
holygift (6)
So you are some guy from my COEN243 class? Hurry, the assignment is due tomorrow.
lethien204 (22)
@@holygift: as u can see, my code is stuck right now >"<
Duthomhas (13206)
I hope you figured it out.

In case you were wondering, I've updated RosettaCode with a good solution.
Without the rotating/flipping transformations, the code is shorter (and something like what your homework should do):

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
  // MEMBER VALUES -----------------------------------------------------------

  const int                   N;
  std::vector <solution_type> solutions;

  // SOLVER ------------------------------------------------------------------

   queens( int N = 8 ):
     N( (N < 0) ? 0 : N )
   {
     // Row by row we create a potentially valid solution.
     // If a queen can be placed in a valid spot by the time
     // we get to the last row, then we've found a solution.

     solution_type solution( N );
     index_type row = 0;
     while (true)
     {
       // Advance the queen along the row
       ++solution[ row ];

       // (If we pass the end of the first row, we're done.)
       if ((row == 0) and (solution[ 0 ] >= N) break;

       if (solution[ row ] < N)
       {
         // If the queen is in a good spot...
         if (ok( solution, row, solution[ row ] ))
         {
           // ...and we're on the last row
           if (row == N-1)
           {
             // Add the solution we found
             solutions.push_back( solution );
           }
           // otherwise begin marching a queen along the next row
           else solution[ ++row ] = -1;
         }

       // When we get to the end of a row's columns then
       // we need to backup a row and continue from there.
       }
       else --row;
     }
   }

Notice the changes on lines 82, 101, and 112+ from the RosettaCode version.

Sorry I couldn't help you further before your homework was due.
(I still think your Professor's a jerk for giving you this problem as a first assignment.)
lethien204 (22)
I already got the solution, but the only one thing is that when I push back the whole solutions in the nQueens function, it just show me only 1 solution. :(
Duthomhas (13206)
Your professor's code prints all the solutions you put in the vector.

Are you sure your nqueens() function is not terminating after finding just one solution?
lethien204 (22)
for example i input size 5, after finish my SOLVE function, it give me a list of solutions which is correct, then in my nQueens function, I use solutions.push_back(vector_solution_from SOLVE). It just only show 1 solution :(. I will update the code and u can check it:)
lethien204 (22)
the code is updated :D
lethien204 (22)
:)))))))))))))))))))))))> I dont know how to express my feeling now. AAAAAAAAAAAAAAAAAAAAAAAAA. I got it :D:DD:D:D:D:D:. Thank you so much Duous for helping me a lot a lot alot . Thanks thanks thanks ..........:D
Duthomhas (13206)
[removed -- see reasoning below]
Last edited on
lethien204 (22)
yes, I did exactly the same as ur code. :D. So happy right now. Finally, I did solve nqueens problem A A A AA A A A A .
Duthomhas (13206)
Its a wonderful feeling, isn't it?

Remember, exposure to computers produces endorphins that enslave us. Enjoy the high, but don't let it take over. :OJ
lethien204 (22)
Thanks a lot Duoas. Really really happy right now. Thanks for everything. Best of lucks for you!!!!
lethien204 (22)
Can you do me a favor? Could you please modify the comment just about 30minutes ago ( this comment show all of my code), so the other people can do it by themselve. I want them to work hard and get the same feeling as I have.
Duthomhas (13206)
I would normally disagree, but in this (exceedingly rare) case I'll do that (as there is no other code that links to commentary on your solution, and other solutions can be found online).
lethien204 (22)
ok. that's good, I just hope people try their hard to get this problem. Anyway, thanks a gain Duoas :D
Pages: 123