Bài toán N Hậu

Độ khó: Khó

Theo quy tắc cờ vua, quân hậu có thể tấn công các quân khác nằm cùng hàng, cùng cột hoặc cùng đường chéo.

Bài toán N Hậu nghiên cứu cách đặt n quân hậu lên bàn cờ kích thước n×n sao cho chúng không thể tấn công lẫn nhau.

Cho một số nguyên n, hãy trả về tất cả các cách đặt hậu khác nhau thỏa mãn điều kiện trên.

Mỗi giải pháp sẽ chứa một mảng các chuỗi biểu diễn vị trí của các quân hậu, trong đó 'Q' đại diện cho quân hậu và '.' đại diện cho ô trống.

Ví dụ 1:

Đầu vào: n = 4
Đầu ra: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Giải thích: Hình minh họa cho thấy bài toán N Hậu với n=4 có hai nghiệm khác nhau.

Ví dụ 2:

Đầu vào: n = 1
Đầu ra: [["Q"]]

Điều kiện:

• 1 <= n <= 9

Ghi chú cốt lõi: Bài toán N Hậu

1. Tư tưởng chính (Tóm tắt bằng một câu)

"Chỉ đặt một quân hậu mỗi hàng, dùng ba mảng để kiểm tra khả năng đặt."

Ta đi từ hàng đầu tiên đến hàng cuối cùng, mỗi hàng chỉ chọn đúng một cột để đặt hậu.

Để kiểm tra nhanh liệu vị trí (r, c) có hợp lệ hay không, ta cần ba mảng boolean để lưu lại các cột, đường chéo chính và đường chéo phụ đã bị chiếm.

2. Khó khăn cốt lõi: Công thức đường chéo (Ma thuật toán học)

Làm thế nào để xác định nhanh (r, c) thuộc đường chéo nào?

• Cột: Dễ dàng là c.

• Đường chéo phụ (/): Giá trị r + c là hằng số.

• Ví dụ: (0, 2), (1, 1), (2, 0) đều có tổng bằng 2.

• Đường chéo chính (): Giá trị r - c là hằng số.

• Ví dụ: (0, 0), (1, 1), (2, 2) đều có hiệu bằng 0.

• Lưu ý: r - c có thể âm, vì vậy phải cộng thêm độ lệch n - 1 để đảm bảo chỉ số không âm: r - c + n - 1.

3. Quy trình thuật toán (Ba bước)

1. Khởi tạo mảng ghi nhớ (Init): Khởi tạo ba mảng boolean col, diag1 (chéo chính), diag2 (chéo phụ). Độ dài của diag là 2n - 1.
2. Duyệt từng hàng (DFS):

• Với hàng hiện tại r, thử từng cột c.
• Kiểm tra: Nếu col[c], diag1[r+c], hoặc diag2[r-c+offset] là true, bỏ qua.
• Đặt hậu: Đánh dấu true, lưu queens[r] = c.
• Đệ quy: Tiếp tục với hàng r + 1.
• Hoàn tác (backtrack): Đặt lại thành false.

3. Tạo bảng cờ (Output): Chỉ khi r == n, dùng mảng queens để tạo danh sách chuỗi kết quả.

Mã nguồn (có chú thích)

// Bài tập: LC 51. N-Queens
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queens = new int[n]; // queens[row] = col: quân hậu ở hàng row nằm ở cột col
        
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // đường chéo chính: r + c
        boolean[] diag2 = new boolean[2 * n - 1]; // đường chéo phụ: r - c + n - 1
        
        backtrack(0, queens, cols, diag1, diag2, result);
        return result;
    }

    private void backtrack(int row, int[] queens, boolean[] cols, boolean[] diag1, boolean[] diag2, List<List<String>> result) {
        int size = cols.length;
        
        if (row == size) {
            // Chuyển đổi trạng thái từ mảng int sang List<String>
            List<String> board = new ArrayList<>(size);
            for (int col : queens) {
                char[] line = new char[size];
                Arrays.fill(line, '.');
                line[col] = 'Q';
                board.add(new String(line));
            }
            result.add(board);
            return;
        }

        for (int col = 0; col < size; col++) {
            int diagIndex = row - col + size - 1;

            if (!cols[col] && !diag1[row + col] && !diag2[diagIndex]) {
                queens[row] = col;
                cols[col] = true;
                diag1[row + col] = true;
                diag2[diagIndex] = true;

                backtrack(row + 1, queens, cols, diag1, diag2, result);

                cols[col] = false;
                diag1[row + col] = false;
                diag2[diagIndex] = false;
            }
        }
    }
}

Kiểm tra nhanh (Những điểm dễ nhầm)

• [ ] Kích thước mảng đường chéo?
• Là 2 * n - 1.
• Lý do: Tổng lớn nhất của r + c là 2n - 2, nên mảng cần có 2n - 1 phần tử.
• [ ] Quên công thức đường chéo chính?
• Nhớ: "Đường chéo cộng" (/) và "đường chéo trừ" (\).
• diag1: r + c.
• diag2: r - c + (n - 1). Nếu không cộng n - 1, vị trí (0, n-1) sẽ ra chỉ số âm.
• [ ] Tại sao không cần mảng hàng?
• Vì quá trình đệ quy dfs(r, ...) → dfs(r+1, ...) xử lý từng hàng một, không bao giờ đặt hai quân hậu cùng hàng, nên không cần kiểm tra hàng.

Mô phỏng ví dụ

Giả sử n = 4, đang xét vị trí (0, 1) – đặt hậu ở hàng 0, cột 1.

1. Ghi nhận:

• cols[1] = true
• diag1[0+1 = 1] = true
• diag2[0-1+3 = 2] = true

2. Tiếp tục: DFS(1) (hàng 1):

• Thử (1, 0):
• cols[0] OK.
• diag1[1+0 = 1] → False! (trùng đường chéo phụ với (0,1)).
• Bỏ qua.
• Thử (1, 1):
• cols[1] → False! (trùng cột).
• Bỏ qua.
• Thử (1, 2):
• diag2[1-2+3 = 2] → False! (trùng đường chéo chính với (0,1)).
• Bỏ qua.
• Thử (1, 3):
• Tất cả đều OK → Đặt hậu!

(Kết quả cuối cùng: (0,1) → (1,3) → ...)