POJ 1321 棋盤問題：DFS回溯法完整解析與代碼實現

POJ 1321 棋盤問題：DFS回溯法完整解析與代碼實現

問題描述：在一個n×n（n≤8）的不規則棋盤上放置k個無區別棋子（k≤n），棋盤格子用#標記可用、.標記禁用。要求任意兩棋子不同行、不同列，求所有合法擺放方案數C（C<2³¹）。多組測試數據，-1 -1結束。

一、問題建模與N皇后類比

本質是在受限位置上選擇k個互不衝突的行列對。與N皇后問題同構：

• N皇后：每行必放一個，判斷列、對角線衝突。
• 本題：每行可選放或不放，僅判斷列衝突，且必須落在#格。

採用按行遞歸DFS，狀態包括：當前行cur、已放棋子數m、列佔用標記book[]、方案計數total。

二、DFS遞歸設計

void DFS(int cur) {
    if (m == k) { total++; return; }           // 已放滿k個，方案+1
    if (cur >= n) return;                      // 超出棋盤行數，回溯

    // 選擇在當前行放置棋子
    for (int j = 0; j < n; j++) {
        if (!book[j] && board[cur][j] == '#') { // 列空閒且格子可用
            book[j] = 1; m++;
            DFS(cur + 1);                       // 遞歸下一行
            book[j] = 0; m--;                   // 回溯恢復現場
        }
    }
    // 選擇當前行不放棋子，直接進入下一行
    DFS(cur + 1);
}

三、關鍵點解析

1. 剪枝：cur >= n提前終止；book[] O(1)判斷列衝突。
2. 不放棋子分支：DFS(cur+1)放在循環外，覆蓋「當前行無棋子」的所有情況。
3. 多測試用例處理：主循環讀取n,k，初始化全局變量，調用DFS(0)，輸出total。

四、完整AC代碼（C++，兼容C99）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char board[10][10];
int book[10];
int n, k;
int total, placed;

void DFS(int cur) {
    if (placed == k) { total++; return; }
    if (cur >= n) return;
    for (int j = 0; j < n; j++) {
        if (!book[j] && board[cur][j] == '#') {
            book[j] = 1; placed++;
            DFS(cur + 1);
            book[j] = 0; placed--;
        }
    }
    DFS(cur + 1); // 當前行不放
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> k) {
        if (n == -1 && k == -1) break;
        for (int i = 0; i < n; i++) cin >> board[i];
        memset(book, 0, sizeof(book));
        total = 0; placed = 0;
        DFS(0);
        cout << total << '\n';
    }
    return 0;
}

五、複雜度分析

• 最壞情況：每行最多n個可用格，搜索樹上界 O(n^k)，但n≤8, k≤n，實際運行極快。
• 空間：O(n)遞歸棧 + O(n²)棋盤存儲。

六、舉一反三

• 若棋子有區別：方案數乘以k!。
• 若增加對角線衝突：變為N皇后變體，需額外維護兩個對角線標記數組。
• 大規模棋盤（n>15）可考慮DLX（Dancing Links）精確覆蓋算法。

此題是DFS回溯法處理「帶約束的組合選擇」的經典範例，掌握其狀態定義與回溯模板，可快速解決同類棋盤/放置問題。