【DFS】hdu 2553 N皇后问题

题目描述：

http://acm.hdu.edu.cn/showproblem.php?pid=2553

 

思路：

采用打表的方式来做这道题。

对于 N 皇后问题，具体解法是：从第 0 列开始，逐行放置皇后。

check() 函数用来回溯剪枝。

 

代码：

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

int num[11] = {0};
int n;
int cols[11];

bool check(int r, int c){
    //检查 0 ~ r-1 行皇后的放置位置 
    for(int i=0;i<r;i++){
        //cols[i] 记录的是第 i 行皇后的位置信息 
        if(cols[i] == c || abs(r-i) == abs(c-cols[i])){
            return false;
        }
    }
    return true;
}

void dfs(int r){
    //0~n-1 行皇后放置完毕 
    if(r == n){
        num[n]++;
        return;
    }
    
    //从第 0 列开始，尝试放置皇后 
    for(int i=0;i<n;i++){
        if(check(r, i)){
            //放置皇后，记录信息
            cols[r] = i;
            //放置下一行 
            dfs(r+1);
        }
    }
}

int main(){
    for(int i=1;i<=10;i++){
        memset(cols, -1, sizeof(cols));
        n = i;
        dfs(0);
    }
    while(scanf("%d", &n) && n){
        printf("%d
", num[n]);
    }
}