Hướng giải của N-Queens

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Quay lui: tại hàng row, thử từng cột c thỏa mãn 3 điều kiện (cột, đường chéo chính, đường chéo phụ đều chưa có hậu). Đánh dấu → đệ quy hàng row+1 → bỏ đánh dấu (quay lui).

Độ phức tạp: \(O(n!)\) với nhánh cận, thực tế chạy nhanh hơn rất nhiều.

C++

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

int n, cnt;
bool col[20], diag1[40], diag2[40];

void solve(int row) {
    if (row > n) { cnt++; return; }
    for (int c = 1; c <= n; c++) {
        int d1 = row + c;
        int d2 = row - c + 20;
        if (col[c] || diag1[d1] || diag2[d2]) continue;
        col[c] = diag1[d1] = diag2[d2] = true;
        solve(row + 1);
        col[c] = diag1[d1] = diag2[d2] = false;
    }
}

int main() {
    cin >> n;
    solve(1);
    cout << cnt << "\n";
    return 0;
}

Python

def solve_nqueens(n):
    col = [False]  n
    diag1 = [False]  (2  n)
    diag2 = [False]  (2 * n)
    cnt = 0

    def backtrack(row):
        nonlocal cnt
        if row == n:
            cnt += 1
            return
        for c in range(n):
            if col[c] or diag1[row + c] or diag2[row - c + n]:
                continue
            col[c] = diag1[row + c] = diag2[row - c + n] = True
            backtrack(row + 1)
            col[c] = diag1[row + c] = diag2[row - c + n] = False

    backtrack(0)
    return cnt

n = int(input())
print(solve_nqueens(n))

Nhận xét

Không có ý kiến tại thời điểm này.