java N皇后实现问题解析

n皇后问题是一个典型的约束求解问题，利用递归机制，可以很快的得到结果。
n皇后问题的描述：
在一个n*n的棋盘上，摆放n个皇后，要求每个皇后所在行、列、以及两个对角线上不能出现其他的皇后，否则这些皇后之间将会相互攻击。如下图所示。

利用递归机制，可以很容易的求解n皇后问题。针对八皇后，总共有92种解。下面将给出n-皇后问题的一般求解代码，在这里代码是使用java编码的。
总共设计了三个类，一个是皇后类（queen），一个棋盘类（board），一个是求解主程序类（nqueens）。具体代码如下：

import java.util.arraylist;
import java.util.list;
public class nqueens {
private int numsolutions;//求解结果数量
private int queensize;//皇后的多少
private board board;//棋盘
private list<queen> queens = new arraylist<queen>();//皇后
//private list<queen> nqueens = new arraylist<queen>();
public nqueens(){
}
public nqueens(int size){
numsolutions = 0;
queensize = size;
board = new board(queensize);
for (int i = 0; i < queensize; i++) {
queen queen = new queen();
queens.add(queen);
}
}
public void solve(){
system.out.println("start solve....");
putqueen(0);
}
private void putqueen(int index){
int row = index;
//如果此列可用
for (int col = 0; col < board.getqueensize(); col++) {
if (board.getlayout()[row][col] == 0) {
//将皇后的位置置为此列位置
queens.get(row).setposition(col);
//然后将相应的位置（此列的正下方以及两个对角线）加1（即使其不可用）
for (int i = row + 1; i < board.getqueensize(); i++) {
board.getlayout()[i][col] ++;
if (row + col - i >= 0) {
board.getlayout()[i][row + col - i] ++;
}
if (i + col - row < board.getqueensize()) {
board.getlayout()[i][i + col - row] ++;
}
}
if (row == board.getqueensize()-1) {
numsolutions++;
printsolution(numsolutions);
}else {
putqueen(row + 1);
}
//回溯，将相应的位置（此列的正下方以及两个对角线）减1
for (int i = row + 1; i < board.getqueensize(); i++) {
board.getlayout()[i][col] --;
if (row + col - i >= 0) {
board.getlayout()[i][row + col - i] --;
}
if (i + col - row < board.getqueensize()) {
board.getlayout()[i][i + col - row] --;
}
}
}
}
}
//打印求解结果
private void printsolution(int i){
system.out.println("the "+i+ " solution is:");
for (int j = 0; j < board.getqueensize(); j++) {
for (int k = 0; k < board.getqueensize(); k++) {
system.out.print(queens.get(j).getposition() == k ? " * ":" - ");
}
system.out.println();
}
system.out.println();
}
/**
* @param args
*/
public static void main(string[] args) {
//可以改变参数
nqueens nqueens = new nqueens(8);
nqueens.solve();
}
}
import java.io.serializable;
//皇后类
public class queen implements serializable, cloneable {
/**
*
*/
private static final long serialversionuid = 7354459222300557644l;
//皇后的位置
private int position;
public queen(){
}
public int getposition() {
return position;
}
public void setposition(int position) {
this.position = position;
}
public object clone() throws clonenotsupportedexception {
return super.clone();
}
}
import java.io.serializable;
//棋盘类
public class board implements serializable,cloneable {
/**
*
*/
private static final long serialversionuid = -2530321259544461828l;
//棋盘的大小
private int queensize;
//棋盘的布局
private int[][] layout;
public board(int size){
this.queensize = size;
this.layout = new int[queensize][queensize];
//初始化，使棋盘所有位置都可用，即全部置为0
for (int i = 0; i < queensize; i++) {
for (int j = 0; j < queensize; j++) {
layout[i][j] = 0;
}
}
}
public int getqueensize() {
return queensize;
}
public void setqueensize(int queensize) {
this.queensize = queensize;
}
public int[][] getlayout() {
return layout;
}
public void setlayout(int[][] layout) {
this.layout = layout;
}
public object clone() throws clonenotsupportedexception {
return super.clone();
}
}