queenback.java

N皇后问题的实现

package yus.part2;

public class QueenBack {

	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		int n = 20;
		int[] x = new int[n + 1];
		// int[] y = new int[n + 1];
		boolean success = false;
		while (success == false)
			success = backTrack(1, n, x);
		for (int i = 0; i < x.length; i++) {
			System.out.println("x[" + i + "]:" + x[i]);
		}

		long end = System.currentTimeMillis();
		System.out.println("time lasts " + (end - start) + "ms");
	}

	static boolean backTrack(int t, int n, int[] x) {

		if (t > n) {
			return true;
		} else {
			for (int i = 1; i <= n; i++) {
				x[t] = i;
				if (place(t, x) == true)
					if (backTrack(t + 1, n, x) == true)
						return true;
			}
		}
		return false;
	}

	static boolean place(int k, int[] x) {
		for (int j = 1; j < k; j++) {
			if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
				return false;
		}
		return true;
	}
}