N-Queens

n x n 체스판에 서로 공격하지 못 하는 n개의 퀸을 놓는 문제

class Solution {
public:
    vector<vector<string>> _result{};
    int N{0};
    
    bool promising(int row, vector<int> &cols)
    {
        for (int i = 0; i < row; i++)
        {
            if (cols[i] == cols[row])
            {
                return false;
            }
            else if (row - i == abs(cols[row] - cols[i]))
            {
                return false;
            }
        }
        
        return true;
    }
    
    void PlaceQueen(int row, vector<string> &board, vector<int> &cols)
    {
        if (promising(row, cols) == false)
        {
            return;
        }
        else if (row == N - 1)
        {
            _result.push_back(board);
            return;
        }
        
        for (int i = 0; i < N; i++)
        {
            cols[row + 1] = i;
            
            board[row + 1][i] = 'Q';
            PlaceQueen(row + 1, board, cols);
            board[row + 1][i] = '.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        
        vector<string> board(n, string(n, '.'));
        vector<int> cols(n, -1);
        
        N = n;
        
        for (int i = 0; i < N; i++)
        {
            cols[0] = i;
            
            board[0][i] = 'Q';
            PlaceQueen(0, board, cols);
            board[0][i] = '.';
        }
        
        return _result;
    }
};