52. N-Queens II.md

52. N-Queens II

Question:

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 the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

Thinking:

1. Question9_9: 八皇后

class Solution {
    public int totalNQueens(int n) {
        if(n == 0) return 0;
        return backtrace(0, n, new boolean[n][n], new boolean[n]);
    }
    private static int backtrace(int level ,int n, boolean[][] chess, boolean[] used){
        if(level == n) return 1;
        else{
            int count = 0;
            for(int i = 0; i < n; i++){
                if(used[i]) continue;
                if(isValid(chess, level, i, n)){
                    used[i] = true;
                    chess[level][i] = true;
                    count += backtrace(level + 1, n, chess, used);
                    used[i] = false;
                    chess[level][i] = false;
                }
            }
            return count;
        }
    }
    private static boolean isValid(boolean[][] chess, int row, int col, int n){
        if(row > 0){
            for(int i = 0; i < row; i++)
                if(chess[i][col]) return false;
            int tempRow = row;
            int tempCol = col;
            while(--tempRow >= 0 && --tempCol >= 0)
                if(chess[tempRow][tempCol]) return false;
            tempRow = row;
            tempCol = col;
            while(--tempRow >= 0 && ++tempCol <= n - 1)
                if(chess[tempRow][tempCol]) return false;
        }
        return true;
    }
}

二刷

在会输的过程中经常希望有一个全局的值用来保存。所以可以通过设置对象的属性，因为属性对于类的内部是可见的。

class Solution {
    private int res = 0;
    public int totalNQueens(int n) {
        if(n == 0) return 0;
        char[][] map = new char[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                map[i][j] = '.';
        }
        backtrace(map, 0, n);
        return this.res;
    }
    private void backtrace(char[][] map, int row, int n){
        if(row == n) res ++;
        else{
            for(int i = 0; i < n; i++){
                if(check(map, row, i)){
                    map[row][i] = 'Q';
                    backtrace(map, row + 1, n);
                    map[row][i] = '.';
                }
            }
        }
    }
    private boolean check(char[][] map, int row, int col){
        for(int i = 0; i < row; i++) if(map[i][col] == 'Q') return false;
        for(int i = 0; i < col; i++) if(map[row][i] == 'Q') return false;
        int i = row, j = col;
        while(--i >= 0 && --j >= 0) if(map[i][j] == 'Q') return false;
        while(--row >= 0 && ++col < map.length) if(map[row][col] == 'Q') return false;
        return true;
    }
}

Third time

• Method 1: search + dfs
  • the global variable is not required, we alse can implement that using return int.

  class Solution {
      public int totalNQueens(int n) {
          char[][] table = new char[n][n];
          for(int i = 0; i < n; i++)
              for(int j = 0; j < n; j++)
                  table[i][j] = '.';
          return dfs(table, 0, n);
      }
      private int dfs(char[][] table, int row, int n){
          if(row == n){return 1;}
          else{
              int res = 0;
              for(int i = 0; i < n; i++){
                  if(check(table, row, i, n)){
                      table[row][i] = 'Q';
                      res += dfs(table, row + 1, n);
                      table[row][i] = '.';
                  }
              }
              return res;
          }
      }
      private boolean check(char[][] table, int row, int col, int n){
          for(int i = 0; i < n; i++){
              if(table[row][i] == 'Q') return false;
              if(table[i][col] == 'Q') return false;
          }
          int r = row, c = col;
          while(row >= 0 && col >= 0)
              if(table[row--][col--] == 'Q') return false;
          while(r >= 0 && c < n)
              if(table[r--][c++] == 'Q') return false;
          return true;
      }
  }

C++ Version

• Method 1: backtrace

   class Solution {
   private:
   	int res_;
   	bool check(vector<string>& board, int row, int col, int n){
   		for(int i = 0; i < n; ++i){
   			if(board[row][i] == 'Q') return false;
   			if(board[i][col] == 'Q') return false;
   		}
   		int tx = row, ty = col;
   		while(tx >= 0 && ty >= 0) if(board[tx--][ty--] == 'Q') return false;
   		while(row >= 0 && col < n) if(board[row--][col++] == 'Q') return false;
   		return true;
   	}
   	void dfs(vector<string>& board, int row, int n){
   		if(row == n) res_++;
   		else{
   			for(int i = 0; i < n; ++i){
   				if(check(board, row, i, n)){
   					board[row][i] = 'Q';
   					dfs(board, row + 1, n);
   					board[row][i] = '.';
   				}
   			}
   		}
   	}
   public:
   	int totalNQueens(int n) {
   		res_ = 0;
   		string line = "";
   		for(int i = 0; i < n; ++i) line += ".";
   		vector<string> temp(n, line);
   		dfs(temp, 0, n);
   		return res_;
   	}
   };