说明:
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);
}
}