NQueen.rar_NQueen

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