怎样做展会推广网站/宁波网站建设优化企业
皇后问题
First question：八皇后问题
在棋盘上放置8个皇后，使得它们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解，如图所示。
先上代码：
#include<bits/stdc++.h>
using namespace std;
int tot=0, n, C[5];
void search(int cur)
{if(cur==n) {tot++;return;}//每行每列只有一个皇后 for(int i=0; i<n; i++){int ok=1;C[cur]=i; //尝试把第cur行的皇后放在第i列 C[y]=xfor(int j=0; j<cur; j++) //检查是否和前面的皇后冲突 { //检查纵向 检查斜向 巧妙 //不用检查横向，因为皇后是逐行放置if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]){ //y-x x+yok=0;break;}}if(ok)search(cur+1); //如果合法，则继续递归 }
}int main()
{n=5;search(0);cout<<tot<<endl;return 0;
}
注意：皇后是逐行放置的，皇后肯定不会横向攻击（因为横向不可能有皇后），因此只需检查是否纵向和斜向攻击即可。
条件“cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]”用来判断皇后（cur,C[cur]）和（j,C[j]）是否在同一条对角线上。
（神秘的操作）其原理可以用下图解释。
（a）格子（x,y）的y-x值标识了主对角线
（b）格子（x,y）的x+y值标识了副对角线
在“八皇后”代码中并没有用到回溯的方法，但是我们可以模仿“八皇后”的代码，写出接下来的这道题——2n皇后问题
Second question：2n皇后问题
问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
我采用的方法是用一个类似棋盘的二维数组qp[10][10]来模拟全局的状态。在棋盘上，任意同色的皇后任都不在同一行、同一列或同一条对角线上。
换句话说，黑白皇后之间没有影响，要考虑2个问题：
1、该位置有没有被占或不能下？
2、会不会与同色皇后冲突？
如果你有做过八皇后的题目，那你可以直接套用在这个2n皇后的题目，只要添加回溯即可。
如何添加回溯？
想象一下，你要下一步棋，现在你有很多个下棋位置可以选择。
第一种情况：你下了几步后发现输了，你想悔棋。于是你就把棋局回到你一开始要下的棋局，选择其他可能赢的下棋位置。
第二种情况：你下了几步后发现赢了，你获胜的可能多了一种，但是你觉得赢的方式有很多种。于是你就把棋局回到你一开始要下的棋局，选择其他可能赢的下棋位置。
#include<bits/stdc++.h>
using namespace std;
long long tot=0, n, tot1=0;
int C[10], C1[10], qp[10][10];void black(int cur)
{if(cur==n) //放好黑皇后、白皇后 {tot++;return;}for(int i=0; i<n; i++){int ok=1, j;C1[cur]=i;for(j=0; j<cur; j++){if(C1[cur]==C1[j]||cur-C1[cur]==j-C1[j]||cur+C1[cur]==j+C1[j]){ ok=0;break;}}if(ok&&qp[cur][i]==1){qp[cur][i]=2;black(cur+1); qp[cur][i]=1;}}
}void white(int cur)
{if(cur==n) //白皇后放置完毕 {black(0);//开始放黑皇后 for(int i=0; i<n; i++)cout<<C[i]<<" ";return;}for(int i=0; i<n; i++){int ok=1, j;C[cur]=i; //尝试把第cur行的皇后放在第i列 （对应讲解图C[y]=x） for(j=0; j<cur; j++){//不得不说这里的一维数组用得很巧妙，甚至有点神秘//判断同列有没有同色皇后、斜边有没有同色皇后//由于该判断有点抽象，具体请看上面原理图 if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]){ ok=0;break;}}if(ok&&qp[cur][i]==1)//判断该位置是否符合条件、是否为空 {qp[cur][i]=2;white(cur+1); qp[cur][i]=1; //回溯： } //想象一下，你要下一步棋，现在你有很多个选择 } //你下了几步后发现输了，你想悔棋
} //于是你就把棋局回到你一开始要下的棋局 //选择其他可能赢的选择
int main()
{cin>>n;for(int i=0; i<n; i++)for(int j=0; j<n; j++)cin>>qp[i][j];white(0); //先放白皇后 cout<<tot<<endl;return 0;
}
希望能够将自己的一些学习经验分享给有需要的人。
我是小郑，一个坚持不懈的小白。
参考资料：《算法竞赛入门经典》