N-Queens

<-H 51> N-Queens

// Method 1
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        this->columns = vector<int> (n, 0);
        this->main_diag = vector<int> (2 * n, 0);
        this->anti_diag  = vector<int> (2 * n, 0);


        vector<vector<string>> result;
        vector<int> count(n, 0);
        dfs(count, result, 0);
        return result;
    }

private:
    vector<int> columns;
    vector<int> main_diag;
    vector<int> anti_diag;

    void dfs(vector<int> &count, vector<vector<string>> &result, int row) {
        const int num = count.size();
        if(row == num) {
            vector<string> solution;
            for(int i = 0; i < num; i++) {
                string s(num, '.');
                for(int j = 0; j < num; j++)
                    if(j == count[i])
                        s[j] = 'Q';
                solution.push_back(s);
            }
            result.push_back(solution);
            return;
        }

        for(int j = 0; j < num; j++) {
            bool ok = columns[j] == 0 && main_diag[row + j] == 0 &&
                anti_diag[row - j + num] == 0;

            if(!ok)
                continue;
            count[row] = j;
            columns[j] = main_diag[row + j] = anti_diag[row - j + num] = 1;
            dfs(count, result, row + 1);

            count[row] = 0;
            columns[j] = main_diag[row + j] = anti_diag[row - j + num] = 0;
        }
    }
};

// Method 2
class Solution {
private:

void fun(vector<vector<string>> &ans, vector<string> &board, vector<int> &leftrow,
         vector<int> &upper, vector<int> &lower, int col) {
        if(col == board.size()) {
            ans.push_back(board);
            return;
        }
        for(int i = 0; i < board.size(); i++) {
            if(leftrow[i] == 0 && upper[board.size() - 1 + col - i] == 0 &&
               lower[i + col] == 0) {
                board[i][col] = 'Q';
                leftrow[i] = 1;
                upper[board.size() - 1 + col - i] = 1;
                lower[i + col] = 1;
                fun(ans, board, leftrow, upper, lower, col + 1);
                board[i][col] = '.';
                leftrow[i] = 0;
                upper[board.size() - 1 + col - i] = 0;
                lower[i + col] = 0;
            }
        }
    }
public:
	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>> ans;
        vector<string> board;
        string x(n, '.');
        for(int i = 0; i < n; i++)
            board.push_back(x);
        vector<int> leftrow(n, 0);
        vector<int> upper(2 * n - 1, 0);
        vector<int> lower(2 * n - 1, 0);
        fun(ans, board, leftrow, upper, lower,0);
        return ans;
	}
};