问题描述：
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。给出所有可行解。
算法分析：
注：i-j=k-l 或 i+j=k+l 说明2个皇后在对角线上
源代码：
1.Java实现——递归回溯
import java.util.*;
public class Queen {
private char[][] matrix; //输出棋盘的摆放
private int size; //皇后个数
private int[] position; //每个皇后的摆放位置
private int result; //统计解的个数
public int getResult() {
return result;
}
public Queen(int size) {
this.size = size;
matrix = new char[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix[i][j] = 'x';
}
}
position = new int[size];
}
private void printMatrix() {
System.out.printf("---- sulution %d ----\n", result);
for (int i = 0; i < size; i++) {
System.out.print("{");
for (int j = 0; j < size - 1; j++)
System.out.print(matrix[i][j] + " ");
System.out.print(matrix[i][size - 1]);
System.out.println("}");
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (position[i] == position[row]) {
return false;
}
if (Math.abs(position[i] - position[row]) == row - i) {
return false;
}
}
return true;
}
public void trial(int row) {
for (int i = 0; i < size; i++) {
matrix[row][i] = '.';
position[row] = i; //保存二维数组每一维的一个位置用一位数组的下标和元素值就能完成，
if (isValid(row, position[row])) {
if (row < size - 1) {
trial(row + 1);
}
else { //即一般算法中if(t>n)……的情况，前面的for巧妙地隐含了t<n的情况
result++;
printMatrix();
}
}
matrix[row][i] = 'x';
}
}
public static void main(String[] args) {
Queen test = new Queen(8);
test.trial(0);
System.out.printf("result is: %d", test.getResult());
}
}
2.迭代回溯
import java.util.*;
public class NQueen
{
static int sum=0;
//用迭代回溯法设计函数Queen(n)求解
public static boolean Place(int x[],int k)//考察皇后k放置在x[k]列是否发生冲突
{
for(int i=1; i<k; i++)
if (x[k]==x[i]|| k-i==Math.abs(x[k]-x[i]))
return false;
return true;
}
public static void Queen(int n)
{
int x[]=new int[n+1];
for (int i=1; i<=n; i++)//初始化
x[i]=0;
int k=1;
while (k>=1)
{
x[k]++;//在下一列放置第k个皇后
while (x[k]<=n&&!Place(x,k))
x[k]++; //直到找到一个可以放置的位置，超过n则回溯
if (x[k]<=n && k==n) //得到一个解，输出
{
sum++;
System.out.println("第"+sum+"个解是:");
for (int i=1; i<=n; i++)
System.out.print("("+i+","+x[i]+")"+" ");
System.out.println();
}
else if (x[k]<=n && k<n) //放置下一个皇后
k=k+1;
else //没有合适位置，重置x[k]，回溯
{
x[k]=0;
k=k-1;
}
}
}
public static void main(String[] args)
{
//Scanner in=new Scanner(System.in); //从键盘获取输入的方法
//System.out.println("Please enter the number of queen you want(请输入你要求解的皇后的个数)");
//int n=in.nextInt();
int n=8;
double startTime=System.currentTimeMillis();//startTime 统计运行时间的方法
Queen(n);
double endTime=System.currentTimeMillis();//endTime
System.out.println("共有"+sum+"个解");
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
}
3.C++版八皇后代码
#include<iostream>
#include<cmath>
using namespace std;
int x[9];
void print(){
for(int i = 1; i <= 8; i++)
cout << x[i] << " ";
cout << endl;
}
bool canPlace(int k){
for(int i = 1; i < k; i++){
//判断处于同一列或同一斜线
if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i]))
return false;
}
return true;
}
void queen(int i){
if(i > 8){
print();
return;
}
for(int j = 1; j <= 8; j++){
x[i] = j;
if(canPlace(i)) queen(i+1);
}
}
int main(){
queen(1);
return 0;
}
