NQueen.zip_NQueen

package queen; /** * 程序目的：用迭代回溯法解决N-皇后问题 * * 作者： 孙松山 * * 制作日期：2011-11-15 */ public class NQueen { private int N = 8; // 问题规模 private int[] x = new int[N + 1]; // 第k行的第x[k]列 private int count; // 存放有多少种解法 /** * 得到N的值 * * @return */ public int GetN() { return N; } /** * 得到总共有多少种解法的值 * * @return */ public int GetCount() { return count; } /** * 判断此位置是否安全（不和前边已经放置的皇后在同一列或者对角线上） * * @param row * @return */ private boolean SafeQueen(int row) { int i; for (i = 1; i < row; i++) if (x[i] == x[row] || i - x[i] == row - x[row] || i + x[i] == row + x[row]) return false; return true; } /** * 深度优先遍历整个解空间 */ public void Queen() { int i, j; int k = 1; x[1] = 1; count = 0; // 当k值减为0时则遍历完毕 while (k > 0) { // 如果此列不安全，则遍历下一列，直到遍历完此行的每一列为止 while (x[k] <= N && !SafeQueen(k)) { x[k]++; } if (x[k] <= N) { if (k == N) { for (i = 1; i <= N; i++) { // 控制棋盘的输出 for (j = 1; j <= N; j++) { if (j == x[i]) System.out.print('Q' + " "); else System.out.print('-' + " "); } System.out.println(); } count++; System.out.println("\n*************************\n"); // 找到一个最优解之后，回溯 k--; x[k]++; } else { // 正常情况下向下遍历 k++; x[k] = 1; } } else { // 当遍历k行的每一列都没有解时，回溯到k-1行，并且从第x[k-1]+1列再次开始遍历 k--; x[k]++; } } } /** * 主函数 * * @param args */ public static void main(String[] args) { NQueen q = new NQueen(); System.out.println("以下为" + q.GetN() + "-皇后问题的所有解："); q.Queen(); System.out.println(q.GetN() + "-皇后问题的解法共有：" + q.GetCount() + "种"); } }