2019-02-23 Nクイーンズアルゴリズム

C++はN皇后問題を実現する
プログラムの最初にsizeOfBoardを設定することで四角い碁盤の大きさを規定する
プログラムはvectorクラスを使用して、サイズが可変な2次元配列を作成しました.chessBoard.size()はsizeOfBoardです
実はこれは時計の秒のようで、分、時計回りのようで、秒針は1周して、分針は1格を歩いて、同じ理屈で、分針は1周して、時計回りは1格を歩いて、絶えずすべての可能性を遍歴して終わります

#include
#include

using namespace std;

int times = 0;

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

int main(void)
{
    int sizeOfBoard;
    cout << "enter the size of board ( 1 or >= 4 ) : " << endl;
    cin >> sizeOfBoard;
    if (sizeOfBoard == 1 || sizeOfBoard >= 4)
    {
        vector> eightQueen(sizeOfBoard, vector(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>& 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>& 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>& 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;
}