回溯法应用之n皇后有关问题

回溯法应用之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;
    		}
    	}
    }
	@Override
	public boolean valid(Position pos) {
		if(this.grid[pos.getRow()][pos.getColumn()]==0)
		return true;
		return false;
	}

	@Override
	public 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;
	}

	@Override
	public boolean done(Position pos) {
		if(pos.getRow()==this.grid.length-1)
			return true;
		return false;
	}

	@Override
	public 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;
    }

	@Override
	public 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;
        }
		@Override
		public boolean hasNext() {
			return count<this.size;
		}

		@Override
		public Object next() {
			Position nextPos=new Position(this.row+1,count); 
			count++;
			return nextPos;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
    	
    }
}

初始情况是整个棋盘每个位置初始值为0，public boolean valid(Position pos)中判断为0 有效
在public void record(Position pos)中我让该位置为中心的横竖斜的方向上每个位置之加1，该位置加2*this.grid.length;
public void undo(Position pos)，撤销时与上是逆过程；

private class QueenIterator implements Iterator为内部类，记录某位置的下一行可选位置，

一下是测试程序：

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

测试时可找到从第一排每个位置开始的可能的n皇后结果，还有什么不妥的地方，欢迎拍砖

回溯法应用之n皇后有关问题

相关推荐