回溯法应用之n皇后问题
在n行n列的棋盘上，如果两个皇后位于棋盘上的同一行或者同一列或者同一对角线上，则称他们为互相攻击。现要求找出使n元棋盘上的n个皇后互不攻击的所有布局,即是n皇后问题
package 数据结构及算法.回溯法应用之n皇后问题;import java.util.Iterator;import 数据结构及算法.回溯法.Application;import 数据结构及算法.回溯法.Position;public class Queen implements Application{ private int[][]grid; private int[][]path; public Queen(int n){ this.grid=new int[n][n]; this.path=new int[n][2]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ this.grid[i][j]=0; } } }@Overridepublic boolean valid(Position pos) {if(this.grid[pos.getRow()][pos.getColumn()]==0)return true;return false;}@Overridepublic void record(Position pos) {for(int i=0;i<this.grid.length;i++){if(i!=pos.getColumn()) this.grid[pos.getRow()][i]+=1;//横if(i!=pos.getRow())this.grid[i][pos.getColumn()]+=1;//竖}int x=pos.getRow()-1;int y=pos.getColumn()-1;while(x>=0&&y>=0){//左上this.grid[x][y]+=1;x--;y--;}x=pos.getRow()+1;y=pos.getColumn()-1;while(x<this.grid.length&&y>=0){//左下this.grid[x][y]+=1;x++;y--;}x=pos.getRow()-1;y=pos.getColumn()+1;while(y<this.grid.length&&x>=0){//右上this.grid[x][y]+=1;x--;y++;}x=pos.getRow()+1;y=pos.getColumn()+1;while(x<this.grid.length&&y<this.grid.length){//右下this.grid[x][y]+=1;x++;y++;}this.grid[pos.getRow()][pos.getColumn()]+=2*this.grid.length;}@Overridepublic boolean done(Position pos) {if(pos.getRow()==this.grid.length-1)return true;return false;}@Overridepublic void undo(Position pos) {for(int i=0;i<this.grid.length;i++){if(i!=pos.getColumn()) this.grid[pos.getRow()][i]-=1;//横if(i!=pos.getRow())this.grid[i][pos.getColumn()]-=1;//竖}int x=pos.getRow()-1;int y=pos.getColumn()-1;while(x>=0&&y>=0){//左上this.grid[x][y]-=1;x--;y--;}x=pos.getRow()+1;y=pos.getColumn()-1;while(x<this.grid.length&&y>=0){//左下this.grid[x][y]-=1;x++;y--;}x=pos.getRow()-1;y=pos.getColumn()+1;while(y<this.grid.length&&x>=0){//右上this.grid[x][y]-=1;x--;y++;}x=pos.getRow()+1;y=pos.getColumn()+1;while(x<this.grid.length&&y<this.grid.length){//右下this.grid[x][y]-=1;x++;y++;}this.grid[pos.getRow()][pos.getColumn()]-=2*this.grid.length;}public String toString(){String result=""; for(int i=0;i<this.grid.length;i++){ for(int j=0;j<this.grid[0].length;j++){ if(this.grid[i][j]==2*this.grid.length) result+="*"+" "; else result+=this.grid[i][j]+" "; } result+="\n"; } return result; }@Overridepublic Iterator iterator(Position pos) {return new QueenIterator(pos,this.grid.length);} private class QueenIterator implements Iterator{ private int size; private int count=0; private int row; //private int col; public QueenIterator(Position pos,int queenGridLength){ this.row=pos.getRow(); //this.col=pos.getColumn(); this.size=queenGridLength; }@Overridepublic boolean hasNext() {return count<this.size;}@Overridepublic Object next() {Position nextPos=new Position(this.row+1,count); count++;return nextPos;}@Overridepublic void remove() {throw new UnsupportedOperationException();} }}package 数据结构及算法.回溯法应用之n皇后问题;import java.util.Iterator;import java.util.Scanner;import 数据结构及算法.回溯法.Application;import 数据结构及算法.回溯法.BackTrack;import 数据结构及算法.回溯法.Position;public class QueenTest { private int n; public QueenTest(){ Scanner sc=new Scanner(System.in); String prompt="请输入皇后的大于3的维数！"; System.out.println(prompt); this.n=sc.nextInt(); pocessInput(); }public void pocessInput() {Application app=new Queen(n);BackTrack backTrack=new BackTrack(app);println("开始为：");println(app.toString());Position pos=new Position(-1,0);Iterator itr=app.iterator(pos);int count=0;while(itr.hasNext()){Position startPosition=(Position) itr.next();app.record(startPosition);if(backTrack.tryToSolve(startPosition)){println("success");count++;println("第"+count+"个满足的为：");println(app.toString());app=new Queen(this.n);backTrack=new BackTrack(app);}else{app=new Queen(this.n);backTrack=new BackTrack(app);println("failure!");}}}public void println(String s){System.out.println(s);}public static void main(String[]args){new QueenTest();}}