zstu4026——DFS+回溯—

zstu4026——DFS+回溯——八皇后

Description

在n*n(1 <= n <= 8)的棋盘上放置n个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排。同一纵列，也不允许处在同一与棋盘边框成45o角的斜线上

Input

多组测试数据，每组输入一个整数n

Output

对于每组测试数据输出1行，如果没有可能做到输出No,否则在一行中输出所有皇后的位置，输出时按第1列所在行数，第2列所在行数，...输出（行的起始坐标为1），如果有多种可能，只输出行数最小的那组（即第一列行数最小的，若第一列行数最小的有多种情况，输出第二列行数最小的，依次类推）

Sample Input

3
4

Sample Output

No
2 4 1 3

HINT

对于第2组数据，

大意：DFS以及回溯回溯巨坑。最近在看状态压缩，但是发现皇后问题不满足状态压缩的条件，状态压缩看的是层与层之间的关系，如果对于没一行会影响整体的问题就不能解决，那么只要DFS进行判断当前行与前面已经放的行是否矛盾就行，思想一样，巨坑一点在于函数的类型，输出正确但是int 型的话如果写dfs会wa。。void型就行，这..

皇后问题重在回溯，网上找了好多都没有回溯所有答案的代码，我开二维想要保存所有状态的时候发现有的数会变成0，原来回溯的话是不会到达所有的状态的，只会在当前满足下把这个东西改掉看看是否满足，所以上一个数没有进行赋值，导致了0的出现（数组开始全是零，值是覆盖上去的）

献上两段代码

A代码，只记录字典序最小路径，（全排列第一个就是字典序最小）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int tot,n;
int c[100];
int vis[100];
int path[100];
bool flag;
 
void dfs(int cur)
{
    if(cur == n + 1) {
        tot++;
        for(int i = 1; i <= n ;i++){
            if(i == n)
                printf("%d
",path[i]);
            else
                printf("%d ",path[i]);
        }
        return ;
    }
    if(tot == 2) return ;
    else {
        for(int i = 1; i <= n ;i++){
            c[cur] = i;
            int ok = 1;
            for(int j = 1; j  < cur; j++){
                if(c[cur] == c[j] || cur - c[cur] == j - c[j] || cur + c[cur] == j + c[j]){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                path[cur] = i;
                dfs(cur+1); 
                }
            }
    }
}
int main()
{
 while(~scanf("%d",&n)){
    tot = 1;
    dfs(1);
    flag = false;
    memset(c,0,sizeof(c));
    memset(path,0,sizeof(path));
    if(tot == 1)
        printf("No
");
 
 }
 return 0;
}

回溯所有情况代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int tot,n;
int c[100];
int vis[100];
int path[100][10];

void dfs(int cur)
{
    if(cur == n + 1) {
        for(int i = 1; i <= n ;i++){
            if(i == n)
                printf("%d
",path[tot][i]);
            else 
                printf("%d ",path[tot][i]);
        }
        tot++;
        for (int i = 1 ; i <= n ; i ++)
           path[tot][i] = path[tot - 1][i] ;
        return ;
    }
    else {
        for(int i = 1; i <= n ;i++){
            c[cur] = i;
            int ok = 1;
            for(int j = 1; j  < cur; j++){
                if(c[cur] == c[j] || cur - c[cur] == j - c[j] || cur + c[cur] == j + c[j]){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                path[tot][cur] = i;
                dfs(cur+1); 
                }
            }
    }
}
int main()
{
 while(~scanf("%d",&n)){
    tot = 1;
    dfs(1);
    printf("%d
",tot-1);
    memset(c,0,sizeof(c));
    memset(path,0,sizeof(path));
    if(tot == 1)
        printf("No
");

 }
 return 0;
}