queenrandom.java

N皇后问题的实现

package yus.part2;

public class QueenRandom {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		int n = 54;
		int[] x = new int[n + 1];
		boolean success = false;
		while (success == false) {
			success = queensLV(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 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;
	}

	static boolean queensLV(int n, int[] x) {
		int k = 1;
		int ok[] = new int[n + 1];
		int count;
		boolean success = false;
		while (k <= n) {
			count = 0;
			for (int i = 1; i <= n; i++) {
				x[k] = i;
				if (place(k, x) == true) {
					count++;
					ok[count] = i;
				}
			}
			if (count == 0) {
				success = false;
				break;
			} else {
				x[k] = ok[(int) (Math.random() * (count)) + 1];
				success = true;
			}
			k++;
		}
		return success;
	}
}