Showing more than one n-queen answer opportunity

Question

I have code to display the n-queens problem in the console based on the board size number entered by the user.

Here is the code:

#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" );
        const 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;
}

The console display is as follows. Say I introduce 4:

Then the result:

I want to know if I can add another feature to the application, because a 4x4 board can have 2 solutions. Some help would be appreciated - thanks!

ps: the code was not completely created by me, I completely forgot how I got the first code algorithm, I do not take responsibility for this code :)

Answer 1

, 1 . , .

NQueens q;
while(q.next()) // search next solution
{
    q.clearScreen(); // OR clrscr();
    q.displayBoard();
    char c = getch();
    if(c != ' ') break; // Interrupt loop when user press key, but not space
    // When user press space he will see next answer
}

Answer 2

#include <iostream>

using namespace std;

const int N = 5;
int position[N];

// Check if a position is safe
bool isSafe(int queen_number, int row_position)
{
        // Check each queen before this one
        for(int i=0; i<queen_number; i++)
        {
                // Get another queen row_position
                int other_row_pos = position[i];

                // Now check if they're in the same row or diagonals
                if(other_row_pos == row_position || // Same row
                        other_row_pos == row_position - (queen_number-i) || // Same diagonal
                        other_row_pos == row_position + (queen_number-i))   // Same diagonal
                        return false;
        }
        return true;
}


// Recursively generate a tuple like [0 0 0 0], then [0 0 0 1] then etc...
void solve(int k)
{
        if(k == N) // We placed N-1 queens (0 included), problem solved!
        {
                // Solution found!
                cout << "Solution: ";
                for(int i=0; i<N; i++)
                        cout << position[i] << " ";
                cout << endl;
        }
        else
        {
                for(int i=0; i<N; i++) // Generate ALL combinations
                {
                        // Before putting a queen (the k-th queen) into a row, test it for safeness
                        if(isSafe(k,i))
                        {
                                position[k] = i;
                                // Place another queen
                                solve(k+1);
                        }
                }
        }
}

int main()
{
        solve(0);

        return 0;
}

, :)

Answer 3

return true :

if( !cnt ) 
    return true;

(.. displayBoard), false. , , .

displayBoard solve, , system("CLS"), , .

Answer 4

if( !cnt ) 
return true;

(.. displayBoard), return false. , , .

You want to remove the call displayBoardin the solution, and you may need to adjust the places that you call in the system (" CLS") to get the overall result that you like.