N-Queens — Backtracking và nghệ thuật cắt tỉa

Năm 1848, nhà toán học Max Bezzel đặt câu hỏi: có thể đặt 8 quân hậu trên bàn cờ 8×8 sao cho không quân nào tấn công quân nào không? Câu hỏi đơn giản này trở thành một trong những bài toán kinh điển nhất của khoa học máy tính — không phải vì khó giải cho N=8 (92 nghiệm), mà vì nó là bài test thuần khiết nhất cho paradigm Backtracking. Nếu bạn giải được N-Queens đúng cách, bạn hiểu backtracking.

Trong production, N-Queens hiếm khi xuất hiện nguyên bản. Nhưng cấu trúc bài toán — đặt N đối tượng trên lưới sao cho thỏa mãn tập ràng buộc (constraints) — xuất hiện khắp nơi: phân bổ tần số vô tuyến tránh nhiễu, xếp lịch thi không trùng giờ phòng, bố trí linh kiện VLSI không chồng lấn. Đây đều là Constraint Satisfaction Problems (CSP), và backtracking là engine giải CSP phổ biến nhất.

Bài học này không chỉ dừng ở "viết hàm đệ quy đặt hậu". Bạn sẽ học cách biến thuật toán brute-force O(N^N) thành giải pháp thực tế qua pruning (cắt tỉa), constraint propagation (lan truyền ràng buộc), và tối ưu bitwise — kỹ thuật giảm kiểm tra xung đột từ O(N) xuống O(1).

Bức tranh tư duy

Hình dung bạn đang xếp bàn tiệc cưới ở một nhà hàng Sài Gòn. Có N vị khách "khó tính" — mỗi người không chịu ngồi cùng hàng, cùng cột, hoặc cùng đường chéo với bất kỳ ai khác. Bạn phải xếp từng người một, và nếu đến một lúc không còn chỗ hợp lệ cho khách tiếp theo — bạn phải dời khách trước đó sang ghế khác rồi thử lại.

Đây chính là backtracking: thử → kiểm tra → tiến tới hoặc quay lui.

text

N = 4: Quá trình tìm nghiệm

Bước 1: Đặt Q ở hàng 0, cột 0
  Q . . .       Bước 2: Hàng 1, cột 0,1 bị chặn → thử cột 2
  . . Q .       Bước 3: Hàng 2, TẤT CẢ cột bị chặn! → QUAY LUI
  . . . .
  . . . .

Quay lui: Dời Q hàng 1 → cột 3
  Q . . .       Bước 3: Hàng 2, cột 1 hợp lệ
  . . . Q       Bước 4: Hàng 3, cột 2 hợp lệ → NGHIỆM!
  . Q . .
  . . . Q       Kết quả: [0, 3, 1, 2] ← cột của Q mỗi hàng

Số nghiệm theo N:
┌─────┬───────────┬──────────────────────────┐
│  N  │ Nghiệm   │  Nghiệm phân biệt        │
│     │ (tổng)    │  (bỏ đối xứng/xoay)      │
├─────┼───────────┼──────────────────────────┤
│  1  │     1     │         1                │
│  4  │     2     │         1                │
│  8  │    92     │        12                │
│ 12  │  14.200   │     1.787                │
│ 14  │ 365.596   │    45.752                │
└─────┴───────────┴──────────────────────────┘

Quan sát quan trọng: Mỗi hàng chỉ có đúng 1 quân hậu (vì 2 quân cùng hàng tấn công nhau). Vậy bài toán rút gọn thành: chọn 1 cột cho mỗi hàng, sao cho không vi phạm ràng buộc cột và đường chéo. Thay vì duyệt N^N khả năng (đặt tự do), ta chỉ duyệt N! hoán vị cột — giảm đáng kể không gian tìm kiếm ngay từ đầu.

Cốt lõi kỹ thuật

Kiểm tra xung đột — Phiên bản cơ bản O(N)

Khi đặt quân hậu ở hàng row, cột col, cần kiểm tra 3 ràng buộc với tất cả quân đã đặt ở các hàng trước:

text

Ràng buộc 1: Cùng cột     → board[i] == col
Ràng buộc 2: Đường chéo ↘  → |row - i| == |col - board[i]|
Ràng buộc 3: Đường chéo ↗  → (tương tự, nằm trong công thức trên)

Nhận xét đường chéo:
- Đường chéo chính (↘): row - col = hằng số
- Đường chéo phụ (↗): row + col = hằng số

Backtracking cơ bản

C++PythonJavaGo

cpp

#include <vector>
#include <cmath>

class NQueens {
public:
    std::vector<std::vector<int>> solveAll(int n) {
        std::vector<std::vector<int>> solutions;
        std::vector<int> board(n, -1);
        backtrack(board, 0, n, solutions);
        return solutions;
    }

private:
    void backtrack(std::vector<int>& board, int row, int n,
                   std::vector<std::vector<int>>& solutions) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                backtrack(board, row + 1, n, solutions);
                board[row] = -1;
            }
        }
    }

    bool isSafe(const std::vector<int>& board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col ||
                std::abs(board[i] - col) == std::abs(i - row)) {
                return false;
            }
        }
        return true;
    }
};

python

def solve_n_queens(n: int) -> list[list[int]]:
    """Tìm tất cả nghiệm N-Queens. Trả về list các hoán vị cột."""
    solutions = []
    board = [-1] * n

    def is_safe(row: int, col: int) -> bool:
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == abs(i - row):
                return False
        return True

    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1

    backtrack(0)
    return solutions

java

import java.util.ArrayList;
import java.util.List;

public class NQueens {
    public List<int[]> solveAll(int n) {
        List<int[]> solutions = new ArrayList<>();
        int[] board = new int[n];
        java.util.Arrays.fill(board, -1);
        backtrack(board, 0, n, solutions);
        return solutions;
    }

    private void backtrack(int[] board, int row, int n,
                           List<int[]> solutions) {
        if (row == n) {
            solutions.add(board.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                backtrack(board, row + 1, n, solutions);
                board[row] = -1;
            }
        }
    }

    private boolean isSafe(int[] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col ||
                Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }
}

package nqueens

import "math"

func SolveAll(n int) [][]int {
	var solutions [][]int
	board := make([]int, n)
	for i := range board {
		board[i] = -1
	}

	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			sol := make([]int, n)
			copy(sol, board)
			solutions = append(solutions, sol)
			return
		}
		for col := 0; col < n; col++ {
			if isSafe(board, row, col) {
				board[row] = col
				backtrack(row + 1)
				board[row] = -1
			}
		}
	}

	backtrack(0)
	return solutions
}

func isSafe(board []int, row, col int) bool {
	for i := 0; i < row; i++ {
		if board[i] == col ||
			math.Abs(float64(board[i]-col)) == math.Abs(float64(i-row)) {
			return false
		}
	}
	return true
}

Tối ưu O(1) với Set — Constraint Propagation

Thay vì kiểm tra tất cả hàng trước mỗi lần đặt (O(N)), dùng 3 tập hợp (set) theo dõi cột và đường chéo đã bị chiếm:

text

Nhận xét chìa khóa:
- Cột bị chiếm: cols = {col}
- Đường chéo ↘:  diag1 = {row - col}  (hằng số trên cùng đường chéo)
- Đường chéo ↗:  diag2 = {row + col}  (hằng số trên cùng đường chéo)

Kiểm tra: col ∉ cols AND (row-col) ∉ diag1 AND (row+col) ∉ diag2 → O(1)

C++PythonJavaGo

cpp

#include <vector>
#include <unordered_set>

class NQueensOptimized {
public:
    std::vector<std::vector<int>> solveAll(int n) {
        std::vector<std::vector<int>> solutions;
        std::vector<int> board;
        std::unordered_set<int> cols, diag1, diag2;
        backtrack(board, 0, n, cols, diag1, diag2, solutions);
        return solutions;
    }

private:
    void backtrack(std::vector<int>& board, int row, int n,
                   std::unordered_set<int>& cols,
                   std::unordered_set<int>& diag1,
                   std::unordered_set<int>& diag2,
                   std::vector<std::vector<int>>& solutions) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col, d2 = row + col;
            if (cols.count(col) || diag1.count(d1) || diag2.count(d2))
                continue;

            board.push_back(col);
            cols.insert(col);
            diag1.insert(d1);
            diag2.insert(d2);

            backtrack(board, row + 1, n, cols, diag1, diag2, solutions);

            board.pop_back();
            cols.erase(col);
            diag1.erase(d1);
            diag2.erase(d2);
        }
    }
};

python

def solve_n_queens_optimized(n: int) -> list[list[int]]:
    """N-Queens với kiểm tra xung đột O(1) bằng set."""
    solutions = []
    board: list[int] = []
    cols: set[int] = set()
    diag1: set[int] = set()   # row - col
    diag2: set[int] = set()   # row + col

    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            d1, d2 = row - col, row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue

            board.append(col)
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)

            backtrack(row + 1)

            board.pop()
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)

    backtrack(0)
    return solutions

java

import java.util.*;

public class NQueensOptimized {
    public List<int[]> solveAll(int n) {
        List<int[]> solutions = new ArrayList<>();
        List<Integer> board = new ArrayList<>();
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        backtrack(board, 0, n, cols, diag1, diag2, solutions);
        return solutions;
    }

    private void backtrack(List<Integer> board, int row, int n,
                           Set<Integer> cols, Set<Integer> diag1,
                           Set<Integer> diag2, List<int[]> solutions) {
        if (row == n) {
            solutions.add(board.stream().mapToInt(i -> i).toArray());
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col, d2 = row + col;
            if (cols.contains(col) || diag1.contains(d1)
                || diag2.contains(d2))
                continue;

            board.add(col);
            cols.add(col);
            diag1.add(d1);
            diag2.add(d2);

            backtrack(board, row + 1, n, cols, diag1, diag2, solutions);

            board.remove(board.size() - 1);
            cols.remove(col);
            diag1.remove(d1);
            diag2.remove(d2);
        }
    }
}

package nqueens

func SolveAllOptimized(n int) [][]int {
	var solutions [][]int
	board := []int{}
	cols := map[int]bool{}
	diag1 := map[int]bool{}
	diag2 := map[int]bool{}

	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			sol := make([]int, len(board))
			copy(sol, board)
			solutions = append(solutions, sol)
			return
		}
		for col := 0; col < n; col++ {
			d1, d2 := row-col, row+col
			if cols[col] || diag1[d1] || diag2[d2] {
				continue
			}

			board = append(board, col)
			cols[col] = true
			diag1[d1] = true
			diag2[d2] = true

			backtrack(row + 1)

			board = board[:len(board)-1]
			delete(cols, col)
			delete(diag1, d1)
			delete(diag2, d2)
		}
	}

	backtrack(0)
	return solutions
}

Tối ưu Bitwise — Đỉnh cao hiệu năng

Với N ≤ 32 (hoặc 64), thay 3 set bằng 3 bitmask — mỗi bit đại diện cho 1 cột hoặc đường chéo. Kiểm tra xung đột trở thành phép AND bit — nhanh hơn set lookup đáng kể trên CPU hiện đại:

text

Ý tưởng:
  cols   = 0b00101  → cột 0 và 2 đã bị chiếm
  diag1  = 0b01000  → đường chéo ↘ tại index 3 bị chiếm
  diag2  = 0b10010  → đường chéo ↗ tại index 1, 4 bị chiếm

  available = ~(cols | diag1 | diag2) & ((1 << N) - 1)
  → bit 1 ở vị trí cột còn hợp lệ

  Lấy cột hợp lệ tiếp theo: col_bit = available & (-available)
  → lowest set bit trick

C++PythonJavaGo

cpp

#include <vector>

class NQueensBitwise {
    int n;
    int allMask;
    std::vector<std::vector<int>> solutions;

public:
    std::vector<std::vector<int>> solveAll(int n) {
        this->n = n;
        this->allMask = (1 << n) - 1;
        solutions.clear();
        std::vector<int> board;
        backtrack(board, 0, 0, 0);
        return solutions;
    }

    int countSolutions(int n) {
        this->n = n;
        this->allMask = (1 << n) - 1;
        return countBT(0, 0, 0);
    }

private:
    void backtrack(std::vector<int>& board,
                   int cols, int diag1, int diag2) {
        int row = board.size();
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        int available = allMask & ~(cols | diag1 | diag2);
        while (available) {
            int bit = available & (-available);
            int col = __builtin_ctz(bit);
            board.push_back(col);
            backtrack(board,
                      cols | bit,
                      (diag1 | bit) << 1,
                      (diag2 | bit) >> 1);
            board.pop_back();
            available &= available - 1;
        }
    }

    int countBT(int cols, int diag1, int diag2) {
        if (cols == allMask) return 1;
        int count = 0;
        int available = allMask & ~(cols | diag1 | diag2);
        while (available) {
            int bit = available & (-available);
            count += countBT(cols | bit,
                             (diag1 | bit) << 1,
                             (diag2 | bit) >> 1);
            available &= available - 1;
        }
        return count;
    }
};

python

def solve_n_queens_bitwise(n: int) -> list[list[int]]:
    """N-Queens tối ưu bitwise — nhanh nhất cho N ≤ 30."""
    solutions = []
    all_mask = (1 << n) - 1

    def backtrack(board: list[int], cols: int, d1: int, d2: int):
        row = len(board)
        if row == n:
            solutions.append(board[:])
            return
        available = all_mask & ~(cols | d1 | d2)
        while available:
            bit = available & (-available)
            col = bit.bit_length() - 1
            board.append(col)
            backtrack(board,
                      cols | bit,
                      (d1 | bit) << 1,
                      (d2 | bit) >> 1)
            board.pop()
            available &= available - 1

    backtrack([], 0, 0, 0)
    return solutions


def count_n_queens_bitwise(n: int) -> int:
    """Chỉ đếm nghiệm — không lưu, nhanh hơn."""
    all_mask = (1 << n) - 1

    def count(cols: int, d1: int, d2: int) -> int:
        if cols == all_mask:
            return 1
        total = 0
        available = all_mask & ~(cols | d1 | d2)
        while available:
            bit = available & (-available)
            total += count(cols | bit,
                           (d1 | bit) << 1,
                           (d2 | bit) >> 1)
            available &= available - 1
        return total

    return count(0, 0, 0)

java

import java.util.ArrayList;
import java.util.List;

public class NQueensBitwise {
    private int n;
    private int allMask;

    public int countSolutions(int n) {
        this.n = n;
        this.allMask = (1 << n) - 1;
        return countBT(0, 0, 0);
    }

    public List<int[]> solveAll(int n) {
        this.n = n;
        this.allMask = (1 << n) - 1;
        List<int[]> solutions = new ArrayList<>();
        backtrack(new ArrayList<>(), 0, 0, 0, solutions);
        return solutions;
    }

    private void backtrack(List<Integer> board,
                           int cols, int d1, int d2,
                           List<int[]> solutions) {
        if (board.size() == n) {
            solutions.add(board.stream().mapToInt(i -> i).toArray());
            return;
        }
        int available = allMask & ~(cols | d1 | d2);
        while (available != 0) {
            int bit = available & (-available);
            int col = Integer.numberOfTrailingZeros(bit);
            board.add(col);
            backtrack(board,
                      cols | bit,
                      (d1 | bit) << 1,
                      (d2 | bit) >> 1,
                      solutions);
            board.remove(board.size() - 1);
            available &= available - 1;
        }
    }

    private int countBT(int cols, int d1, int d2) {
        if (cols == allMask) return 1;
        int count = 0;
        int available = allMask & ~(cols | d1 | d2);
        while (available != 0) {
            int bit = available & (-available);
            count += countBT(cols | bit,
                             (d1 | bit) << 1,
                             (d2 | bit) >> 1);
            available &= available - 1;
        }
        return count;
    }
}

package nqueens

import "math/bits"

func SolveAllBitwise(n int) [][]int {
	allMask := (1 << n) - 1
	var solutions [][]int

	var backtrack func(board []int, cols, d1, d2 int)
	backtrack = func(board []int, cols, d1, d2 int) {
		if len(board) == n {
			sol := make([]int, n)
			copy(sol, board)
			solutions = append(solutions, sol)
			return
		}
		available := allMask & ^(cols | d1 | d2)
		for available != 0 {
			bit := available & (-available)
			col := bits.TrailingZeros(uint(bit))
			backtrack(append(board, col),
				cols|bit,
				(d1|bit)<<1,
				(d2|bit)>>1)
			available &= available - 1
		}
	}

	backtrack([]int{}, 0, 0, 0)
	return solutions
}

func CountBitwise(n int) int {
	allMask := (1 << n) - 1

	var count func(cols, d1, d2 int) int
	count = func(cols, d1, d2 int) int {
		if cols == allMask {
			return 1
		}
		total := 0
		available := allMask & ^(cols | d1 | d2)
		for available != 0 {
			bit := available & (-available)
			total += count(cols|bit,
				(d1|bit)<<1,
				(d2|bit)>>1)
			available &= available - 1
		}
		return total
	}

	return count(0, 0, 0)
}

Template Backtracking tổng quát

Mọi bài toán backtracking đều tuân theo cấu trúc 3 bước Choose → Explore → Unchoose:

text

function backtrack(state):
    if is_solution(state):
        process(state)
        return

    for choice in get_candidates(state):
        if is_valid(choice, state):
            make_choice(choice, state)       ← Choose
            backtrack(state)                 ← Explore
            undo_choice(choice, state)       ← Unchoose

Với N-Queens: state = board hiện tại, choice = cột cho hàng tiếp theo, is_valid = kiểm tra xung đột, undo = xóa quân hậu vừa đặt.

Thực chiến

Tình huống: Phân bổ tần số vô tuyến (Frequency Assignment)

Bối cảnh: Hệ thống viễn thông cần phân bổ N tần số cho N trạm phát sóng trên lưới. Hai trạm gần nhau (cùng hàng, cùng cột, hoặc cùng đường chéo trên lưới) không được dùng tần số gây nhiễu lẫn nhau. Bài toán tương đương N-Queens.

python

from dataclasses import dataclass


@dataclass
class FrequencyAssignment:
    """Phân bổ tần số cho trạm phát sóng dùng backtracking."""
    grid_size: int
    frequencies: list[str]

    def assign(self) -> list[dict] | None:
        """Tìm phương án phân bổ hợp lệ đầu tiên."""
        board: list[int] = []
        cols: set[int] = set()
        diag1: set[int] = set()
        diag2: set[int] = set()

        def backtrack(row: int) -> bool:
            if row == self.grid_size:
                return True
            for col in range(self.grid_size):
                d1, d2 = row - col, row + col
                if col in cols or d1 in diag1 or d2 in diag2:
                    continue
                board.append(col)
                cols.add(col)
                diag1.add(d1)
                diag2.add(d2)

                if backtrack(row + 1):
                    return True

                board.pop()
                cols.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)
            return False

        if not backtrack(0):
            return None

        return [
            {
                'station': f'S{row}',
                'position': (row, board[row]),
                'frequency': self.frequencies[board[row] % len(self.frequencies)],
            }
            for row in range(self.grid_size)
        ]

    def visualize(self, assignment: list[dict]) -> str:
        """Hiển thị lưới phân bổ."""
        grid = [['.' for _ in range(self.grid_size)]
                for _ in range(self.grid_size)]
        for item in assignment:
            r, c = item['position']
            grid[r][c] = item['frequency'][0]
        return '\n'.join(' '.join(row) for row in grid)


# Sử dụng
fa = FrequencyAssignment(
    grid_size=8,
    frequencies=['F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8']
)
result = fa.assign()
if result:
    print(fa.visualize(result))

Phân tích:

Bài toán thực tế thường có thêm ràng buộc (khoảng cách tối thiểu, tần số ưu tiên) — mở rộng bằng cách thêm điều kiện vào is_valid
Với lưới lớn (N > 20), cần kết hợp heuristic (chọn hàng có ít lựa chọn nhất trước — MRV heuristic)
Đây là ứng dụng trực tiếp của CSP framework, dùng rộng rãi trong AI planning

Sai lầm điển hình

❌ Sai lầm 1: Quên bước Unchoose (quay lui không sạch)

Vấn đề: Đặt quân hậu vào board nhưng không xóa khi quay lui, dẫn đến trạng thái bẩn.

python

# SAI: Thiếu bước undo
def backtrack(row):
    if row == n:
        solutions.append(board[:])
        return
    for col in range(n):
        if is_safe(row, col):
            board[row] = col
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            # ← THIẾU: không xóa col khỏi cols, diag1, diag2!

Tại sao sai: Sau khi thử col=2 ở hàng 3 và quay lui, cột 2 vẫn nằm trong cols → các nhánh khác ở hàng 3 hoặc hàng trước sẽ coi cột 2 là đã chiếm → bỏ qua nghiệm hợp lệ. Bug này đặc biệt khó debug vì chương trình vẫn chạy, chỉ thiếu nghiệm.

python

# ĐÚNG: Luôn undo sau khi quay lui
backtrack(row + 1)

board.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)

❌ Sai lầm 2: Kiểm tra xung đột sai đường chéo

Vấn đề: Dùng row - col == i - board[i] thay vì abs(row - i) == abs(col - board[i]), bỏ sót một chiều đường chéo.

python

# SAI: Chỉ kiểm tra một đường chéo
def is_safe(row, col):
    for i in range(row):
        if board[i] == col or (row - col == i - board[i]):
            return False  # Bỏ sót đường chéo ngược!
    return True

Tại sao sai: row - col == i - board[i] chỉ phát hiện xung đột trên đường chéo ↘. Đường chéo ↗ có đặc trưng row + col == i + board[i]. Thiếu một chiều = quân hậu có thể tấn công nhau mà không bị phát hiện.

python

# ĐÚNG: Kiểm tra cả hai đường chéo
def is_safe(row, col):
    for i in range(row):
        if (board[i] == col or
            abs(board[i] - col) == abs(i - row)):
            return False
    return True
# Hoặc dùng set: d1 = row - col, d2 = row + col

❌ Sai lầm 3: Lưu nghiệm bằng reference thay vì copy

Vấn đề: Append board trực tiếp vào danh sách nghiệm mà không copy.

python

# SAI: Lưu reference, không phải giá trị
if row == n:
    solutions.append(board)  # ← board sẽ bị modify sau đó!
    return

Tại sao sai: board là mutable list. Khi backtrack tiếp, board thay đổi → tất cả "nghiệm" trong solutions đều trỏ đến cùng một list, kết thúc với giá trị cuối cùng (thường là [-1, -1, ..., -1]).

python

# ĐÚNG: Deep copy khi lưu nghiệm
if row == n:
    solutions.append(board[:])   # Slice copy
    # hoặc: solutions.append(list(board))
    return

❌ Sai lầm 4: Duyệt brute-force toàn bộ N^N trường hợp

Vấn đề: Thử đặt quân hậu ở mọi ô trên bàn cờ thay vì chỉ 1 quân mỗi hàng.

Tại sao sai: Với N=12, N^N = 12^12 ≈ 8.9 × 10^12 trường hợp — không chạy nổi. Nhận xét rằng mỗi hàng chỉ có 1 quân giảm xuống N! = 479 triệu, kết hợp pruning giảm còn vài triệu node thực tế.

Under the Hood

Phân tích độ phức tạp

Phiên bản	Time	Space	Kiểm tra xung đột	Ghi chú
Brute-force	O(N^N)	O(N)	O(N)	Thử mọi ô — không dùng
Cơ bản (1 queen/row)	O(N! × N)	O(N)	O(N) per check	Mỗi hàng ≤ N-k lựa chọn
Set-optimized	O(N!)	O(N)	O(1) per check	3 set cho cột + 2 đường chéo
Bitwise	O(N!)	O(N)	O(1) bit ops	Nhanh nhất, giới hạn N ≤ 32/64

Thực tế: Với N=14, phiên bản bitwise chạy trong ~0.5 giây (C++), set-optimized ~2 giây, cơ bản ~15 giây. Pruning tự nhiên của backtracking loại bỏ phần lớn nhánh — số node thực tế thăm ít hơn N! rất nhiều.

Chiến lược cắt tỉa (Pruning)

Chiến lược	Mô tả	Tác động
Constraint propagation	Dùng set/bitmask theo dõi ràng buộc	Giảm kiểm tra từ O(N) xuống O(1)
Early termination	Dừng ngay khi tìm 1 nghiệm (nếu chỉ cần 1)	Bỏ qua toàn bộ cây còn lại
Symmetry breaking	Cố định cột đầu tiên ≤ N/2	Giảm ~50% nhánh (nghiệm đối xứng)
MRV heuristic	Chọn hàng có ít lựa chọn nhất trước	Fail sớm hơn → cắt nhiều hơn
Forward checking	Kiểm tra hàng tiếp có còn lựa chọn không trước khi đệ quy	Tránh đệ quy sâu vô ích

Khi nào dùng Backtracking vs các phương pháp khác

Phương pháp	Khi nào dùng	N-Queens
Backtracking	Tìm tất cả nghiệm, N nhỏ-trung bình	N ≤ 15: tối ưu
CSP Solver (AC-3, MAC)	Bài toán ràng buộc tổng quát, nhiều biến	N ≤ 50: hiệu quả với arc consistency
SAT Solver	Mã hóa thành boolean satisfiability	N ≤ 100: SAT solver hiện đại rất mạnh
Constructive (heuristic)	Chỉ cần 1 nghiệm, N rất lớn	N > 1000: dùng công thức toán học

Kết nối với Constraint Satisfaction Problems (CSP)

N-Queens là một trường hợp đặc biệt của CSP:

text

CSP formulation:
  Biến (Variables): X₁, X₂, ..., Xₙ  (cột của quân hậu ở hàng i)
  Miền giá trị (Domains): Dᵢ = {0, 1, ..., N-1}
  Ràng buộc (Constraints):
    - Xᵢ ≠ Xⱼ                  (khác cột)
    - |Xᵢ - Xⱼ| ≠ |i - j|     (khác đường chéo)
    ∀ i ≠ j

Trong production, CSP framework (như Google OR-Tools, Choco Solver) cho phép mô tả bài toán ở mức cao và tự động áp dụng kỹ thuật cắt tỉa tiên tiến (arc consistency, domain filtering) — hiệu quả hơn viết backtracking thủ công cho bài toán lớn.

Checklist ghi nhớ

✅ Checklist triển khai

Cấu trúc Backtracking

[ ] Mỗi bước: Choose → Explore → Unchoose (luôn undo sạch)
[ ] Base case: row == N → lưu nghiệm (deep copy, không reference)
[ ] Recursive case: thử từng cột hợp lệ cho hàng hiện tại

Kiểm tra xung đột N-Queens

[ ] Cùng cột: board[i] == col
[ ] Đường chéo: |board[i] - col| == |i - row| (cả hai chiều)
[ ] Tối ưu O(1): dùng set cho cols, row - col (diag1), row + col (diag2)

Tối ưu hiệu năng

[ ] Bitwise: cols, diag1, diag2 là bitmask → kiểm tra bằng phép bit
[ ] available & (-available) lấy cột hợp lệ tiếp theo
[ ] Shift diag khi xuống hàng: (diag1 | bit) << 1, (diag2 | bit) >> 1
[ ] Chỉ đếm: bỏ lưu board → nhanh hơn ~30%

Pruning

[ ] Symmetry breaking: cột hàng đầu ≤ N/2
[ ] Early termination nếu chỉ cần 1 nghiệm
[ ] Forward checking: hàng tiếp còn lựa chọn không?

Liên hệ CSP

[ ] N-Queens = CSP với N biến, mỗi biến miền [0, N-1], 2 loại ràng buộc
[ ] Production CSP: dùng solver chuyên dụng (OR-Tools, Choco) thay vì tự viết

Bài tập luyện tập

Bài 1: Đếm nghiệm N-Queens — Foundation

Đề bài: Viết hàm count_solutions(n) chỉ đếm số nghiệm mà không lưu, cho N từ 1 đến 14. So sánh thời gian chạy giữa phiên bản set và phiên bản bitwise.

🧠 Quiz

Câu hỏi: Bài toán N-Queens với N=5 có bao nhiêu nghiệm?

[ ] A. 2
[ ] B. 5
[x] C. 10
[ ] D. 16 Giải thích: N=5 có đúng 10 nghiệm. Quy luật: số nghiệm tăng nhanh theo N nhưng không có công thức đóng — phải dùng thuật toán duyệt.

💡 Gợi ý

Chỉ đếm: không cần lưu board, return 1 thay vì append
Bitwise nhanh hơn đáng kể từ N ≥ 12
Dùng time.time() hoặc chrono::high_resolution_clock để benchmark

✅ Lời giải

python

import time

def count_queens_set(n: int) -> int:
    cols, d1, d2 = set(), set(), set()
    count = 0

    def bt(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            dd1, dd2 = row - col, row + col
            if col in cols or dd1 in d1 or dd2 in d2:
                continue
            cols.add(col); d1.add(dd1); d2.add(dd2)
            bt(row + 1)
            cols.remove(col); d1.remove(dd1); d2.remove(dd2)

    bt(0)
    return count

# Benchmark
for n in range(8, 15):
    start = time.time()
    c = count_queens_set(n)
    elapsed = time.time() - start
    print(f"N={n:2d}: {c:>8d} nghiệm, {elapsed:.3f}s (set)")

Phân tích: Time O(N!), Space O(N). Phiên bản bitwise nhanh hơn ~2-3× cho N ≥ 12 nhờ CPU bit operations.

Bài 2: N-Queens trên bàn cờ có chướng ngại vật — Intermediate

Đề bài: Mở rộng bài toán: một số ô trên bàn cờ bị khóa (obstacles), không thể đặt quân hậu. Cho danh sách obstacles = [(r1, c1), (r2, c2), ...], tìm tất cả nghiệm hợp lệ.

🧠 Quiz

Câu hỏi: Nếu ô (0, 0) bị khóa trên bàn N=4, số nghiệm thay đổi thế nào?

[ ] A. Vẫn 2 nghiệm
[x] B. 1 nghiệm (mất nghiệm bắt đầu ở cột 0 hàng 0)
[ ] C. 0 nghiệm
[ ] D. 3 nghiệm Giải thích: N=4 có 2 nghiệm: [1,3,0,2] và [2,0,3,1]. Nghiệm [2,0,3,1] không đặt quân ở (0,0) nên không bị ảnh hưởng. Nghiệm [1,3,0,2] cũng không đặt ở (0,0). Vậy đáp án phụ thuộc vào nghiệm cụ thể — cần chạy thử.

✅ Lời giải

python

def solve_with_obstacles(n: int, obstacles: set[tuple[int, int]]) -> list[list[int]]:
    solutions = []
    cols, d1, d2 = set(), set(), set()
    board: list[int] = []

    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if (row, col) in obstacles:
                continue
            dd1, dd2 = row - col, row + col
            if col in cols or dd1 in d1 or dd2 in d2:
                continue
            board.append(col)
            cols.add(col); d1.add(dd1); d2.add(dd2)
            backtrack(row + 1)
            board.pop()
            cols.remove(col); d1.remove(dd1); d2.remove(dd2)

    backtrack(0)
    return solutions

# Test
obs = {(0, 0), (2, 2)}
result = solve_with_obstacles(4, obs)
print(f"Nghiệm với obstacles: {len(result)}")
for sol in result:
    print(sol)

Phân tích: Chỉ thêm 1 dòng kiểm tra obstacle — không thay đổi cấu trúc backtracking. Obstacles thực chất là thêm ràng buộc unary vào CSP.

Bài 3: Tối ưu bitwise cho N=15 — Advanced

Đề bài: Triển khai phiên bản bitwise bằng C++ để đếm nghiệm N=15. Target: chạy dưới 5 giây. Áp dụng thêm symmetry breaking (cột hàng đầu ≤ N/2) để tăng tốc thêm ~50%.

💡 Gợi ý

Cố định cột hàng 0 từ 0 đến (N-1)/2, nhân đôi kết quả
Nếu N lẻ, xử lý riêng trường hợp cột hàng 0 = N/2 (không nhân đôi)
Dùng __builtin_ctz (GCC) hoặc _BitScanForward (MSVC) cho trailing zeros

✅ Lời giải

cpp

#include <cstdio>
#include <chrono>

int n, allMask;
long long totalCount;

void solve(int cols, int d1, int d2) {
    if (cols == allMask) {
        totalCount++;
        return;
    }
    int available = allMask & ~(cols | d1 | d2);
    while (available) {
        int bit = available & (-available);
        solve(cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
        available &= available - 1;
    }
}

long long countWithSymmetry(int n_val) {
    n = n_val;
    allMask = (1 << n) - 1;
    totalCount = 0;

    // Cột hàng đầu: 0 đến (n-1)/2 → nhân đôi
    for (int col = 0; col < n / 2; col++) {
        int bit = 1 << col;
        solve(bit, bit << 1, bit >> 1);
    }
    totalCount *= 2;

    // N lẻ: cột giữa không nhân đôi
    if (n % 2 == 1) {
        int bit = 1 << (n / 2);
        solve(bit, bit << 1, bit >> 1);
    }

    return totalCount;
}

int main() {
    for (int i = 8; i <= 15; i++) {
        auto start = std::chrono::high_resolution_clock::now();
        long long result = countWithSymmetry(i);
        auto end = std::chrono::high_resolution_clock::now();
        double elapsed = std::chrono::duration<double>(end - start).count();
        printf("N=%2d: %10lld nghiệm, %.3fs\n", i, result, elapsed);
    }
    return 0;
}
// N=15: 2.279.184 nghiệm, ~1-3 giây tùy CPU

Phân tích: Symmetry breaking giảm ~50% thời gian. Bitwise + symmetry: N=15 chạy trong 1-3 giây thay vì 5-10 giây.

Liên kết học tiếp

Từ khóa glossary: N-Queens, Backtracking, Pruning, Constraint Satisfaction Problem, CSP, Bitwise Optimization, Constraint Propagation, DFS

Tìm kiếm liên quan: bài toán N quân hậu, thuật toán quay lui, cắt tỉa, bài toán ràng buộc, tối ưu bit

N-Queens — Backtracking và nghệ thuật cắt tỉa ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Kiểm tra xung đột — Phiên bản cơ bản O(N) ​

Backtracking cơ bản ​

Tối ưu O(1) với Set — Constraint Propagation ​

Tối ưu Bitwise — Đỉnh cao hiệu năng ​

Template Backtracking tổng quát ​

Thực chiến ​

Tình huống: Phân bổ tần số vô tuyến (Frequency Assignment) ​

Sai lầm điển hình ​

❌ Sai lầm 1: Quên bước Unchoose (quay lui không sạch) ​

❌ Sai lầm 2: Kiểm tra xung đột sai đường chéo ​

❌ Sai lầm 3: Lưu nghiệm bằng reference thay vì copy ​

❌ Sai lầm 4: Duyệt brute-force toàn bộ N^N trường hợp ​

Under the Hood ​

Phân tích độ phức tạp ​

Chiến lược cắt tỉa (Pruning) ​

Khi nào dùng Backtracking vs các phương pháp khác ​

Kết nối với Constraint Satisfaction Problems (CSP) ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Đếm nghiệm N-Queens — Foundation ​

Bài 2: N-Queens trên bàn cờ có chướng ngại vật — Intermediate ​

Bài 3: Tối ưu bitwise cho N=15 — Advanced ​

Liên kết học tiếp ​

N-Queens — Backtracking và nghệ thuật cắt tỉa

Bức tranh tư duy

Cốt lõi kỹ thuật

Kiểm tra xung đột — Phiên bản cơ bản O(N)

Backtracking cơ bản

Tối ưu O(1) với Set — Constraint Propagation

Tối ưu Bitwise — Đỉnh cao hiệu năng

Template Backtracking tổng quát

Thực chiến

Tình huống: Phân bổ tần số vô tuyến (Frequency Assignment)

Sai lầm điển hình

❌ Sai lầm 1: Quên bước Unchoose (quay lui không sạch)

❌ Sai lầm 2: Kiểm tra xung đột sai đường chéo

❌ Sai lầm 3: Lưu nghiệm bằng reference thay vì copy

❌ Sai lầm 4: Duyệt brute-force toàn bộ N^N trường hợp

Under the Hood

Phân tích độ phức tạp

Chiến lược cắt tỉa (Pruning)

Khi nào dùng Backtracking vs các phương pháp khác

Kết nối với Constraint Satisfaction Problems (CSP)

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Đếm nghiệm N-Queens — Foundation

Bài 2: N-Queens trên bàn cờ có chướng ngại vật — Intermediate

Bài 3: Tối ưu bitwise cho N=15 — Advanced

Liên kết học tiếp