n皇後java_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 queens = new ArrayList();//皇後

//private List nQueens = new ArrayList();

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();

}

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();

}

}