原：八皇后問題的遞歸和非遞歸Java實(shí)現(xiàn)

原：八皇后問題的遞歸和非遞歸實(shí)現(xiàn)

八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名
的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即
任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后
來有人用圖論的方法解出92種結(jié)果。事實(shí)上就是有92種解法。

以下是code：

[@more@]

import java.io.*;
import java.util.*;

class Queens {
final boolean available = true;
final int squares =5, norm = squares - 1;
int[] positionInRow = new int[squares];
boolean[] column = new boolean[squares];
boolean[] leftDiagonal = new boolean[squares*2 - 1];
boolean[] rightDiagonal = new boolean[squares*2 - 1];
int howMany = 0;
List queensList = new ArrayList();

Queens() {
for (int i = 0; i < squares; i++) {
positionInRow[i] = -1;
column[i] = available;
}
for (int i = 0; i < squares*2 - 1; i++)
leftDiagonal[i] = rightDiagonal[i] = available;
}
void printBoard(PrintStream out, int row, int col) {

out.println("row = " +row + ", col = " + col);
}


void putQueen(int row) {
int[] arr = null;
for (int col = 0; col < squares; col++)
if (column[col] == available &&
leftDiagonal [row+col] == available &&
rightDiagonal[row-col+norm] == available) {

positionInRow[row] = col;
column[col] = !available;
leftDiagonal[row+col] = !available;
rightDiagonal[row-col+norm] = !available;
if (row < squares-1)
putQueen(row+1);


else {
for(int kk=0; kk < positionInRow.length; kk++ ) {
System.out.print(positionInRow[kk] +", ");
}
System.out.println();

arr =new int[positionInRow.length];
System.arraycopy(positionInRow, 0, arr, 0, positionInRow.length);
queensList.add(arr);

this.howMany ++;
}

column[col] = available;
leftDiagonal[row+col] = available;
rightDiagonal[row-col+norm] = available;

}
}


void putQueen() {
int times = 1;
boolean flag=false;
int[] st = new int[squares];
int[] st2 = new int[squares];
int top =0;

for(int row=0, col=0; row < squares; ) {
for(; colif (column[col] == available &&
leftDiagonal [row+col] == available &&
rightDiagonal[row-col+norm] == available) {



positionInRow[row] = col;
column[col] = !available;
leftDiagonal[row+col] = !available;
rightDiagonal[row-col+norm] = !available;

st[top]=row;
st2[top]=col;
top++;

col=0;
row++;
flag = true;
break;
}



}

if (row == squares)
for(int k=0; k < positionInRow.length; k++) {
if(positionInRow[k] != -1) {
if(k==positionInRow.length-1) {
for(int kk=0; kk < positionInRow.length; kk++ ) {
System.out.print(positionInRow[kk] +", ");
}
System.out.println();
this.howMany ++;

}
}
}



if(st2[0]==squares-1&&top==0)return;

if(/*col==squares*/ !flag) {
if(/*!st.isEmpty() && !st2.isEmpty()*/top!=0) {
/* row=((Integer)st.pop()).intValue();
col=((Integer) st2.pop()).intValue(); */
top--;row=st[top];col=st2[top];

column[col] = available;
leftDiagonal[row+col] = available;
rightDiagonal[row-col+norm] = available;
col++;
}

}
flag=false;


if(row==squares ) {

row=0;

}





}
}

void getAllSymmetricalQueens() {
int[] q, q2;
for(int i=0; i q = (int[]) queensList.remove(0);

for(int j=0; j q2=(int[]) queensList.get(j);


int k;
for( k=0;kif(q[k]+q2[k]!=squares-1)
break;
}
if(k==squares) {
for(k=0; kSystem.out.print(q[k] + ",");
System.out.print(" and ");
for(k=0; kSystem.out.print(q2[k] + ",");
System.out.print(" are symmetricaln");
}

}
}
}

public static void main(String args[]) {
Queens queens = new Queens();
queens.putQueen(0); System.out.println("----------------");
queens.putQueen();


System.out.println(queens.howMany + " solutions found.");

queens.getAllSymmetricalQueens();
}
}

轉(zhuǎn)載請注明出處:http://herosoft.itpub.net/post/5802/487069