Bài 51 Leetcode: N-Queens

Đề bài:

Đề bài vấn đề n-queens là bài toán đặt n quân hậu trê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ề tất cả các giải pháp riêng biệt cho bài toán n-queens. Bạn có thể trả về các giải pháp theo bất kỳ thứ tự nào.

Mỗi giải pháp bao gồm một bố cục bàn cờ riêng biệt của các quân hậu, trong đó ‘Q’ và ‘.’ lần lượt chỉ ra một quân hậu và một ô trống.

Ví dụ 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
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ị ở trên.

Ví dụ 2:

Input: n = 1
Output: [["Q"]]

Ràng buộc:

• 1 <= n <= 9

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

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

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

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

Đâ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).

Thuật toán này sử dụng phương pháp backtracking để tìm kiếm tất cả các giải pháp có thể. Ý tưởng chính của thuật toán là đặt từng quân hậu vào các ô trống trên bàn cờ, kiểm tra tính hợp lệ của vị trí đặt và tiếp tục đệ quy để tìm kiếm các vị trí đặt hậu tiếp theo.

Đầu tiên, hàm `solveNQueens` khởi tạo một vector 2 chiều `ans` để lưu trữ tất cả các giải pháp. Sau đó, nó gọi hàm `dfs` để thực hiện quá trình tìm kiếm.

Trong hàm `dfs`, tham số `n` là kích thước của bàn cờ và `i` là chỉ số hàng hiện tại đang xét. Các tham số `cols`, `diag1`, `diag2`, `board` lần lượt là các vector và ma trận để lưu trữ thông tin về vị trí đã được đặt quân hậu.

Nếu `i` bằng `n`, tức là đã đặt quân hậu vào tất cả các hàng, ta có một giải pháp hợp lệ. Lúc này, ta thêm `board` vào `ans` 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 đặt quân hậu vào ô đó và đánh dấu các 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 và đặt lại giá trị của ô đang xét thành trống. Tiếp tục duyệt các cột còn lại.

Khi tất cả các vị trí đặt quân hậu đã được xét hết trong hàng hiện tại, thuật toán sẽ trở lại các bước trước đó để thử các vị trí khác.

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

class Solution {
  public List<List<String>> solveNQueens(int n) {
    List<List<String>> ans = new ArrayList<>();
    char[][] board = new char[n][n];

    for (int i = 0; i < n; ++i)
      Arrays.fill(board[i], '.');

    dfs(n, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], board, ans);
    return ans;
  }

  private void dfs(int n, int i, boolean[] cols, boolean[] diag1, boolean[] diag2, char[][] board,
                   List<List<String>> ans) {
    if (i == n) {
      ans.add(construct(board));
      return;
    }

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

  private List<String> construct(char[][] board) {
    List<String> listBoard = new ArrayList<>();
    for (int i = 0; i < board.length; ++i)
      listBoard.add(String.valueOf(board[i]));
    return listBoard;
  }
}

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

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

    def dfs(i: int, board: List[int]) -> None:
      if i == n:
        ans.append(board)
        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, board + ['.' * j + 'Q' + '.' * (n - j - 1)])
        cols[j] = diag1[i + j] = diag2[j - i + n - 1] = False

    dfs(0, [])
    return ans