nqueen.java

本实例通过堆栈以及回朔法进行N皇后的遍历.

import java.util.*;

public class NQueen {
	Stack s = new Stack();
	int N = 5;
	int i ;
	Queen q;

	public static void main(String[] args) {
		NQueen NQ = new NQueen();
		NQ.start();
	}

	void start() {
		q = new Queen(1, 1);
		s.push(q);
		back(q, 1);//寻找皇后
		if (N == s.size()) {
			System.out.println(N + "皇后找到解决方案：");
			print();
		} else {
			System.out.println(N + "皇后没有找到解决方案！");
		}
	}

	void back(Queen q, int col) {
		i = q.i + 1;
		for (int j = col ; j <= N; j++) {
			q = new Queen(i, j);
			/*如果没有冲突，q的列加1，否则将将q压如栈中*/
			if (!isClash(q)) {
				continue;
			} else {
				s.push(q);
				/*如果栈的长度等于N，说明N皇后找到解决方案，方法返回，否则q的行*/
				if (N == s.size()) {
					return;
				} else {
					back(q, 1);//递归
				}
			}
		}
		/*删除栈顶，再将新的栈顶递归*/
		if (q.i < N) {
			try {
				q = (Queen) s.pop();
				col = q.j+1;
				q = (Queen) s.peek();
				back(q, col);
			} catch (Exception e) {
				return;
			}
		}
	}

	/**
	 * 判断是否冲突
	 * 
	 * @param q
	 * @return
	 */
	boolean isClash(Queen q) {
		Queen sq;
		for (int i = 0; i < s.size(); i++) {
			sq = (Queen) s.get(i);
			if (Math.abs(q.i - sq.i) == Math.abs(sq.j - q.j) || q.i == sq.i
					|| q.j == sq.j) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 打印解决方案
	 * 
	 */
	void print() {
		for (int i = 0; i < s.size(); i++) {
			System.out.println(s.get(i));
		}
	}
}