一、什么是N皇后问题？
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。
二、算法
1、将第一个皇后放置在第一行的第一个空格里
2、对于第二行，从第一个空格开始寻找不与第一行的皇后冲突的空格。找到的第一个不冲突的空格是第2个。
3、对于第三行，这时已经找不到与之前放置的两个皇后不冲突的空格了。把当前行恢复初始状态，返回到上一行。
4、在当前行皇后所占的空格之后寻找一个不与之前皇后冲突的位置。有两种情况，如果找打了则把当前行的皇后移动到该位置，然后处理下一行。如果直到最后当前行的最后一个空格也没有找合适的位置，则把当前行恢复初始状态，继续回溯到上一行。
5、把最后一个皇后成功安置在最后一行，代表找到了一种可行解。返回步骤4。
6、当需要回溯到第0行（表格之外）的时候代表已经找遍了所有可能的可行解。
三、4皇后解法图解
第一步
| Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
第二步
| Q |
|
|
|
|
|
|
Q |
|
|
|
|
|
|
|
|
|
|
|
第三步 发现第三行没有合适的位置了，于是将第二行皇后的位置移到下一个不冲突的位置
| Q |
|
|
|
|
|
|
|
Q |
|
|
|
|
|
|
|
|
|
|
第四步
| Q |
|
|
|
|
|
|
|
Q |
|
|
Q |
|
|
|
|
|
|
|
第五步 发现第四行没有合适的位置了，于是回溯到第二行，又发现第二行到头了，于是继续回溯到第一行。把第一行皇后的位置后移。
|
|
Q |
|
|
|
|
|
|
Q |
|
|
|
|
|
|
|
|
|
|
第六步
|
|
Q |
|
|
|
|
|
|
Q |
| Q |
|
|
|
|
|
|
|
|
第七步
|
|
Q |
|
|
|
|
|
|
Q |
| Q |
|
|
|
|
|
|
Q |
|
四、程序
#include "stdafx.h"
#include <iostream>
using namespace std;
int n=0;
int arr[100];
bool place(int i) //判断能不能放置第N个皇后
{
for(int j=0;j<i;j++)
if(arr[j]==arr[i]||abs(arr[j]-arr[i])==abs(j-i))
return false;
return true;
}
int queue(int n)
{
int solution=0;
for(int i=0;i<n;i++)
arr[i]=0;
int k=1;
while(k>=0)
{
while(!place(k)&&k<n) //放置第N个皇后
arr[k]=arr[k]+1;
if(arr[k]<n&&k==n-1) //排列完成一次
{
solution++;
arr[k]=arr[k]+1;
}
else if(arr[k]<n&&k<n-1) //排列完一个皇后
{
k=k+1;
arr[k]=-1;
}
else //当前皇后没有合适的位置
{
arr[k]=0;
k=k-1;
arr[k]=arr[k]+1;
}
}
return solution;
}
void main()
{
while(1)
{
cout<<"Please input the queue number:"<<endl;
cin>>n;
if(n==-1)
break;
int x=queue(n);
cout<<x<<" solution(s)"<<endl;
}
system("pause");
}n solution(n)
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352
以上结果可以作为测试案例验证程序。
文章浏览阅读4.1w次，点赞122次，收藏88次。上一章节我们利用了事务机制进行了数据的写入（执行了 INSERT 语句）。"增、删、改、查"这四个操作，只做了 "查询" 与 "添加"，"删除" 与 "修改" 的实验还没有做。先别着急，接下来我们先学习一下 "连接池技术"，然后再去练习 "删除" 与 "修改" 的实验也不迟。............
文章浏览阅读2.5k次。打开命令窗口，执行pip install word2vec，如图：ERROR: Command errored out with exit status 1: command: 'e:\python\python.exe' -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\\TEMP\\pip-install-x..._word2vec安装失败
文章浏览阅读6.1k次，点赞6次，收藏16次。自己在做项目的时候，在jsp页面通。过${xxx}获取不到值，困扰了自己好久。自己jsp页面如下：<input id="uuid" type="hidden" value="${user.uId}" name="userId"/>controller如下： @RequestMapping(value = "/checkLogin",method = Reques_在jsp文件中requestscoped读取不到元素
文章浏览阅读531次。NSString *urlStr = @"http://localhost:8080/datainterface/interfacename"; NSMutableURLRequest *jsonRequest = [[NSMutableURLRequest alloc] init]; [jsonRequest setURL:[NSURL URLWithString:ur_oc post form
文章浏览阅读915次。如果要在同一台KMS服务器上激活多个产品(如Office 2010和Windows 7)，则需要同时安装并激活Windows KMS主机密钥。例如，当用户A安装完Office 2010后，6、KMS激活之后并非永久有效，KMS客户端必需在180之内再次连接到KMS服务器上对产品进行激活。1、Office 2007的批量授权版本是不需要激活，安装完成便可以正常使用的，但从Office 2010开始，激活的180天之内，KMS 客户端必需主动联系到KMS服务器进行重新激活，激活完成后可以再使用180天。_kms csdn
文章浏览阅读1w次。当前的工作用到了TFS，从没玩过，赶紧补习下，推荐下载地址：http://download.csdn.net/detail/wujiandao/4128032 Getting Started with Visual Studio Application Lifecycle ManagementVisual Studio 2010Other Ver_microsoft visual studio team foundation server 2010
文章浏览阅读6.2k次，点赞7次，收藏33次。知识图谱？有哪些典型应用？01 知识图谱背景1. 什么是知识2. 什么是图谱02 知识图谱的定义03 知识图谱的典型应用1. 医疗领域2. 金融投资领域3. 政府管理和安全领域4. 电商领域5. 聊天机器人领域01 知识图谱背景在给出知识图谱的定义之前，我们先分开讨论一下什么是知识，什么是图谱。1. 什么是知识首先看一下什么是知识。有读者可能会提出这样的问题，在大数据时代，人类拥有海量的数据，这是不是代表人类可以随时随地利用无穷无尽的知识呢？答案是否定的。知识是人类在实践中认识客观世界（包括人类_知识图谱的典型应用包括，传统搜索机器问答社交网络
文章浏览阅读4.1k次。今天很多工程师都使用不同的CAD软件，以至于产生了不同格式的CAD格式文件，因此所有人都难以互换，其中主流的CAD软件有：PTC Creo，Siemens NX，CATIA，SolidWorks，Autodesk Inventor等，如果要向下游进行传递或是需要在线预览下车间等，则需要统一轻量化处理后方可传递或是在线预览，经过近三年的时间探索，目前实现了几种主流CAD文件的轻量化处理，处理后的文件可以在线预览或是传递给下游系统，如有需要可以扫描下方且交流，其中sldprt文件在线预览如下：..._solidworks在线预览
文章浏览阅读398次。在网站中,我们经常看到每当我们准备登陆时,网页询问我们是否保存用户名和密码,以便下次登陆时不用再次输入。诸如此类的功能如何实现哪？经过两天的研究，终于有了收获！现将我的经验与大家分享。在网页中记录用户的信息通常有如下几种方式：Session、Cookie、以及.Net环境下的ViewState等。比较起来，Session将用户的信息暂存在内存中，除非用户关闭网页，否则信息将一直有效。所以，用Ses..._cookie无法使用时如何保存用户信息
文章浏览阅读559次。在刚刚接触PHP时，曾遇到过这样一个坑，就是在PHP7.0版本中无法使用mysql连接数据库，当时只好降级PHP版本来通过mysql来连接数据库(很无奈的做法)，但作为一个与时俱进的程序员，必须学习新的技术才能保持竞争力，所以今天就介绍一下利用PDO_mysql连接MySQL，这也是PHP新版本推荐使用的一个扩展。PDO_mysql操作在php.ini中开启PDO_mysql扩展//取消注释ext..._pat pdo_mysql
文章浏览阅读1.8k次。第一种是数组的值改变，在改变数组的值的时候使用索引值去更改某一项，这样视图不会实时更新，这种情况是因为直接通过索引去改变数组，vue对象监听不到他的变化，所以没有更新；使用vue的变异方法pop(),push(),shift(),unshift(),revese(),sort(),splice()等方法也会触发视图更新。1.利用vue.set(object,key,val)：例：vue.set(vm.obj,'k1','v1');2.利用Object.assign({},this.obj)创建新对象；_vue改变数组或对象视图没更新
文章浏览阅读654次。点击上方“芋道源码”，选择“设为星标”管她前浪，还是后浪？能浪的浪，才是好浪！每天 10:33更新文章，每天掉亿点点头发...源码精品专栏原创 | Java 2021超神之路，很肝~中文详细注释的开源项目RPC 框架 Dubbo 源码解析网络应用框架 Netty 源码解析消息中间件 RocketMQ 源码解析数据库中间件 Sharding-JDBC 和 MyCAT 源码解析作业调度中间件 E..._系统级的优化