N-Queens

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

http://www.lintcode.com/en/problem/n-queens/

Discussion

N-Queens N皇后问题，非常经典的DFS问题。
用一个一位数组来存放当前皇后的状态。假设数组为int state[n], state[i]表示第 i 行皇后所在的列。那么在新的一行 k 放置一个皇后后:

• 判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等；
• 判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1-row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置

Solution

Recursion

// Time:  O(n * n!)
// Space: O(n)
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<vector<string> > result;
        if(n==0) return result;
        vector<int> state(n, -1);//存的是各行queen放在哪一列
        dfs(0, state, result);
        return result;
    }
private:
    void dfs(int row, vector<int> &state, vector<vector<string> > &solutions) {
        int n = state.size();
        if(row == n) {//output result
            //vector<vector<string> > tmpSol(n, vector<string>(n, '.'));
            vector<string> tmpSol(n, string(n,'.'));
            for(int i=0; i<n; i++) {
                tmpSol[i][state[i]] = 'Q';
            }
            solutions.push_back(tmpSol);
        }
        for(int col=0; col<n; col++) {
            if(isSafe(state, row, col)) {
                state[row] = col;
                dfs(row+1, state, solutions);
                state[row] = -1;
            }
        }
    }
    bool isSafe(vector<int> state, int row, int col) {
        for(int i=0; i<row; i++) {
            if(state[i] == col || abs(row-i) == abs(col-state[i]))
                return false;
        }
        return true;
    }
};

Iteration的方法比较难。。。
还是用数组int state[n], state[i]表示第 i 行皇后所在的列，初始化为-1表示都还没有开始放， 从第row=0行开始放， 有四种情况需要考虑：

1. 已经放到row==n了，说明已经放了n个queen了，得到一个可行解了，这时候要输出可行解，并且，注意了!!! 还要继续扩展求解下一个solution，因为题目要求列出所有solution。扩展方法是回到上一行，将上一行的queen放到下一个位置 --- row--, state[row]++, 继续判断。
2. 还没有放到row==n，已经试到最后一列了(state[row]==n)，这时候说明在row这一行，所有列都试过了，那么就要重这一行的queen，回到上一行（row--），（这时候row是可能变成-1的），并且将上一行的queen位置加1再继续试。
3. 还没有到最后一列，那就检验这一列能不能放(或者还是-1还没开始放），不能放就继续试下一列（还是在这一行，上面两种情况都是要回到上一行的）。
4. 如果这一列能放，那就开始下一行。

这四种情况在一个大的循环里。长话短说就是当某个位置不能放就试下一个位置（下一列），反之若能放，就move到下一行，但是在试之前（不是move到下一行之前）要看一看是不是已经到达最后一行了（输出solution），还要看一看是不是已经放到最后一列了。这两种情况都是要回到上一行的。

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<vector<string> > result;
        if(n==0) return result;
        vector<int> state(n, -1);
        int row = 0;
        while (true) {
            if(row == n) {//达到最后一行了，输出结果
                vector<string> tmpSol(n, string(n,'.'));
                for(int i=0; i<n; i++) {
                    tmpSol[i][state[i]] = 'Q';
                }
                result.push_back(tmpSol);
                row--;//继续扩展
                state[row]++;
            } else if(state[row] == n) {//到达最后一列了，回到上一行，继续
                state[row] = -1;//要回上一行了，所以当前行queen要清除掉重新来过
                row--;
                if(row==-1) break;
                state[row]++;
            } else if(state[row] == -1 || isSafe(state, row, state[row]) == false) {
                state[row]++;//这一列失败了，继续试下一列
            } else {//一切正常，继续下一行
                 row++;
            }
        }
        return result;
    }
    bool isSafe(vector<int> &state, int row, int col) {
        for(int i=0; i<row; i++) {
            if(state[i] == col || row-i == abs(col-state[i])) {
                return false;
            }
        }
        return true;
    }
};

上面的itereation的方法确实比较难想出来，有没有更一般的办法呢？

把递归改成迭代，就需要用一些变量来记录函数执行时的状态。在八皇后问题中，函数的状态和行数是息息相关的，每次递归都是由一行进入下一行，那么用一个变量把把行数记录下来，迭代的时候，以这个变量为序进行操作就可以了。具体如下：

1. 在每一行开始的时候，state[row]++，意思是说从下一列（记为第COL列）开始试（初始化时是-1嘛，所以第一次的时候刚好是从第0列开始试。
2. 从第COL列开始，找到一个新的能放皇后的列，记为newCol。
3. 如果没找到，意味着本行结束，回溯到上一行
4. 如果找到了
   4.1 如果是最后一行了，那么输出结果，回到上一行
   4.2 要是还没到最后一行，继续下一行，同时状态置-1

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<vector<string> > result;
        if(n<=0) return result;
        vector<int> state (n, -1);
        int row = 0;
        while(row>=0) {
            bool iFound = false;
            state[row] ++;
            for(int col=state[row]; col<n; col++) {
                if(isSafe(state, row, col)) {
                    state[row] = col;
                    iFound = true;
                    break;
                }
            }
            if(iFound) {
                if(row == n-1) {
                    outputsolution(result, state);
                    row--;
                    //state[row]++;
                } else {
                    row++;
                    state[row] = -1;
                }
            } else {
                row--;
            }
        }
        return result;
    }
    void outputsolution(vector<vector<string> > &solutions, vector<int> state) {
        int n = state.size();
        vector<string> sol(n, string(n, '.'));
        for(int i=0; i<n; i++) {
            sol[i][state[i]] = 'Q';
        }
        solutions.push_back(sol);
    }
    bool isSafe(vector<int> state, int row, int col) {
        int n = state.size();
        for(int i=0; i<row; i++) {
            if(state[i] == col || row-i == abs(col-state[i])) {
                return false;
            }
        }
        return true;
    }
};