Leetcode 51: N-Queens - Ứng dụng thuật toán quay lui

Mặc dù Leetcode 51: N-Queens được Leetcode đánh giá là khó, nhưng về bản chất thì mình thấy đây không hẳn là một bài vò đầu bức tóc nếu các bạn đã làm qua các bài về Depth First Search hay DFS (Tìm kiếm theo chiều sâu) và Backtracking (Thuật toán quay lui).

Leetcode 51: N-Queens - Ứng dụng thuật toán quay lui

Mặc dù Leetcode 51: N-Queens được Leetcode đánh giá là khó, nhưng về bản chất thì mình thấy đây không hẳn là một bài vò đầu bức tóc nếu các bạn đã làm qua các bài về Depth First Search hay DFS (Tìm kiếm theo chiều sâu)Backtracking (Thuật toán quay lui).

Trước khi đi vào các phần quan trọng để giải bài này, mình sẽ tóm tắt sơ lược các số liệu mà đề cung cấp và đưa ra hướng giải quyết dựa vào kiến thức DFS và Backtracking.

Leetcode 51: N-Queens là một bài điển hình cho thuật toán quay lui và mình thấy đây cũng là một bài thực tế và rất đáng để giải. Giá trị đầu vào của bài này là độ dài cạnh N của một bàn cờ vua hình vuông với diện tích là NxN.  Và thuật toán của bạn phải giải quyết được vấn đề để đặt N quân hậu (Ký hiệu: Q) vào bàn cờ ở trên sao cho các quận hậu không thể tấn công lẫn nhau. Bài này cũng khá là giống với bài Sudoku Solver khi số lượng hoán vị các lựa chọn để tìm ra đáp án phù hợp là quá lớn. Nếu chỉ chạy hai vòng lặp để quét qua toàn bộ bàn cờ (O(n^2)) và đặt các vị trí con cờ cho phù hợp thì độ phức tạp thời gian là rất lớn. Do đó đối với bài này, Sử dụng thuật toán quay lui sau đó pruning (khái niệm trong backtracking, có thể hiểu là cắt tỉa các lựa chọn dựa trên các điều kiện được đặt ra) các lựa chọn không hợp lệ để tìm ra đáp án thoả điều kiện

Thuật toán quay lui (Backtracking)

Về mặt ý tưởng, backtracking được xây dựng dựa trên đệ quy, hay ở một khía cạnh khác, backtracking lại khá là giống với DFS. Cụ thể hơn về cách backtracking hoạt động thì thuật toán sẽ tìm kiếm các lực chọn khả dĩ sau khi đã pruning. Sau đó, tiếp tục đệ quy các lựa chọn đó cho đến khi tìm được đáp án cuối cùng. Các bài toán backtracking thường có dạng

if (thoả điều kiện của đề bài){
	trả về base case (trường hợp cơ sở) và không đệ quy
} else {
	đánh dấu trạng thái
    	đệ quy trạng thái được đánh dấu
    	huỷ đánh dấu trạng thái
}
Dạng tổng quát của các phương pháp backtracking

Nếu đặt backtracking trong ngữ cảnh của cơ sỡ dữ liệu đồ thị và cây thì thuật toán này tương tự với DFS. DFS cũng sẽ loan qua các phần tử theo chiều sâu cho đến khi kết thúc nhánh và tiếp tục đệ quy để loan tương tự cho các nhánh lân cận. Một điểm khác biệt điển hình giữa DFS thông thường và backtracking là pruning. Bằng cách prune các hoán vị lựa chọn, chúng ta sẽ giảm thiểu được phần lớn các lựa chọn không hợp lệ, từ đó tối ưu hoá thuật toán quay lui.

 Ứng dụng để giải Leetcode 51: N-Queens

Trước đi đến bước áp dụng backtracking vào giải bài này, ta sẽ cần phân tích đề bài 1 chút. Theo như miêu tả đường đi của quân Hậu trong cờ vua ở trên, chúng ta biết được quân có 2 trường hợp không lệ đó là bị tần công theo chiều xéo và tấn công theo chiều dọc. Do đó ta sẽ có các hàm sau để kiểm tra từng trường hợp. Đối với kiểm tra hàng dọc, ta sẽ lặp qua các hàng trước đó để kiếm tra xem tại vị trí cột X (cột đặt quân Hậu hiện tại) mỗi hàng đã có bất kì quân hậu nào chưa:

 pub fn validate_vertical(board: &mut Vec<Vec<String>>, row: usize, col: usize) -> bool {
    for r in 0..row {
      if board[r][col] == "Q".to_string() {
        return false;
      }
    }
    true
  }
Kiếm tra hàng dọc

Và kiểm tra xéo trái, hay xéo 45 độ

 pub fn validate_45_degree_diagonal(board: &mut Vec<Vec<String>>, row: usize, col: usize) -> bool {
    let mut i = row as i32 - 1;
    let mut j = col as i32 - 1;
    while i >= 0 && j >= 0 {
      if board[i as usize][j as usize] == "Q".to_string() {
        return false;
      }
      i -= 1;
      j -= 1;
    }

    true
  }
Kiểm tra xéo trái, góc 45 độ

Và kiểm tra xéo phải, góc 135 độ

 pub fn validate_135_degree_diagonal(
    board: &mut Vec<Vec<String>>,
    row: usize,
    col: usize,
  ) -> bool {
    let mut i = row as i32 - 1;
    let mut j = col as i32 + 1;
    while i >= 0 && j < board.len() as i32 {
      if board[i as usize][j as usize] == "Q".to_string() {
        return false;
      }
      i -= 1;
      j += 1;
    }

    true
  }
Kiểm tra xéo phải, góc 135 độ

Lưu ý, mặc dù quân Hậu có thể đi ngang, tương tự quân Xe, tuy nhiên, tấn công theo chiều ngang sẽ không bao giờ khả thi vì thế nên chúng ta sẽ chỉ đặt mỗi hàng 1 quân Hậu.

Hai trường hợp không hợp lệ

Nếu suy nghĩ theo hướng từ trên xuống (top-down), khi đặt quân cờ vào bàn, ta cần kiểm tra xem các đường đi của quân cờ trước đó có đang tấn công quân cờ hiện tại được đặt vào hay không. Tuy nhiên, nếu làm như vậy, với mỗi quân cờ được đặt vào, ta sẽ phải chạy vòng lặp qua các quần cờ trước đó để xét tính hợp lệ. Do đó, bài này ta sẽ suy nghĩ theo hướng từ dưới lên (bottom-up), đó là mỗi khi đặt quân cờ vào, ta sẽ kiểm tra xem quân cờ này có đang tấn công quân cờ nào trước đó hay không. Ta sẽ có hàm validate_spot() để kiểm tra các đường đi của quân Hậu.

 pub fn validate_spot(board: &mut Vec<Vec<String>>, row: usize, col: usize) -> bool {
    Solution::validate_vertical(board, row, col)
      && Solution::validate_45_degree_diagonal(board, row, col)
      && Solution::validate_135_degree_diagonal(board, row, col)
  }
Hàm validate spot từ xây dựng từ 3 hàm phía trên (Ta sẽ kiểm tra cả 3 trường hợp: Xéo trái, xéo phải và hàng dọc)

Để thấy rõ được điểm khác biệt giữa hai hướng suy nghĩ này, bạn hãy xem hình dưới đây:

Hai hướng suy nghĩ cho cách kiểm tra vị trí hợp lệ của quân cờ

Để giải quyết bài toán này, ta sẽ đi tuần tự từ trên xuống. Tưởng tượng ngay lúc đầu, bàn cờ của chúng ta chưa có bất kì quân cờ nào trên bàn, ta sẽ đi từ hàng đầu tiên của bàn cờ từ trên xuống và đặt quân cờ đầu tiên. Dựa vào hướng suy nghĩ bottom-up cho cách xét tính hợp lệ của quân Hậu, ta có thể thấy được quân cờ của hàng đầu tiên là luôn luôn hợp lệ, tuy nhiên, vị trí của quân Hậu đầu tiên sẽ ảnh hưởng đến lựa chọn cuối cùng.

Ở hàng tiếp theo, ta có thể dễ dàng thấy được, sẽ có hai đến ba trường hợp mà quân Hậu hàng 2 không hợp lệ (phụ thuộc vào vị trí đặt quân hậu hàng 1): Xéo trái, xéo phải và thẳng. Vì vậy, với mỗi hoán vị lựa chọn, ta phải kiểm tra xem vị trí đó có hiệu lực chưa để có thể đi tiếp tới các hàng tiếp theo, đây gọi là pruning, nếu không hiệu lực, dừng lại và quay lai về các hoán vị lựa chọn khác, đây là ứng dụng của backtracking.

Hoán vị lựa chọn của một vị trí quân Hậu hàng 1 trong bàn cờ 4x4

Áp dụng lý thuyết và mẫu hình chung cho các bài toán backtracking, ta có thuật toán hoàn thiện như sau:

Nếu bạn không xem được code nhúng, bạn có thể xem gist cho toàn bộ thuật toán tại đây

Leetcode 51: N-Queens
Leetcode 51: N-Queens. GitHub Gist: instantly share code, notes, and snippets.

Subscribe to Tin Chung's Blog

Sign up now to get access to the library of members-only issues.
Jamie Larson
Subscribe