八皇后问题是：在八行八列的格子上放８个皇后（棋子），使得任意两个皇后都攻击不到对方，即使得他们都不在同一行同一列和同一斜线上。

记得以前学C语言的时候，就见过这个问题，但当时怎么都弄不懂。现在看Java的书，书上课后练习有这个题目，就上网搜了一下怎么做，现在终于差不多懂了。代码和注释如下：

public class BackTrackQueen {

	private int[] s; // 记录皇后放置情况，s[i] = w表示皇后放在第i行的第w列（从下标0开始计数）
	private int m_queenNum; // 皇后个数
	private int m_solution; // 解的个数

	public BackTrackQueen(int queenNum) {
		m_solution = 0;
		m_queenNum = queenNum;
		s = new int[queenNum];
		for (int i = 0; i < queenNum; i++) {
			s[i] = -1;
		}
	}

	/**
	 * printThis()输出解，即打印皇后的放置情况
	 */
	public void printThis() {
		System.out.println("第" + m_solution + "种解法：");
		for (int i = 0; i < m_queenNum; i++)
			System.out.println("第" + (i + 1) + "行的第" + (s[i] + 1) + "列");
	}

	/**
	 * check()判断是否满足条件； 注意，因为每个s[i]只能等于一个值，也就限定了每行只有一个皇后，
	 * 所以，不用再判断同一行是否有2个皇后。
	 * 
	 * @param n
	 * @return boolean
	 */
	public boolean check(int n) {
		for (int i = 0; i < n; i++) {
			if (s[i] == s[n]) // 判断是否存在2个皇后在同一列
				return false;
			if (Math.abs(s[n] - s[i]) == n - i)// 判断是否存在2个皇后在同一斜线上
				return false;
		}
		return true;
	}

	/**
	 * queen()核心函数，实现把所有的满足题义的情况列出来
	 * 
	 * @param n
	 */
	public void queen(int n) {
		if (m_queenNum == n) {// 如果所有皇后都放置完毕，则输出当前解
			m_solution++;
			printThis();
			return;
		} else {
			for (int i = 0; i < m_queenNum; i++) {
				s[n] = i; // 将第n个皇后放在第n行的i列，如果满足check(n)为真，则继续放置下一个皇后
				if (check(n)) // 否则i++，继续（从下标0计数，这里的第n个，其实是现实中的第n+1个）
					queen(n + 1);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BackTrackQueen btq = new BackTrackQueen(8);//声明类的时候给定皇后个数为8，8皇后问题，也可以是N皇后问题
		btq.queen(0);
	}

}

参考文章：http://blog.csdn.net/lixiaoshan_18899/article/details/1286716

（原博客发布时间：2012-01-06 13:39:10）