N-Queens II (H)

題目

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.."]
]

題意

在 n * n 的棋盤上放置n個皇后，使得每一行、每一列、每一條對角線有且只有一個皇后，統計所有有效的放置方法的個數，

思路

與 51. N-Queens 方法相同，但不需要記錄每一種解法，只要求統計個數，

因為不需要記錄組合，可以只需要三個陣列來對當前位置進行判斷：當前列是否被占用，當前左對角線(主對角線方向)是否被占用，當前右對角線(副對角線方向)是否被占用，通過畫圖尋找規律可得：共有(2n-1)條左對角線，且row-col+n-1相同(加上n-1是為了讓值能從0開始)的坐標位于同一左對角線；共有(2n-1)條右對角線，且row+col相同的坐標位于同一右對角線，

代碼實作

Java

記錄組合

class Solution {
    int count = 0;
    
    public int totalNQueens(int n) {
        generate(0, new int[n], new boolean[n]);
        return count;
    }

    private void generate(int row, int[] queen, boolean[] occupied) {
        if (row == occupied.length) {
            count++;
            return;
        }

        for (int col = 0; col < occupied.length; col++) {
            if (!occupied[col]) {
                boolean isValid = true;
                for (int preRow = 0; preRow < row; preRow++) {
                    if (Math.abs(row - preRow) == Math.abs(queen[preRow] - col)) {
                        isValid = false;
                        break;
                    }
                }

                if (isValid) {
                    queen[row] = col;
                    occupied[col] = true;
                    generate(row + 1, queen, occupied);
                    occupied[col] = false;
                }
            }
        }
    }
}

不記錄組合

class Solution {
    int count = 0;

    public int totalNQueens(int n) {
        generate(0, new boolean[2 * n - 1], new boolean[2 * n - 1], new boolean[n], n);
        return count;
    }

    private void generate(int row, boolean[] diaLeft, boolean[] diaRight, boolean[] colValid, int n) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int dl = row - col + n - 1;
            int dr = row + col;
            if (!colValid[col] && !diaLeft[dl] && !diaRight[dr]) {
                colValid[col] = diaLeft[dl] = diaRight[dr] = true;
                generate(row + 1, diaLeft, diaRight, colValid, n);
                colValid[col] = diaLeft[dl] = diaRight[dr] = false;
            }
        }
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
  let board = new Array(n).fill(0).map((value, index) => index)
  return dfs(board, 0)
}

let dfs = function (board, index) {
  if (index === board.length) {
    return 1
  }

  let count = 0
  for (let i = index; i < board.length; i++) {
    let isValid = true
    for (let j = 0; j < index; j++) {
      if (index - j === Math.abs(board[j] - board[i])) {
        isValid = false
        break
      }
    }
    if (isValid) {
      [board[index], board[i]] = [board[i], board[index]]
      count += dfs(board, index + 1);
      [board[index], board[i]] = [board[i], board[index]]
    }
  }

  return count
}

標籤：其他

上一篇：0051. N-Queens (H)

下一篇：一文徹底掌握二叉查找樹（多組動圖）(史上最全總結）