189 8069 5689
原：八皇后问题的递归和非递归实现
创新互联公司凭借在网站建设、网站推广领域领先的技术能力和多年的行业经验，为客户提供超值的营销型网站建设服务，我们始终认为：好的营销型网站就是好的业务员。我们已成功为企业单位、个人等客户提供了做网站、网站建设服务，以良好的商业信誉，完善的服务及深厚的技术力量处于同行领先地位。
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名
的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即
任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后
来有人用图论的方法解出92种结果。事实上就是有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(; col
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
for(int j=0; j
int k;
for( k=0;k
break;
}
if(k==squares) {
for(k=0; k
System.out.print(" and ");
for(k=0; 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();
}
}
转载请注明出处:http://herosoft.itpub.net/post/5802/487069