Tổng quan
Bài toán N-Queens (N quân hậu) yêu cầu đặt N quân hậu lên bàn cờ N×N sao cho không quân nào tấn công quân nào — tức không có hai quân nào cùng hàng, cùng cột hay cùng đường chéo. Đây là ví dụ kinh điển để dạy quay lui, vì tầm khống chế rộng của quân hậu buộc thuật toán phải cắt tỉa mạnh các nước đi tồi.
Thuật toán quay lui giải nó bằng cách đặt mỗi hàng một quân hậu và lần lượt thử từng cột. Mỗi khi một vị trí xung đột với quân hậu đã có trên bàn cờ, nhánh đó bị loại bỏ và quá trình tìm kiếm 'quay lui' để thử cột kế tiếp — duyệt không gian nghiệm như một chuyến đi sâu (DFS) trên cây quyết định.
N Quân Hậu hoạt động thế nào?
- Làm theo từng hàng: bắt đầu ở hàng 0 và thử đặt một quân hậu vào một cột nào đó của hàng hiện tại.
- Trước khi đặt, kiểm tra cột được chọn không xung đột với các quân hậu trước đó trên cùng cột hoặc hai đường chéo.
- Nếu vị trí an toàn, đệ quy xuống hàng kế tiếp; quá trình tìm kiếm đi sâu thêm một mức cho mỗi quân hậu được cố định.
- Nếu không cột nào trong hàng hiện tại an toàn, quay lui: gỡ quân hậu trước đó và thử cột khả dụng kế tiếp của nó.
- Khi đặt an toàn được một quân hậu ở hàng cuối cùng, một nghiệm hoàn chỉnh đã được tìm thấy; tiếp tục quay lui để liệt kê mọi nghiệm.
Khi nào nên dùng?
- Dạy kỹ thuật quay lui, cắt tỉa và tìm kiếm theo chiều sâu trên cây quyết định.
- Một bài toán chuẩn để đánh giá các bộ giải ràng buộc (CSP) và kỹ thuật tìm kiếm heuristic.
- Mô hình cho các bài toán sắp đặt thực tế khi các đối tượng không được cùng hàng, cùng cột hay cùng đường chéo — chẳng hạn bố trí tài nguyên không xung đột.
- Minh họa cách cắt tỉa tốt thu nhỏ một không gian tìm kiếm vốn bùng nổ.
Phân tích độ phức tạp
Cách đặt ngây thơ mỗi hàng một quân hậu trên N cột cho một cây tìm kiếm bị chặn bởi O(N!), vì mỗi hàng có ít cột an toàn hơn hàng trước. Việc cắt tỉa theo xung đột cột và đường chéo loại bỏ những cây con khổng lồ, nên chi phí thực tế thấp hơn nhiều so với trường hợp xấu nhất, nhưng cận tiệm cận vẫn xấp xỉ O(N!). Bộ nhớ là O(N) cho ngăn xếp đệ quy và việc theo dõi cột/đường chéo.
Câu hỏi thường gặp
Vì sao đặt mỗi hàng một quân hậu là đủ?
Hai quân hậu trên cùng một hàng luôn tấn công nhau, nên mọi nghiệm hợp lệ đều có đúng một quân hậu mỗi hàng. Cố định mỗi hàng một quân hậu loại bỏ hoàn toàn ràng buộc hàng và thu gọn tìm kiếm về việc chọn một cột cho mỗi hàng.
Kiểm tra đường chéo hoạt động hiệu quả thế nào?
Hai quân hậu cùng đường chéo khi hiệu hoặc tổng của chỉ số hàng và cột bằng nhau. Việc lưu các giá trị (hàng − cột) và (hàng + cột) đã dùng trong tập hợp giúp mỗi lần kiểm tra an toàn chạy O(1) thay vì phải quét cả bàn cờ.
N-Queens có luôn có nghiệm không?
Nghiệm tồn tại với mọi N ngoại trừ N = 2 và N = 3, khi bàn cờ quá nhỏ để tách các quân hậu. Từ N = 4 trở lên, số nghiệm phân biệt tăng nhanh theo N.