C++实现N皇后问题

程序中一开始通过设置sizeOfBoard规定方形棋盘的大小

程序使用了vector类创建了一个大小可变的二维数组，chessBoard.size()就是sizeOfBoard

其实这就好像时钟的秒，分，时针一样，秒针转一圈，分针走一格，同理，分针走完一圈，时针走一格，不断的把所有可能都遍历完

#include<iostream>
#include<vector>

using namespace std;

int times = 0;

void put_Chess(int x, vector<vector<int>>& chessBoard);
bool check_Pos_Valid(int x, int y, vector<vector<int>>& chessBoard);
void print_Board(vector<vector<int>>& chessBoard);

int main(void)
{
    int sizeOfBoard;
    cout << "enter the size of board ( 1 or >= 4 ) : " << endl;
    cin >> sizeOfBoard;
    if (sizeOfBoard == 1 || sizeOfBoard >= 4)
    {
        vector<vector<int>> eightQueen(sizeOfBoard, vector<int>(sizeOfBoard));
        put_Chess(0, eightQueen);
        cout << "times = " << times << endl;
    }
    else
        cout << "only size of board is 1 or bigger than 4 has solution" << endl;
    return 0;
}

void put_Chess(int x, vector<vector<int>>& chessBoard)
{
    for (int col = 0; col < chessBoard.size(); col++)
    {
        if ((x >= 0 && x < chessBoard.size()) && check_Pos_Valid(x, col, chessBoard))
        {
            chessBoard[x][col] = 1;
            put_Chess(x + 1, chessBoard);
        }
        else if (x < 0 || x >= chessBoard.size())
        {
            times++;
            print_Board(chessBoard);
            break;
        }
    }
    if (x != 0)   //防止回溯到第一行最后一列结束时意外给内存中不属于数组的部分赋值
    {
        for (int i = x - 1; i < chessBoard.size(); i++)
        {
            for (int j = 0; j < chessBoard.size(); j++)
            {
                chessBoard[i][j] = 0;
            }
        }
    }
}

/*检查所选位置是否可放置皇后，是返回true，否返回false*/
bool check_Pos_Valid(int x, int y, vector<vector<int>>& chessBoard)
{
    /*检查所选位置的行是否已放置了皇后*/
    for (int i = 0; i < chessBoard.size(); i++)
    {
        if (chessBoard[x][i] == 1)
            return false;
    }
    /*检查所选位置的列是否已放置了皇后*/
    for (int j = 0; j < chessBoard.size(); j++)
    {
        if (chessBoard[j][y] == 1)
            return false;
    }
    /*检查所选位置的左上角是否已放置了皇后*/
    for (int i = 0, j = 0; i < chessBoard.size(); i++, j++)
    {
        if ((x - i >= 0) && (y - j >= 0) && chessBoard[x - i][y - j] == 1) 
            return false;
    }
    /*检查所选位置的右上角是否已放置了皇后*/
    for (int i = 0, j = 0; i < chessBoard.size(); i++, j++)
    {
        if ((x - i >= 0) && (y + j < chessBoard.size()) && chessBoard[x - i][y + j] == 1) 
            return false;
    }
    /*检查所选位置的左下角是否已放置了皇后*/
    for (int i = 0, j = 0; i < chessBoard.size(); i++, j++)
    {
        if ((x + i < chessBoard.size()) && (y - j >= 0) && chessBoard[x + i][y - j] == 1) 
            return false;
    }
    /*检查所选位置的右下角是否已放置了皇后*/
    for (int i = 0, j = 0; i < chessBoard.size(); i++, j++)
    {
        if ((x + i < chessBoard.size()) && (y + j < chessBoard.size()) && chessBoard[x + i][y + j] == 1) 
            return false;
    }
    return true;
}

void print_Board(vector<vector<int>>& chessBoard)
{
    cout << "------------------------" << endl;
    for (int i = 0; i < chessBoard.size(); i++)
    {
        for (int j = 0; j < chessBoard.size(); j++)
        {
            cout << chessBoard[i][j] << " ";
        }
        cout << endl;
    }
    cout << "------------------------" << endl;
}