八皇后问题——递归与dfs

问题表述为：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解题思路

其实就是简单的dfs或递归，前提是如何判断同一斜线，主对角线上（x，y）（i，j），要是处于同一条对角线则x+y=i+j

如果处于同一条副对角线则 x-y=i-j

递归解法

题目

题目 2047: x皇后问题

时间限制: 1Sec 内存限制: 128MB 提交: 123 解决: 69

题目描述

请输出字典序最小的x皇后问题对应的排列。

(x<=10)

输入

一个数x

输出

包括一行，输出1~x的一个排列，满足x皇后问题的要求。

样例输入

样例输出

1 5 8 6 3 7 2 4

#include <stdio.h>
#include <stdlib.h>
int c[13],totl,n;
int flag;
void search(int cur)  //不能以cur为全局变量，因为回溯回来后cur的值并没有恢复
{
    int i,j;
    if(n==cur)
    {
        for(i=0;i<n;i++)
            printf("%d ",c[i]+1);
        flag=1;
    }
    if(!flag)
      for(i=0;i<n;i++)
        {
            int ok=1;
            c[cur]=i;
            for(j=0;j<cur;j++)
                if(c[j]==c[cur] || j-c[j]==cur-i || j+c[j]==cur+i)
            {
                ok=0;
                break;
            }
            if(ok)
            {
                search(cur+1);
            }
        }

}

int main()
{
    scanf("%d",&n);
    search(0);
    return 0;
}

DFS解法

题目

题目 2087: [蓝桥杯][算法提高VIP]8皇后·改

时间限制: 1Sec 内存限制: 128MB 提交: 623 解决: 342

题目描述

规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。

输入

一个8*8的棋盘。

棋盘上的数字范围0~99

输出

所能得到的最大数字和

样例输入

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48

48 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64

样例输出

260

#include <stdio.h>
#include <stdlib.h>
int map[8][8],c[8],max,total;
int vis[3][17];
void DFS(int n)
{
    int i;
    if(n==8)
    {
        total++;
        int sum=0;
        for(i=0;i<8;i++)
            sum+=map[i][c[i]];
        if(max<sum)
            max=sum;
        return;
    }
    for(i=0;i<8;i++)
    {
        c[n]=i;
        if(!vis[0][i] && !vis[1][i+n] && !vis[2][i-n+8])
        {
            vis[0][i]=vis[1][i+n]=vis[2][i-n+8]=1;
            DFS(n+1);
            vis[0][i]=vis[1][i+n]=vis[2][i-n+8]=0;
        }
    }
}


int main()
{
    int i,j;
    for(i=0;i<8;i++)
        for(j=0;j<8;j++)
        scanf("%d",&map[i][j]);
    DFS(0);
    //printf("%d\n",total);
    printf("%d",max);
    return 0;
}