Bài 52 Leetcode: N-Queens II

Đề bài:

Bài toán n-queens là bài toán đặt n quân hậu lên một bàn cờ n x n sao cho không có hai quân hậu nào tấn công nhau.

Cho một số nguyên n, hãy trả về số lượng giải pháp riêng biệt cho bài toán n-queens.

Ví dụ 1:

Input: n = 4
Output: 2
Giải thích: Có hai giải pháp riêng biệt cho bài toán 4-queens như được hiển thị.

Ví dụ 2:

Input: n = 1
Output: 1

Ràng buộc:

• 1 <= n <= 9

Giải thích thuật toán bằng C ++

class Solution {
 public:
  int totalNQueens(int n) {
    int ans = 0;
    dfs(n, 0, vector<bool>(n), vector<bool>(2 * n - 1), vector<bool>(2 * n - 1),
        ans);
    return ans;
  }

 private:
  void dfs(int n, int i, vector<bool>&& cols, vector<bool>&& diag1,
           vector<bool>&& diag2, int& ans) {
    if (i == n) {
      ++ans;
      return;
    }

    for (int j = 0; j < n; ++j) {
      if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
        continue;
      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
      dfs(n, i + 1, move(cols), move(diag1), move(diag2), ans);
      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
    }
  }
};

Đây là một đoạn mã C++ để giải quyết bài toán N-queens (n quân hậu) bằng thuật toán đệ quy (DFS) để đếm số lượng giải pháp hợp lệ.

Hàm `totalNQueens` nhận đầu vào là số nguyên `n` và trả về số lượng giải pháp hợp lệ cho bài toán n-queens.

Trong hàm `totalNQueens`, biến `ans` được khởi tạo ban đầu bằng 0. Sau đó, hàm gọi hàm `dfs` để thực hiện quá trình đếm số lượng giải pháp.

Hàm `dfs` chứa các tham số `n`, `i`, `cols`, `diag1`, `diag2` và `ans`. `n` là kích thước của bàn cờ, `i` là chỉ số hàng hiện tại đang xét. `cols`, `diag1`, `diag2` là các vector để lưu trữ thông tin về vị trí đã được đặt quân hậu. `ans` là biến để lưu trữ số lượng giải pháp.

Nếu `i` bằng `n`, tức là đã đặt quân hậu vào tất cả các hàng, ta tăng giá trị của biến `ans` lên 1 và kết thúc hàm.

Ngược lại, ta duyệt qua tất cả các cột trong hàng `i`. Nếu có một cột nào đang bị chiếm hoặc các đường chéo chính và phụ đã có quân hậu, ta bỏ qua và tiếp tục duyệt cột tiếp theo.

Nếu vị trí đặt quân hậu hợp lệ, ta đánh dấu cột, đường chéo chính và phụ đã được chiếm. Sau đó, ta đệ quy gọi hàm `dfs` để xét hàng tiếp theo.

Sau khi hoàn thành đệ quy, ta phục hồi lại trạng thái ban đầu bằng cách bỏ đánh dấu các cột, đường chéo chính và phụ đã được chiếm.

Cuối cùng, hàm `totalNQueens` trả về giá trị của biến `ans`, đại diện cho số lượng giải pháp hợp lệ tìm được.

Giải thích thuật toán bằng Java

class Solution {
  public int totalNQueens(int n) {
    dfs(n, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
    return ans;
  }

  private int ans = 0;

  private void dfs(int n, int i, boolean[] cols, boolean[] diag1, boolean[] diag2) {
    if (i == n) {
      ++ans;
      return;
    }

    for (int j = 0; j < cols.length; ++j) {
      if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
        continue;
      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
      dfs(n, i + 1, cols, diag1, diag2);
      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
    }
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def totalNQueens(self, n: int) -> int:
    ans = 0
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    def dfs(i: int) -> None:
      nonlocal ans
      if i == n:
        ans += 1
        return

      for j in range(n):
        if cols[j] or diag1[i + j] or diag2[j - i + n - 1]:
          continue
        cols[j] = diag1[i + j] = diag2[j - i + n - 1] = True
        dfs(i + 1)
        cols[j] = diag1[i + j] = diag2[j - i + n - 1] = False

    dfs(0)
    return ans