八皇后问题 dfs/递归

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
int ans=0;
int vis_Q[maxn];
int book_col[maxn];
int n;
bool judge(int r,int c)//能否放在r行c列判断
{
    if(book_col[c]==1) return false;//如果这列已经被占用,不行
    for(int i=1;i<r;i++)
    {
        if(abs(c-vis_Q[i])==abs(r-i)) return false;//如果和前面已将摆放好的在同一个对角线上,也不行
    }
    vis_Q[r]=c;//都不冲突,就让第r行标记为c,代表第r行的皇后放在c位置
    return true;
}
void show_Q()//output
{
    ans++;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis_Q[i]==j)
            cout<<"Q ";
            else
            cout<<". ";
        }
        cout<<endl;
    }
    cout<<"_______________"<<endl;
}
void dfs_Q(int r)//核心代码,递归搜索,dfs
{
    if(r==n+1)
        show_Q();
    for(int j=1;j<=n;j++)
    {
        if(judge(r,j))
        {
            book_col[j]=1;
            dfs_Q(r+1);
            book_col[j]=0;
        }
    }
    return;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
       memset(book_col,0,sizeof(book_col));
       memset(vis_Q,0,sizeof(vis_Q));
       vis_Q[1]=i;
       book_col[i]=1;
       dfs_Q(2);
    }
    cout<<ans<<endl;//解的数目
    return 0;
}

  需要了解下西洋棋的基本规则。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端儿

理解运用JS的闭包、高阶函数、柯里化

JS的闭包,是一个谈论得比较多的话题了,不过细细想来,有些人还是理不清闭包的概念定义以及相关的特性。

712
来自专栏专注研发

lambda表达式

682
来自专栏前端知识分享

第200天:js---常用string原型扩展

543
来自专栏Java成长之路

动态代理详解

代理 是常用的基本设计模式之一,在某些情况下,一个客户不想或者不能直接引用一个对 象,此时可以通过一个称之为“代理”的第三者来实现 间接引用。代理对象可以在客户...

571
来自专栏Netkiller

Spring data mongodb @Document定义Enum/List/Map数据结构

本文节选自《Netkiller Java 手札》 7.2.2. @Document 复杂的 @Document 数据类型定义 package cn.netk...

3598
来自专栏数据结构与算法

P1865 A % B Problem

题目背景 题目名称是吸引你点进来的 实际上该题还是很水的 题目描述 区间质数个数 输入输出格式 输入格式: 一行两个整数 询问次数n,范围m 接下来n行...

2959
来自专栏余林丰

Effective Java通俗理解(上)

  这篇博客是Java经典书籍《Effective Java(第二版)》的读书笔记,此书共有78条关于编写高质量Java代码的建议,我会试着逐一对其进行更为通俗...

2237
来自专栏乐沙弥的世界

MongoDB 数组元素增删改

584
来自专栏Java呓语

原型模式(克隆生成对象)

暂时抛弃掉之前的上下文(机器人 Samu与主人 Alice),创建型模式总不能很好对应机器人的上下文。

876
来自专栏专注 Java 基础分享

详解Java动态代理机制

     之前介绍的反射和注解都是Java中的动态特性,还有即将介绍的动态代理也是Java中的一个动态特性。这些动态特性使得我们的程序很灵活。动态代理是面向AO...

1685

扫码关注云+社区