八皇后
八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
public class EightQueen {private static int LENGTH = 8;private static Blank[][] grid = new Blank[LENGTH][LENGTH];private static int NOPOSITION_FOUND = -1;/** * @param args */private static int count = 0;public static void main(String[] args) {init();//test();eightQ();System.out.println(count);}private static void eightQ() {//from the first roweightQ(0,0);}/** * @param rowNo start row * @param columnNo start column * */private static void eightQ(int rowNo,int columnNo) {//if the column is large than length, just returnif (columnNo>=LENGTH){return;}//look for a position in this rowint column = lookForPosition(rowNo,columnNo);if (column<0){//can not find any position just returnreturn;}//below is the situation that find any position in current row//put the position flag to truegrid[rowNo][column].setFlag(true);//if it is the last row,just add the countif (rowNo==LENGTH-1){//if now is the last row and there is a positioncount++;showGrid();}//go to the next row, look from the 0 columnif (rowNo<LENGTH-1) {eightQ(rowNo+1, 0);}//remove the flaggrid[rowNo][column].setFlag(false);//seek for next choice in this columneightQ(rowNo,column+1);}private static int lookForPosition(int rowNo, int i) {for(int j=i;j<LENGTH;j++) {if (testPosition(rowNo, j)){//if there is a positionreturn j;}}return NOPOSITION_FOUND;}private static void test() {grid[1][2].setFlag(true);System.out.println(testPosition(2, 2));System.out.println(testPosition(2, 1));System.out.println(testPosition(0, 1));System.out.println(testPosition(2, 3));System.out.println(testPosition(0, 3));System.out.println(testPosition(3, 0));}private static void init() {for (int i = 0; i < LENGTH; i++) {for (int j = 0; j < LENGTH; j++) {grid[i][j] = new Blank();}}}private static boolean testPosition(int i, int j) {for (int k = 0; k < LENGTH; k++) {// same row, different columnif (grid[i][k].isFlag()) {return false;}}for (int k = 0; k < LENGTH; k++) {// same column, different rowif (grid[k][j].isFlag()) {return false;}}int leftUp = i >= j ? j : i;int rightDown = (LENGTH - i - 1) >= (LENGTH - j - 1) ? (LENGTH - j - 1): (LENGTH - i - 1);int leftDown = j >= (LENGTH - i - 1) ? (LENGTH - i - 1) : j;int rightUp = i >= (LENGTH - j - 1) ? (LENGTH - j - 1) : i;//System.out.println(leftUp+","+rightDown+","+leftDown+","+rightUp);for (int k = 1; k <= leftUp; k++) {if (grid[i-k][j-k].isFlag()){return false;}}for (int k = 1; k <= rightDown; k++) {if (grid[i+k][j+k].isFlag()){return false;}}for (int k = 1; k <= leftDown; k++) {if (grid[i+k][j-k].isFlag()){return false;}}for (int k = 1; k <= rightUp; k++) {if (grid[i-k][j+k].isFlag()){return false;}}return true;}private static void showGrid() {System.out.println("==========GRID==========");for (Blank[] row : grid) {for (Blank b : row) {if (b.isFlag()) {System.out.print(" * ");} else {System.out.print(" - ");}}System.out.println("");}}private static class Blank {private boolean flag = false;public boolean isFlag() {return flag;}public void setFlag(boolean flag) {this.flag = flag;}}private static class Position{private int x;public int getX() {return x;}public void setX(int x) {this.x = x;}public int getY() {return y;}public void setY(int y) {this.y = y;}private int y;}}?