N皇后
说明：
N皇后问题是一个以国际象棋为背景的问题：如何能够在N×N的国际象棋棋盘上放置N个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
解法：
N个皇后中任意两个不能处在同一行，所以每个皇后必须占据一行，及一列。我们采用回溯法的思想去解。首先摆放好第0行皇后的位置，然后在不冲突的情况下摆放第1行皇后的位置。到第j行时，如果没有一个位置可以无冲突的摆放皇后，则回溯到第j-1行，寻找第j-1行皇后的下一个可以摆放的位置。
总结一下，用回溯法解决N皇后问题的步骤：
（1）从第0列开始，为皇后找到安全位置，然后跳到下一列.
（2）如果在第n列出现死胡同，如果该列为第0列，棋局失败，否则后退到上一列，再进行回溯.
（3）如果在第8列上找到了安全位置，则棋局成功.
C：
#include <bits/stdc++.h>
using namespace std;
int N,sum = 0;
int queen[100];//queen[i]的值表示第i行放第queen[i]列
void nqueen(int k)
{
int j;
if(k == N)//如果所有的皇后都放好了就输出
{
for(int i = 0;i < N;i++)
cout<<queen[i] + 1<<" ";//我是从第0行开始放，所以输出就要+1
cout<<endl;
sum++;//每放置一种，就加一种方法
return;
}
for(int i = 0;i < N;i++)//枚举N列
{
for(j = 0;j < k;j++)//前k行的皇后
{//第j行的皇后的列是queen[j]，不能和我当前的列相同
if(queen[j] == i || abs(j - k) == abs(queen[j] - i))
//也不能是对角线
break;
}
if(k == j)
{//如果情况都满足，j就会等于k，这时就保存列号，并且进入下一行枚举
queen[j] = i;
nqueen(k+1);
}//如果下一行的皇后没有正确的位置放，就会回溯，继续循环上一行的皇后位置
}
}
int main()
{
cin>>N;
nqueen(0);//从第0行开始放皇后
cout<<sum;//输出一共有多少种放法
return 0;
}Java：
public class Nqueen{
static int[] queen = new int[100];
static int N,sum = 0;
public static void nqueen(int k){
int j;
if(k == N){
for(int i = 0;i < N;i++)
System.out.print(queen[i] + 1 + " ");
System.out.println();
sum++;
return;
}
for(int i = 0;i < N;i++){
for(j = 0; j < k;j++){
if(queen[j] == i || abs(queen[j],i) == abs(k,j))
break;
}
if(j == k){
queen[j] = i;
nqueen(k+1);
}
}
}
public static int abs(int i,int j){
if(i > j)
return i - j;
else
return j - i;
}
public static void main(String[] args){
N = Integer.parseInt(args[0]);
nqueen(0);
System.out.println(sum);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-03-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读