数据结构应用回顾之Stack(三) N皇后问题 非递归实现

N皇后问题使用stack的非递归实现

 

package com.xx.dataStructure.stack;

class Point {
	int x;
	int y;
	int value;
	
	Point(int x ,int y){
		this(x,y,0);
	}
	
	Point(int x ,int y,int value){
		this.x = x;
		this.y = y;
		this.value = value;
	}
	
	@Override
	public String toString(){
		return "(" + x + "," +  y + ")";
	}
}

//求解N皇后问题的所有解
public class Queen {

	private int solution = 0;

	private int n;
	
	private Point [][] points = null;
	
	public Queen(int n) {
		assert (n > 0);
		this.n = n;
		this.solution = 0;
		points = new Point[n][n];
		for(int i =0; i<n ; ++i){
			for(int j =0; j<n ; ++j){
				points[i][j] = new Point(i,j);
			}
		}
	}
	
	//point的行、列、对角线的点value +1
	public static void add(Point[][] points,Point point){
		//列
		for(int i = 0; i < points.length ; i++ ){
			points[i][point.y].value += 1;
		}
		//行
		for(int i = 0; i < points.length ; i++ ){
			points[point.x][i].value += 1;
		}
		//对角线
		for( int i= point.x, j = point.y ;( i < points.length && j < points.length);
				++i , ++j ){
			points[i][j].value += 1;
		}
		for( int i= point.x, j = point.y ;( i >= 0 && j < points.length);
				--i , ++j ){
			points[i][j].value += 1;
		}
		for( int i= point.x, j = point.y ;( i < points.length && j >= 0);
				++i , --j ){
			points[i][j].value += 1;
		}
		for( int i= point.x, j = point.y ;( i >= 0 && j >= 0);
				--i , --j ){
			points[i][j].value += 1;
		}
		point.value = 1;
	}
	
	
	public static void minus(Point[][] points,Point point){
		//列
		for(int i = 0; i < points.length ; i++ ){
			points[i][point.y].value -= 1;
		}
		//行
		for(int i = 0; i < points.length ; i++ ){
			points[point.x][i].value -= 1;
		}
		//对角线
		for( int i= point.x, j = point.y ;( i < points.length && j < points.length);
				++i , ++j ){
			points[i][j].value -= 1;
		}
		for( int i= point.x, j = point.y ;( i >= 0 && j < points.length);
				--i , ++j ){
			points[i][j].value -= 1;
		}
		for( int i= point.x, j = point.y ;( i < points.length && j >= 0);
				++i , --j ){
			points[i][j].value -= 1;
		}
		for( int i= point.x, j = point.y ;( i >= 0 && j >= 0);
				--i , --j ){
			points[i][j].value -= 1;
		}
		point.value = 0;
	}
	
	
	// 能否使用非递归算法 回溯法来使时间复杂度降为多项式
	public static void solveProblem0(Queen queen) {
		Stack<Point> stack = new Stack<Point>(100);
		System.out.println("开始求解"+queen.n+"皇后问题。");
		Point [][] points = queen.points;
		int [] tags = new int[queen.n]; 
		for(int i = 0; i < queen.n; i ++){
			tags[i] = -1;
		}
		int k = 0;
		try {
			for (int i = 0; i < queen.n; ++i) {
				Point currentPoint = points[0][i];
				stack.push(currentPoint);
				add(points,currentPoint);
				k++;
				while(!stack.isEmpty()){
					if (k == queen.n ){
						queen.solution++;
						stack.traverse();
						Point point = stack.pop();
						minus(points, point);
						k--;
					}else {
						Point nextP = findNextPoint(points,tags,k);
						if (nextP != null){
							stack.push(nextP);
							add(points,nextP);
							k++;
						}else {
							Point point = stack.pop();
							minus(points, point);
							tags[k--] = -1;
						}
					}
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static Point findNextPoint(Point [][] points,int[] tags ,int k){
		Point p = null;
		for(int q = tags[k] + 1 ; q < points.length; q++){
			tags[k]++;
			if (points[k][q].value == 0){
				p = points[k][q];
				break;
			}
		}
		return p;
	}

    public static void main(String[] args) {
		solveProblem0(new Queen(1));
		solveProblem0(new Queen(2));
		solveProblem0(new Queen(3));
		solveProblem0(new Queen(4));
		solveProblem0(new Queen(5));
		solveProblem0(new Queen(6));
	}
}

  程序输出

  

开始求解1皇后问题。
(0,0),
开始求解2皇后问题。
开始求解3皇后问题。
开始求解4皇后问题。
(0,1),(1,3),(2,0),(3,2),
(0,2),(1,0),(2,3),(3,1),
开始求解5皇后问题。
(0,0),(1,2),(2,4),(3,1),(4,3),
(0,0),(1,3),(2,1),(3,4),(4,2),
(0,1),(1,3),(2,0),(3,2),(4,4),
(0,1),(1,4),(2,2),(3,0),(4,3),
(0,2),(1,0),(2,3),(3,1),(4,4),
(0,2),(1,4),(2,1),(3,3),(4,0),
(0,3),(1,0),(2,2),(3,4),(4,1),
(0,3),(1,1),(2,4),(3,2),(4,0),
(0,4),(1,1),(2,3),(3,0),(4,2),
(0,4),(1,2),(2,0),(3,3),(4,1),
开始求解6皇后问题。
(0,1),(1,3),(2,5),(3,0),(4,2),(5,4),
(0,2),(1,5),(2,1),(3,4),(4,0),(5,3),
(0,3),(1,0),(2,4),(3,1),(4,5),(5,2),
(0,4),(1,2),(2,0),(3,5),(4,3),(5,1),