N-Queens

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

--------------------------- thinking ----------------------------------
https://oj.leetcode.com/discuss/13100/accepted-auxillary-space-o-n-using-dfs-cpp
https://oj.leetcode.com/discuss/18411/accepted-java-solution
---------------------------- codes ------------------------------------
class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<int>> result;
        vector<int> marker(n, 0);
        puzzleHelper(result, marker, 0, n);
        return cvtResult(result);
    }
    void puzzleHelper(vector<vector<int>> &result, vector<int> &marker, int row, int n) {
        if (row == n) {
            result.push_back(marker);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(isSafe(marker, row, i)) {
                marker[row] = i;
                puzzleHelper(result, marker, row+1, n);
            }
        }
    }
    bool isSafe(vector<int> &marker, int row, int col) {
        for (int cur_row = row - 1, ldia = col - 1, rdia = col + 1; cur_row >= 0; cur_row--, ldia--, rdia++) {
            if (marker[cur_row] == col || marker[cur_row] == ldia || marker[cur_row] == rdia) {
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> cvtResult(vector<vector<int>> &inputs) {
        vector<vector<string>> result;
        for (int i = 0; i < inputs.size(); i++) {
            vector<string> out;
            for (int j = 0; j < inputs[0].size(); j++) {
                string ele;
                for (int index = 0; index < inputs[0].size(); index++) {
                    if (index == inputs[i][j]) {
                        ele += "Q";
                    } else {
                        ele += ".";
                    }
                }
                out.push_back(ele);
            }
            result.push_back(out);
        }
        return result;
    }
};
------------------------------ non recursive codes ---------------------------
class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<bool> row(n, true);
        vector<bool> lft_dia(2 * n, true);
        vector<bool> rit_dia(2 * n, true);
        stack<int> rst_stk;
        stack<int> stack;
        stack.push(0);
        vector<vector<int>> result;
        //BUG -> it's very important to have this marker, or the codes will become a dead loop
        vector<bool> visited(n, false);
        while (!stack.empty()) {
            if (stack.size() == (n+1)) {
                stack.pop();
                rst_stk = stack;
                vector<int> result_ind;
                while(!rst_stk.empty()) {
                    int cur_ind = rst_stk.top();
                    rst_stk.pop();
                    result_ind.push_back(cur_ind);
                }
                result.push_back(result_ind);
                int r = stack.top();
                resetLabel(row, lft_dia, rit_dia, r, n-1, n);
                stack.pop();
                visited[n-1] = false;
                stack.push(r+1);
            }
            int r = stack.top();
            int c = stack.size()-1;
            if (r == n) {
                stack.pop();
                if (stack.empty()) break;
                resetLabel(row, lft_dia, rit_dia, stack.top(), stack.size()-1, n);
            } else if (!checkLabel(row, lft_dia, rit_dia, r, c, n) || visited[c]) {
                stack.pop();
                visited[c] = false;
                stack.push(r+1);
            } else {
                setLabel(row, lft_dia, rit_dia, r, c, n);
                visited[c] = true;
                stack.push(0);
            }
        }
        return cvrtResult(result, n);
    }
    void setLabel(vector<bool> &row, vector<bool> &lft_dia, vector<bool>&rit_dia, int r, int c, int n) {
        row[r] = false;
        lft_dia[r+c] = false;
        rit_dia[n+r-c] = false;
    }
    void resetLabel(vector<bool> &row, vector<bool> &lft_dia, vector<bool>&rit_dia, int r, int c, int n) {
        row[r] = true;
        lft_dia[r+c] = true;
        rit_dia[n+r-c] = true;
    }  
    bool checkLabel(vector<bool> &row, vector<bool> &lft_dia, vector<bool>& rit_dia, int r, int c, int n) {
        if (row[r] && lft_dia[r+c] && rit_dia[n+r-c]) {
            return true;
        } else {
            return false;
        }
    }
    vector<vector<string>> cvrtResult(vector<vector<int>> result, int n) {
        vector<vector<string>> output;
        for (int i = 0; i < result.size(); i++) {
            vector<string> rslt;
            for (int j = 0; j < n; j++) {
                string ele(n, '.');
                ele[result[i][j]] = 'Q';
                rslt.push_back(ele);
            }
            output.push_back(rslt);
        }
        return output;
    }
};