c++ - 显示 n 皇后问题的多个可能答案

Question

我有一些代码可以根据用户输入的棋盘尺寸数字在控制台中显示 n 皇后区问题。

代码如下:

#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;
}

控制台显示是这样的。假设我输入 4:

然后结果:

我想知道我是否可以在应用程序中添加另一种可能性，因为 4x4 板可以有 2 种解决方案。一些帮助将不胜感激 - 谢谢!

ps: 代码不是我完全创造的，我完全忘记了我是如何得到第一个代码算法的，我不相信这段代码:)

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
}