八皇后问题 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 条评论
登录 后参与评论

相关文章

来自专栏大内老A

如何让普通变量也支持事务回滚?

有一次和人谈起关于事务的话题,谈到怎样的资源才能事务型资源。除了我们经常使用的数据库、消息队列、事务型文件系统(TxF)以及事务性注册表(TxR)等,还有那些资...

1598
来自专栏JackieZheng

RabbitMQ入门-Routing直连模式

Hello World模式,告诉我们如何一对一发送和接收消息; Work模式,告诉我们如何多管齐下高效的消费消息; Publish/Subscribe模式,告...

24710
来自专栏Java3y

【不用框架】文件上传和下载

什么是文件上传? 文件上传就是把用户的信息保存起来。 为什么需要文件上传? 在用户注册的时候,可能需要用户提交照片。那么这张照片就应该要进行保存。 上传组件(工...

5234
来自专栏分布式系统进阶

Kafka集群Metadata管理Kafka源码分析-汇总

可以看到是调用了ReplicaManager.maybeUpdateMetadataCache方法, 里面又会调用到MetadataCache.updateCa...

1652
来自专栏Java 技术分享

Struts2 之 modelDriven & prepare 拦截器详解

3617
来自专栏Java编程技术

使用数据库悲观锁实现不可重入的分布式锁

在同一个jvm进程中时,可以使用JUC提供的一些锁来解决多个线程竞争同一个共享资源时候的线程安全问题,但是当多个不同机器上的不同jvm进程共同竞争同一个共享资源...

651
来自专栏向前进

【笔记】HybridApp中使用Promise化的JS-Bridge

背景: HybridApp,前端采用JS-bridge的方式调用Native的接口,如获取设备信息、拍照、人脸识别等 前端封装了调用库,每次调用Native接口...

3344
来自专栏FD的专栏

一步步理解python的异步IO

看到越来越多的大佬都在使用python的异步IO,协程等概念来实现高效的IO处理过程,可是我对这些概念还不太懂,就学习了一下。 因为是初学者,在理解上有很多不到...

1172
来自专栏IMWeb前端团队

通过ffi在node.js中调用动态链接库(.so/.dll文件)

? 概述 为什么要在node.js中调用动态链接库 由于腾讯体系下的许多公共的后台服务(L5, CKV, msgQ等)已经有了非常成熟的C/C++编写的API...

4187
来自专栏Python自动化测试

测试驱动之xml文件的处理

Xml是可扩展标记语言,关于xml的技术本人这里不在介绍,感兴趣的同学可以去w3c看看详细的资料,这里,我仅仅介绍的是如何获取xml文档结构中的...

1063

扫码关注云+社区