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

相关文章

来自专栏闪电gogogo的专栏

Python初学——多进程Multiprocessing

1.1 什么是 Multiprocessing 多线程在同一时间只能处理一个任务。 可把任务平均分配给每个核,而每个核具有自己的运算空间。 1.2 添加进程 P...

2638
来自专栏一枝花算不算浪漫

[Java 缓存] Java Cache之 Guava Cache的简单应用.

3586
来自专栏学海无涯

Java Web之SpringMVC 进行数据回显

基本介绍 数据回显:模型数据导向视图(模型数据 ---> Controller ---> 视图) 说明:SpringMVC在调用方法前会创建一个隐含的模型对象...

3145
来自专栏散尽浮华

Python-面向对像及其他

其他相关 1、isinstance(obj,cls)       检查是否obj是类cls的对象 # 针对变量 n = 123 s = "123" print...

1859
来自专栏IT进修之路

原 JAVA懒开发:lombok的使用

1792
来自专栏逆向技术

逆向知识第八讲,if语句在汇编中表达的方式

           逆向知识第八讲,if语句在汇编中表达的方式 一丶if else的最简单情况还原(无分支情况) 高级代码: #include "stdafx...

2256
来自专栏Android 开发学习

python 遍历toast msg文本背景简易语法介绍1. 查找目录下所有java文件查找Java文件中的Toast在对应行中找出对应的id使用id在String中查找对应的toast提示信息。

1544
来自专栏刘晓杰

Glide中request的调用和管理

3407
来自专栏代码GG之家

Dagger2图文完全教程

没有更多开场白,直接说下我对它的理解。 Dagger2 是一个Android依赖注入框架。而android开发当前非常流行的非MVP模式莫属了,Dagger2的...

1929
来自专栏刘望舒

探究RemoteViews的作用和原理

RmoteViews是一个能显示在其他进程的视图。同样也提供了一些基本的操作方法来修改视图的内容。

741

扫码关注云+社区