N-Queens: đặt xung đột dưới ràng buộc, rồi tỉa cây quyết định

Bài toán 8 quân hậu đã có lịch sử 170 năm. Phiên bản LeetCode giới hạn n <= 9, nghĩa là toàn bộ ràng buộc là: đặt n quân hậu trên bàn cờ n×n sao cho không có hai quân hậu nào chia sẻ hàng ngang, cột dọc, hay đường chéo. Giới hạn đó quan trọng. Với n <= 9, không gian tìm kiếm đủ nhỏ để ngay cả một backtracker đơn giản cũng chạy xong trong tích tắc, nhưng bài toán vẫn đáng hiểu tại sao việc tỉa cây lại hiệu quả — vì cùng cấu trúc đó xuất hiện trong những bài constraint-satisfaction khó hơn nhiều.

Ba điều giúp bài toán này có thể giải được. Một, đúng một quân hậu mỗi hàng (n quân hậu, n hàng). Hai, xung đột đường chéo rút gọn về một công thức số học đơn giản. Ba, backtracking cho phép bạn loại toàn bộ một nhánh con ngay khi một vị trí đặt thất bại.

Đề bài

Đặt n quân hậu trên bàn cờ n x n sao cho không có hai quân hậu nào tấn công nhau — không chia sẻ hàng ngang, cột dọc, hay đường chéo — và trả về tất cả cách sắp xếp bàn cờ hợp lệ dưới dạng mảng string, trong đó 'Q' là quân hậu và '.' là ô trống. Full statement: LeetCode 51.

Ràng buộc:
- 1 <= n <= 9

Constraint 1 <= n <= 9 mang lại gì

n nhỏ là constraint quan trọng nhất ở đây. Số nghiệm hợp lệ tăng nhanh (n=8 có 92 nghiệm, n=9 có 352), nhưng cây tìm kiếm bị chặn bởi n!. Ở n=9 đó là 362880 lá trước khi tỉa bất kỳ nhánh nào — và việc tỉa cắt số node thực sự được thăm xuống chỉ còn một phần nhỏ của con số đó.

Vì n bị giới hạn trong một chữ số, bạn sẽ không bao giờ bị stack overflow do độ sâu recursion (độ sâu call tối đa là n = 9). Bạn không cần đi theo hướng iterative vì lý do an toàn. Bạn không cần memoization — không có overlapping substructure. Đây là bài toán generate-all-solutions, và backtracking là công cụ chính tắc cho nó.

Constraint cũng cho bạn biết rằng O(n!) time hoàn toàn chấp nhận được. Các giải pháp vượt qua O(n!) hay tốn O(n^2) mỗi lần đặt quân là đang làm thừa, nhưng ngay cả chúng cũng chạy nhanh với kích thước này. Điều khác nhau giữa các approach là hằng số bên trong envelope O(n!) — cụ thể là bao nhiêu công việc bạn bỏ ra để kiểm tra mỗi vị trí đặt.

Approach 1: brute force — liệt kê tất cả, lọc sau

Đọc ngây thơ nhất: chọn bất kỳ n ô nào trong n^2 ô, kiểm tra xem vị trí đặt có hợp lệ không, giữ lại nếu đúng.

from itertools import combinations
 
class Solution:
    def solveNQueens(self, n: int):
        all_positions = [(i, j) for i in range(n) for j in range(n)]
        results = []
 
        for positions in combinations(all_positions, n):
            if self._is_valid(positions):
                results.append(self._build_board(positions, n))
 
        return results
 
    def _is_valid(self, positions):
        for i in range(len(positions)):
            for j in range(i + 1, len(positions)):
                r1, c1 = positions[i]
                r2, c2 = positions[j]
                if r1 == r2 or c1 == c2 or abs(r1 - r2) == abs(c1 - c2):
                    return False
        return True
 
    def _build_board(self, positions, n):
        board = [['.' for _ in range(n)] for _ in range(n)]
        for r, c in positions:
            board[r][c] = 'Q'
        return [''.join(row) for row in board]

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var allPositions = new List<(int, int)>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                allPositions.Add((i, j));
 
        foreach (var positions in Combinations(allPositions, n)) {
            if (IsValid(positions))
                results.Add(BuildBoard(positions, n));
        }
        return results;
    }
 
    private bool IsValid(List<(int, int)> positions) {
        for (int i = 0; i < positions.Count; i++) {
            for (int j = i + 1; j < positions.Count; j++) {
                var (r1, c1) = positions[i];
                var (r2, c2) = positions[j];
                if (r1 == r2 || c1 == c2 || Math.Abs(r1 - r2) == Math.Abs(c1 - c2))
                    return false;
            }
        }
        return true;
    }
 
    private IList<string> BuildBoard(List<(int, int)> positions, int n) {
        var board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            Array.Fill(board[i], '.');
        }
        foreach (var (r, c) in positions)
            board[r][c] = 'Q';
        return board.Select(row => new string(row)).ToList();
    }
 
    private IEnumerable<List<(int, int)>> Combinations(List<(int, int)> src, int k) {
        if (k == 0) { yield return new List<(int, int)>(); yield break; }
        for (int i = 0; i <= src.Count - k; i++) {
            foreach (var rest in Combinations(src.GetRange(i + 1, src.Count - i - 1), k - 1)) {
                rest.Insert(0, src[i]);
                yield return rest;
            }
        }
    }
}

Time: O(C(n^2, n) * n^2). Với n=8 là C(64, 8) = 4,426,165,368 tập hợp ứng cử viên trước khi tỉa bất kỳ nhánh nào — mỗi tập kiểm tra trong O(n^2). Điều này chạy trong vài phút trong thực tế. Space: O(n^2) cho bàn cờ.

Điểm mấu chốt của việc trình bày approach này không phải để bạn submit nó. Mà là brute force làm cấu trúc constraint trở nên rõ ràng: ba phép kiểm tra xung đột (cùng hàng, cùng cột, cùng đường chéo) là thứ duy nhất quan trọng. Tất cả những gì còn lại chỉ là giảm số ứng cử viên bạn cần kiểm tra.

Approach 2: backtracking theo hàng — mỗi hàng một quân hậu, kiểm tra trước khi đặt

Insight then chốt mở ra mọi thứ: vì chúng ta cần đúng một quân hậu mỗi hàng, ta có thể đặt quân hậu từng hàng và không bao giờ nhìn lại. Xung đột hàng ngang là không thể xảy ra theo cấu trúc. Điều đó rút gọn bài toán chỉ còn xung đột cột và đường chéo, và thu nhỏ cây tìm kiếm từ C(n^2, n) xuống còn tối đa n^n lá (tiếp tục được tỉa bởi các phép kiểm tra xung đột).

Bàn cờ bây giờ chỉ là một mảng queens trong đó queens[row] = cột của quân hậu ở hàng đó. Không cần lưới 2D trong quá trình tìm kiếm.

class Solution:
    def solveNQueens(self, n: int):
        results = []
        queens = [-1] * n
 
        def backtrack(row):
            if row == n:
                results.append(self._build_board(queens, n))
                return
            for col in range(n):
                if self._is_safe(queens, row, col):
                    queens[row] = col
                    backtrack(row + 1)
                    queens[row] = -1
 
        backtrack(0)
        return results
 
    def _is_safe(self, queens, row, col):
        for i in range(row):
            if queens[i] == col:
                return False
            if abs(queens[i] - col) == abs(i - row):
                return False
        return True
 
    def _build_board(self, queens, n):
        board = []
        for i in range(n):
            row = ['.'] * n
            row[queens[i]] = 'Q'
            board.append(''.join(row))
        return board

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var queens = new int[n];
        Array.Fill(queens, -1);
        Backtrack(0, n, queens, results);
        return results;
    }
 
    private void Backtrack(int row, int n, int[] queens, IList<IList<string>> results) {
        if (row == n) {
            results.Add(BuildBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (IsSafe(queens, row, col)) {
                queens[row] = col;
                Backtrack(row + 1, n, queens, results);
                queens[row] = -1;
            }
        }
    }
 
    private bool IsSafe(int[] queens, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col) return false;
            if (Math.Abs(queens[i] - col) == Math.Abs(i - row)) return false;
        }
        return true;
    }
 
    private IList<string> BuildBoard(int[] queens, int n) {
        var board = new List<string>();
        for (int i = 0; i < n; i++) {
            var row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }
        return board;
    }
}

Time: O(n!) — cùng lớp tiệm cận với brute force, nhưng hằng số nhỏ hơn nhiều. Lời gọi _is_safe tốn O(row) cho mỗi ứng cử viên, nên tổng công việc bị chặn bởi O(n! * n). Space: O(n) cho mảng queens và call stack.

Trace tay: n=4, tìm nghiệm đầu tiên

Cây quyết định cho n=4 trông như thế này — mỗi tầng là một hàng, mỗi cạnh là một lựa chọn cột, các nhánh đánh dấu x bị tỉa do xung đột:

Từng bước:

• row=0, col=0: đặt quân. queens = [0, -1, -1, -1]
• row=1, col=0: cùng cột với hàng 0 -> bỏ qua
• row=1, col=1: đường chéo? abs(0-1) == abs(0-1) -> có -> bỏ qua
• row=1, col=2: cột ok, đường chéo abs(0-2)=2, abs(0-1)=1 -> ok. Đặt. queens = [0, 2, -1, -1]
• row=2: thử tất cả cột. Tất cả đều xung đột với queen tại (0,0) hoặc (1,2). Backtrack.
• row=1, col=3: cột ok, đường chéo abs(0-3)=3, abs(0-1)=1 -> ok. Đặt. queens = [0, 3, -1, -1]
• row=2, col=1: cột ok, đường chéo từ hàng 0 ok, đường chéo từ hàng 1 abs(3-1)=2, abs(1-2)=1 ok. Đặt. queens = [0, 3, 1, -1]
• row=3: chỉ col=2 vượt qua tất cả kiểm tra. Đặt. queens = [0, 3, 1, 2]
• row=4 == n -> lưu bàn cờ. Nghiệm đầu tiên: ["Q...", "...Q", ".Q..", "..Q."].

Sau đó backtracking tìm nghiệm thứ hai queens = [1, 3, 0, 2], cho ra [".Q..", "...Q", "Q...", "..Q."]. Tổng cộng hai nghiệm cho n=4, khớp với output mong đợi.

Approach 3: backtracking với set-based conflict tracking — O(1) mỗi lần kiểm tra

Nút thắt cổ chai trong Approach 2 là _is_safe: nó lặp qua tất cả các quân hậu đã đặt để kiểm tra xung đột cột và đường chéo. Vòng lặp đó tốn O(row) mỗi ứng cử viên. Với các set theo dõi cột và đường chéo đang bị chiếm, mỗi lần kiểm tra giảm xuống còn O(1).

Insight về đường chéo đáng được ghi nhớ. Hai ô (r1, c1) và (r2, c2) chia sẻ một đường chéo chính (trái trên xuống phải dưới) khi và chỉ khi r1 - c1 == r2 - c2. Chúng chia sẻ một đường chéo phụ (phải trên xuống trái dưới) khi và chỉ khi r1 + c1 == r2 + c2. Vì vậy, thay vì so sánh mỗi quân hậu mới với tất cả các quân hậu trước, bạn theo dõi ba set — cột đã chiếm, các giá trị (row - col) đã chiếm, các giá trị (row + col) đã chiếm — và một phép kiểm tra thành viên duy nhất bao phủ cả ba loại xung đột.

class Solution:
    def solveNQueens(self, n: int):
        results = []
        queens = []
        cols = set()
        diag_main = set()   # row - col là hằng số dọc theo đường chéo chính
        diag_anti = set()   # row + col là hằng số dọc theo đường chéo phụ
 
        def backtrack(row):
            if row == n:
                results.append(self._build_board(queens, n))
                return
            for col in range(n):
                if col in cols or (row - col) in diag_main or (row + col) in diag_anti:
                    continue
                queens.append(col)
                cols.add(col)
                diag_main.add(row - col)
                diag_anti.add(row + col)
 
                backtrack(row + 1)
 
                queens.pop()
                cols.remove(col)
                diag_main.remove(row - col)
                diag_anti.remove(row + col)
 
        backtrack(0)
        return results
 
    def _build_board(self, queens, n):
        board = []
        for i in range(n):
            row = ['.'] * n
            row[queens[i]] = 'Q'
            board.append(''.join(row))
        return board

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var queens = new List<int>();
        var cols = new HashSet<int>();
        var diagMain = new HashSet<int>();
        var diagAnti = new HashSet<int>();
 
        Backtrack(0, n, queens, cols, diagMain, diagAnti, results);
        return results;
    }
 
    private void Backtrack(int row, int n, List<int> queens,
                           HashSet<int> cols, HashSet<int> diagMain, HashSet<int> diagAnti,
                           IList<IList<string>> results) {
        if (row == n) {
            results.Add(BuildBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.Contains(col) || diagMain.Contains(row - col) || diagAnti.Contains(row + col))
                continue;
 
            queens.Add(col);
            cols.Add(col);
            diagMain.Add(row - col);
            diagAnti.Add(row + col);
 
            Backtrack(row + 1, n, queens, cols, diagMain, diagAnti, results);
 
            queens.RemoveAt(queens.Count - 1);
            cols.Remove(col);
            diagMain.Remove(row - col);
            diagAnti.Remove(row + col);
        }
    }
 
    private IList<string> BuildBoard(List<int> queens, int n) {
        var board = new List<string>();
        for (int i = 0; i < n; i++) {
            var row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }
        return board;
    }
}

Time: O(n!) vì lý do tương tự Approach 2 — cây quyết định có cùng hình dạng. Nhưng mỗi node trong cây giờ tốn O(1) để kiểm tra xung đột thay vì O(row), nên hằng số thực sự nhỏ hơn. Space: O(n) cho ba set (mỗi set chứa tối đa n phần tử), danh sách queens, và độ sâu call stack là n.

Phép toán đường chéo chi tiết hơn

Đáng bỏ ra một đoạn để hiểu tại sao row - col mã hóa đường chéo chính. Mỗi ô trên cùng một đường chéo chính thỏa mãn row - col = hằng số. Vẽ lưới 4x4 và đánh nhãn mỗi ô bằng giá trị row - col: ô trái trên cùng là 0 - 0 = 0, ô ngay bên phải là 0 - 1 = -1, ô ngay bên dưới ô trái trên là 1 - 0 = 1. Các ô trên cùng đường chéo chính đều có cùng nhãn. Phạm vi nhãn là -(n-1) đến n-1, nên có đúng 2n - 1 đường chéo chính phân biệt. Logic tương tự áp dụng cho row + col với đường chéo phụ. Hai quân hậu xung đột trên đường chéo chính khi và chỉ khi chúng có cùng row - col; trên đường chéo phụ khi và chỉ khi chúng có cùng row + col.

Đây chính xác là điều mà abs(queens[i] - col) == abs(i - row) của Approach 2 kiểm tra, nhưng Approach 3 tính toán trước nó vào các set để kiểm tra là O(1) thay vì so sánh với mỗi quân hậu đã đặt.

Phân tích các edge case

n=1: ô duy nhất (0, 0) tầm thường vượt qua tất cả kiểm tra. Một nghiệm: [["Q"]]. Cả hai approach xử lý điều này — row=0, col=0 được đặt, row=1 == n, lưu nghiệm.

n=2 và n=3: không có nghiệm nào. Với n=2: đặt quân hậu tại (0,0) chặn cột 0 và đường chéo; (1,1) bị chặn bởi đường chéo chính (row - col = 0 cho cả hai ô). (1,0) bị chặn bởi cột. Tương tự cho (0,1). Backtracker tự nhiên trả về danh sách rỗng — không cần xử lý trường hợp đặc biệt nào.

n=9: 352 nghiệm. Backtracker tìm tất cả chúng trong micro giây. Tỷ lệ tỉa nhánh rất lớn — từ n^n = 387,420,489 đường đi chưa tỉa, chỉ còn 352 nghiệm hợp lệ.

Quân hậu ở các cột biên (col=0 hoặc col=n-1): kiểm tra đường chéo bất đối xứng với các cột biên (một đường chéo phụ không tồn tại). Phép toán set xử lý điều này một cách minh bạch — các giá trị row - col và row + col cho ô biên chỉ là các con số; không cần logic biên đặc biệt.

Bảng so sánh các approach

Sự khác biệt tiệm cận giữa "O(n! * n)" và "O(n!)" chỉ quan trọng tổng hợp trên toàn bộ cây. Trong thực tế với n <= 9, cả hai approach đều gần như tức thời. Phiên bản set sạch hơn khi đọc một khi bạn hiểu phép toán đường chéo, đó là lý do tôi sẽ viết nó là mặc định.

Approach nào tôi sẽ chọn và tại sao

Backtracker với set (Approach 3). Không phải vì hiệu suất ở n <= 9 — bất cứ thứ gì cũng đánh bại brute force ở đó, và khoảng cách hiệu suất giữa Approach 2 và 3 là vô hình ở những kích thước này. Tôi chọn Approach 3 vì cấu trúc ba-set làm mô hình xung đột trở nên rõ ràng: một set mỗi chiều xung đột (cột, đường chéo chính, đường chéo phụ). Đọc code, bạn thấy ba constraint độc lập trực tiếp. Approach 2 chôn vùi cấu trúc đó trong vòng lặp của _is_safe.

Phép toán đường chéo (row - col, row + col) đáng hiểu một lần. Sau đó nó trở thành công cụ bạn với tới trong các bài grid-constraint mà không cần suy nghĩ thêm.

Tôi sẽ không ship Approach 1 trong bất kỳ trường hợp nào. C(64, 8) là quá nhiều tổ hợp để liệt kê ngay cả khi n nhỏ. Giá trị duy nhất của nó là làm tài liệu tham khảo tính đúng đắn để kiểm tra các implementation khác.

Pattern tổng quát và khả năng chuyển giao

N-Queens là ví dụ chính tắc của backtracking trên bài toán constraint-satisfaction. Bộ khung là: chọn, kiểm tra constraint, đệ quy, bỏ chọn. Cặp chọn/bỏ-chọn là điều làm cho nó thành backtracking chứ không phải recursion đơn thuần — bạn đang sửa đổi trạng thái dùng chung (queens, sets) và khôi phục nó sau đó.

Mã hóa xung đột ba-set có ứng dụng rộng hơn vẻ ngoài. Bất cứ khi nào bạn có bài toán grid cần phát hiện xung đột O(1) qua nhiều chiều constraint, thủ thuật (row - col) / (row + col) cho đường chéo là thứ đầu tiên bạn với tới.

N-Queens nằm trong series backtracking sau Subsets, Permutations, và Combination Sum. Những bài đó đã giới thiệu bộ khung chọn/đệ quy/bỏ-chọn trên các domain đơn giản hơn (mảng số, không có cross-element constraints). N-Queens thêm cross-element constraints — lựa chọn ở hàng 3 phụ thuộc vào những gì bạn đã đặt ở hàng 0, 1, 2. Đó là bước leo lên về độ khó.

N-Queens II (52) là bài tiếp theo trực tiếp: cùng logic, nhưng trả về số lượng nghiệm thay vì các nghiệm. Nếu bạn có giải pháp này, 52 là thay đổi ba dòng — thay results.append(self._build_board(...)) bằng self.count += 1.

Sudoku Solver (37) là người anh em khó hơn. Bàn cờ 9x9 với 81 ô, hàng, cột, và ô 3x3 là các constraint. Bộ khung backtracking là như nhau; kiểm tra xung đột phức tạp hơn (3 chiều constraint với các hình dạng khác nhau). Cùng approach dựa trên set hoạt động.

Word Search (79) thêm chiều khám phá không gian — thay vì đặt một phần tử mỗi hàng, bạn đi theo một đường qua lưới. Bộ khung chọn/bỏ-chọn hoàn toàn giống nhau; trạng thái được hoàn tác là marker ô đã thăm thay vì vị trí đặt quân hậu.

Permutations (46) đơn giản hơn ở một chiều (không có đường chéo) nhưng có cùng bất biến "mỗi phần tử dùng đúng một lần" được thực thi bởi một used set. Cùng cấu trúc.