ラス×××計算方と溯法はn皇后問題の上の応用です.
今日はラスを見ました.×××アルゴリズムは、次にトレースを組み合わせて、一緒にn皇后問題に応用して、比較してみると、時間効率は確かにokです.
package test;
import java.util.Random;
public class NQueen {
public static void main(String[] args) {
int size = 24;
array = new int[size];
// lv
long startTime = System.currentTimeMillis(); //
while (!lv(size)) {
}
for (int a : array) {
System.out.print(a + " ");
}
long endTime = System.currentTimeMillis(); //
System.out.println(" ： " + (endTime - startTime) + "ms");
//
startTime = System.currentTimeMillis();
drawBack(0);
for (int a : array) {
System.out.print(a + " ");
}
endTime = System.currentTimeMillis();
System.out.println(" ： " + (endTime - startTime) + "ms");
// lv
startTime = System.currentTimeMillis();
b = false;
while (!lv(size / 2)) {
}
drawBack(size / 2);
for (int a : array) {
System.out.print(a + " ");
}
endTime = System.currentTimeMillis();
System.out.println(" ： " + (endTime - startTime) + "ms");
}
private static int[] array;
// ×××(Las Vegas)
public static boolean lv(int n) {
Random random = new Random();
for (int a = 0; a < n; a++) {
int count = 0;
for (int b = 0; b < array.length; b++) {
if (place(array, a, b)) {
int k = random.nextInt(count + 1);
if (k == count) {
array[a] = b;
}
count++;
}
}
if (count == 0) {
return false;
}
}
return true;
}
// b
private static boolean b = false;
//
public static void drawBack(int level) {
if (level == array.length) {
b = true;
return;
} else {
for (int n = 0; n < array.length && !b; n++) {
if (place(array, level, n)) {
array[level] = n;
drawBack(level + 1);
}
}
}
}
public static boolean place(int[] array, int level, int value) {
for (int n = 0; n < level; n++) {
if (array[n] == value
|| Math.abs(n - level) == Math.abs(value - array[n])) {
return false;
}
}
return true;
}
}