🎯 Mục tiêu bài học

• Hiểu cách kiểm tra ràng buộc khi đặt hậu (Q) lên bàn cờ n×n.
• Biết cắt tỉa nhánh sai thay vì thử tất cả mọi cách mù quáng.

📘 Bài toán N-Queens là gì?

Ta cần đặt n quân Hậu sao cho:

• Không có 2 hậu nào cùng hàng.
• Không có 2 hậu nào cùng cột.
• Không có 2 hậu nào cùng chéo.

Mỗi lời giải là một cách sắp xếp hợp lệ toàn bộ bàn cờ.

💻 Ý tưởng giải bằng quay lui

1. Đặt hậu từng hàng một (row 0, row 1, ...).
2. Ở mỗi hàng, thử đặt vào từng cột có thể.
3. Nếu hợp lệ thì đi tiếp sang hàng sau, nếu không thì bỏ (backtrack).

C++

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> col, diag1, diag2, pos;
int solutions = 0;

void backtrack(int row){
    if(row==n){
        solutions++;
        for(int r=0;r<n;r++){
            for(int c=0;c<n;c++){
                cout << (pos[r]==c ? "Q" : ".");
            }
            cout << "\n";
        }
        cout << "\n";
        return;
    }
    for(int c=0;c<n;c++){
        if(!col[c] && !diag1[row+c] && !diag2[row-c+n-1]){
            col[c]=diag1[row+c]=diag2[row-c+n-1]=1;
            pos[row]=c;
            backtrack(row+1);
            col[c]=diag1[row+c]=diag2[row-c+n-1]=0;
        }
    }
}

int main(){
    cin >> n;
    col.assign(n,0);
    diag1.assign(2*n,0);
    diag2.assign(2*n,0);
    pos.assign(n,-1);
    backtrack(0);
    cerr << "Total solutions: " << solutions << "\n";
}

Python

n = int(input())

col   = [False]*n
diag1 = [False]*(2*n)
diag2 = [False]*(2*n)
pos   = [-1]*n
solutions = 0

def backtrack(row):
    global solutions
    if row == n:
        solutions += 1
        for r in range(n):
            line = "".join("Q" if pos[r]==c else "." for c in range(n))
            print(line)
        print()
        return
    for c in range(n):
        if not col[c] and not diag1[row+c] and not diag2[row-c+n-1]:
            col[c] = diag1[row+c] = diag2[row-c+n-1] = True
            pos[row] = c
            backtrack(row+1)
            col[c] = diag1[row+c] = diag2[row-c+n-1] = False

backtrack(0)
print("Total solutions:", solutions)

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

1. In ra tổng số lời giải của N-Queens với n cho trước.
2. Chỉ in ra 1 lời giải hợp lệ đầu tiên (dừng sớm).
3. Biểu diễn lời giải không phải bằng bảng Q/. mà bằng mảng vị trí cột, ví dụ: [1, 3, 0, 2].

# Trong backtrack(row):
#   nếu đã tìm thấy lời giải đầu tiên thì return True để dừng luôn
#   nếu không thì tiếp tục thử.
# Đây là tối ưu hóa thời gian khi chỉ cần 1 lời giải.