原：八皇后问题的递归和非递归Java实现

原：八皇后问题的递归和非递归实现

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名
的数学家高斯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(; 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( !flag) {
if(top!=0) {

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

转载请注明出处:Http://herosoft.itpub.net/post/5802/487069