快捷導(dǎo)航

java N皇后實現(xiàn)問題解析

更新時間：2012年11月29日 10:42:25 作者：

將 n 個皇后擺放在一個 n x n 的棋盤上，使得每一個皇后都無法攻擊到其他皇后,N皇后問題是一個典型的約束求解問題，利用遞歸機制，可以很快的得到結(jié)果,本文將詳細(xì)介紹，需要了解的朋友可以參考下

N皇后問題是一個典型的約束求解問題，利用遞歸機制，可以很快的得到結(jié)果。
N皇后問題的描述：
在一個n*n的棋盤上，擺放n個皇后，要求每個皇后所在行、列、以及兩個對角線上不能出現(xiàn)其他的皇后，否則這些皇后之間將會相互攻擊。如下圖所示。

利用遞歸機制，可以很容易的求解n皇后問題。針對八皇后，總共有92種解。下面將給出N-皇后問題的一般求解代碼，在這里代碼是使用java編碼的。
總共設(shè)計了三個類，一個是皇后類（Queen），一個棋盤類（Board），一個是求解主程序類（NQueens）。具體代碼如下：

復(fù)制代碼代碼如下:

 
import java.util.ArrayList; 
import java.util.List; 
public class NQueens { 
private int numSolutions;//求解結(jié)果數(shù)量 
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); 
//然后將相應(yīng)的位置（此列的正下方以及兩個對角線）加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); 
} 
//回溯，將相應(yīng)的位置（此列的正下方以及兩個對角線）減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] --; 
} 
} 
} 
} 
} 
//打印求解結(jié)果 
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) { 
//可以改變參數(shù) 
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(); 
} 
} 