算法学习之路|N皇后问题-阿里云开发者社区

开发者社区> 人工智能> 正文

算法学习之路|N皇后问题

简介: N皇后问题,在棋盘上放n个皇后,要求互相之间不能攻击,求问有多少种情况

N皇后问题,在棋盘上放n个皇后,要求互相之间不能攻击,求问有多少种情况
输入格式
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
输出格式
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
输入样例:
1
8
5
0
输出样例:
1
92
10

八皇后问题的拓展,回溯法

#include<stdio.h>  
#include<string.h>  
  
int map[11][11],n,cnt;  
bool pan(int x,int y)  
{  
    int i,j;  
    for(i=0;i<y;i++)  
        if(map[x][i])  
            return false;  
    for(i=x-1,j=y-1;i>=0&&j>=0;i--,j--)  
        if(map[i][j])  
            return false;  
    for(i=x+1,j=y-1;i<n&&j>=0;i++,j--)  
        if(map[i][j])  
            return false;  
    return true;  
}  
  
void dfs(int size)  
{  
    if(size==n)  
        cnt++;  
    for(int i=0;i<n;i++)  
    {  
        if(!map[i][size]&&pan(i,size))  
        {  
            map[i][size]=1;  
            dfs(size+1);  
            map[i][size]=0;  
        }  
    }  
    return ;  
}  
  
int main()  
{  
    int i;  
    int result[11];  
    for(i=0;i<11;i++)  
    {  
        memset(map,0,sizeof(map));  
        n=i+1;  
        cnt=0;  
        dfs(0);  
        result[i]=cnt;  
    }  
    while(~scanf("%d",&n)&&n)  
    {  
        printf("%d\n",result[n-1]);  
    }  
    return 0;  
}  

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章