leetcode| 51. N皇后問題

給定一個整數 n，回傳 n 皇后不同的解，

示例:
輸入: 4
解釋: 4 皇后問題存在如下兩個不同的解法，
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

n皇后問題有兩種解的要求，一種僅要求輸出解決方案個數，一種要求輸出所有的具體解決方案，

思路

暴力破解不可行，時間復雜度為O(n^n)，
回溯法，其中在進行深搜時，剪枝的關鍵在于：

• 對于任意一點(x,y)，其所在的主對角線(\)和副對角線(/)上的坐標點，分別滿足一定關系，
• n*n的矩陣，\型對角線和/型對角線分別有2n-1條，
• 任意一條\型對角線上的坐標點滿足 row-col=常量a ,且a的范圍為-(n-1)到n-1，
• 任意一條/型對角線上的坐標點滿足 row+col=常量b ,且b的范圍為0到2n-2，
• 如4*4矩陣
  
• 使用一維陣列x,y,z可以分別標記\、/和縱方向是否已有棋子（按行放置棋子，無需再考慮橫向），

每一行放置時，相比于上一行能放置棋子的空位就會少1，時間復雜度O(n!)，空間復雜度O(n)，

僅求解決方案個數代碼

class Solution {
    public int dfs_backtrace(int row, int count, int n, int[] z, int[] x, int[] y) {
        //每一層遞回攜帶了row引數，所以每個dfs_backtrace函式代表row行在嘗試放置棋子
        //因此只需一層for回圈遍歷row行的每一列
        for(int col = 0; col < n; col++){
            //如果各個方向都沒有標記，說明此處可以放置棋子
            if(z[col] + x[n + row - col] + y[row + col] == 0) {
                //標記
                z[col] = 1;
                x[n + row - col] = 1;
                y[row + col] = 1;
                //dfs
                if(row + 1 == n) {
                    count++;
                } else {
                    count = dfs_backtrace(row+1, count, n, z, x, y);
                }
                //回溯
                z[col] = 0;
                x[n + row -col] = 0;
                y[row + col] = 0;
            }
        }
        return count;
    }

	public int totalNQueens(int n) {
        int[] z = new int[n];    // z[i]表示第i列是否有棋子
        int[] x = new int[2*n];  // x[n + row - col]表示(row,col)點所在主對角線(\)是否有棋子
        int[] y = new int[2*n];  // y[row + col]表示(row,col)點所在副對角線(/)是否有棋子
		return dfs_backtrace(0, 0, n, z, x, y);
	}
}

求出所有解決方案的代碼

僅需要添加一個queue[n]陣列，queue[i] = j, 表示為第i行的皇后放置在第j列；
將queue在放棋子與撤銷棋子時同步更新即可，引入queue陣列是為了記錄皇后位置，用于輸出解決方案，
以下代碼與上個代碼思路完全一致，僅將一些程序寫成了函式，

class Solution {
    int n;
    int[] x;
    int[] y;
    int[] z;
    int[] queue;

    List<List<String>> output = new ArrayList<List<String>>();

    private boolean is_not_attack(int row, int col) {
        return x[n+row-col]+y[row+col]+z[col] == 0;
    }

    private void placeQueue(int row, int col) {
        x[n + row - col] = 1;
        y[row + col] = 1;
        z[col] = 1;
        queue[row] = col;
    }

    private void removeQueue(int row, int col) {
        x[n + row - col] = 0;
        y[row + col] = 0;
        z[col] = 0;
        queue[row] = 0;
    }

    private void addOutput() {
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < n; i++) {
            char[] str = new char[n];
            Arrays.fill(str, '.');
            str[queue[i]] = 'Q';
            list.add(new String(str));
        }
        output.add(list);
    }

    private void traceback(int row) {
        for(int col = 0; col < n; col++) {
            if(is_not_attack(row, col)) {
                //放置棋子
                placeQueue(row, col);
                //DFS
                if(row + 1 == n) {
                    addOutput();
                } else {
                    traceback(row + 1);
                }
                //回溯棋子
                removeQueue(row, col);
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        x = new int[2*n];
        y = new int[2*n];
        z = new int[n];
        queue = new int[n];
        traceback(0);
        return output;
    }
}

筆記

方陣主副對角線行列值的特殊關系，