Описание задачи: Разместите на шахматной доске восемь ферзей. Никакие два ферзя не могут атаковать друг друга (то есть никакие два ферзя не находятся в одном ряду, столбце или диагонали), как показано на рисунке.
В этой статье для этих двух задач используются несколько разные решения, но обе используют одномерные массивы. В 6.20 требуется найти эффективную раскладку, я установил однобитовый массив из восьми элементов, случайным образом перетасовывая значения массива и сравнивая значение с индексом до тех пор, пока в 6.22 не будет получена эффективная раскладка; это необходимо Найти все Эффективная компоновка: здесь я использую восьмеричные числа, просматриваю все числа от 001234567 до 076543210, преобразую их в восьмеричные строки, сравниваю каждый бит с его индексом и вывожу макет, соответствующий условиям. Принципы и методы реализации будут подробно представлены ниже.
Часть 1. Как определить, правильный ли это макет
Мы рассматриваем шахматную доску как матрицу 8*8 в диапазоне от 0 до 7. Наблюдая за картинкой слева, можно обнаружить, что ее расположение может быть представлено набором пар чисел (сверху вниз), а именно (0, 0), (1, 6), (2, 3), (3). , 5), (4, 7), (5, 1), (6, 4), (7, 2). Представлено массивом, то есть int []list = {0, 6, 3, 5, 7, 1, 4, 2};
Очевидно, что это правильный макет. Далее нам нужно рассмотреть вопрос: существует ли в эффективном макете какая-либо связь между индексом и соответствующим ему значением в массиве, то есть i и list[i]?
Здесь мы устанавливаем list[i] = k; list[j] = q; (i > j), которые удовлетворяют следующим двум условиям (это легче понять, когда они нарисованы на бумаге):
1. к != q;
2. i - j == k - q или i - j == q -k (получено из вопроса)
Чтобы гарантировать, что k != q, список массивов объявляется и инициализируется здесь так, что list[i] = i. Затем случайным образом перетасуйте массив, а затем проверьте, выполняется ли условие 2.
Скопируйте код кода следующим образом:
//Создаем и инициализируем массив
int [] список = новый int [arrSize];
for(int я = 0; я <arrSize; я++)
список [я] = я;
// Случайным образом перемешиваем массив
public static void randomizeArray(int [] list){
int arrSize = list.length;
интервал раниндекс;
for(int я = 0; я <arrSize; я++){
ranIndex = (int)(Math.random() * arrSize);
если(ranIndex!= я){
int temp = список [я];
список[i] = список[ranIndex];
список [ranIndex] = темп;
}
}
}
Тело кода 6.20 выглядит следующим образом:
Скопируйте код кода следующим образом:
// 6.20 Игра: Восемь ферзей
общественная недействительностьsolveEightQueens(){
интервал arrSize = 8;
int [] список = новый int [arrSize];
for(int я = 0; я <arrSize; я++)
список [я] = я;
число интервалов = 0;
логическое notValid = true;
в то время как (недействительно) {
считать++;
notValid = ложь;
RandomizeArray (список);
for(int я = 0; я <arrSize; я++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Проверяем, выполнено ли условие
невалид = правда;
перерыв;
}
}
if(notValid) перерыв;
} // конец внешнего цикла for
} // конец времени
// распечатываем результат
интервал я;
System.out.println("O(∩_∩)Оха-ха~, я пробовал " + count + " раз и в итоге добился успеха.");
for(i = 0; я <arrSize - 1; я++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
Часть 2. Найдите все допустимые макеты.
Поскольку версия 6.22 требует поиска всех допустимых раскладов с восемью ферзями, метод случайного перетасовки массива больше не применим, поэтому нам нужно найти метод, который сможет обойти все возможные массивы. Один из самых прямых методов — использовать восьмиуровневый цикл for, но объем кода слишком велик и голова легко упадет в обморок, поэтому этот метод не используется.
Внимательно наблюдая за значениями массива в части 1, вы можете обнаружить, что все они находятся в диапазоне от 0 до 7, поэтому обход с использованием восьмеричных целых чисел может гарантировать включение каждой перестановки. Поскольку восьмизначные числа различны, существует 8! = 40320 возможных перестановок, а общее количество восьмеричных чисел равно 8^8 = 16777216, поэтому возможное соотношение составляет 40320/16777216 = 1/416, в результате чего получается 40320. перестановки Также предусмотрены проверки для фильтрации окончательного допустимого макета. Этот метод все еще немного неэффективен, но я еще не придумал более эффективный.
Скопируйте код кода следующим образом:
// 6.22 Игра: Различные решения проблемы восьми ферзей (увеличение целочисленного значения, затем преобразование его в восьмеричную строку и последующая проверка)
public static voidsolveEightQueensMethod(){
int start = 001234567 // Восьмеричное число;
int end = 076543210 // восьмеричный;
int count = 0 // Подсчитываем количество допустимых макетов
for(int я = начало; я <конец; я++){
логическое значение isValid = isValid(i);
если (isValid) {
если (++счет % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Выводим количество допустимых макетов;
}
// Проверяем, является ли число допустимым макетом
public static boolean isValid(int number){
Строка numOct = Integer.toOctalString(число);
int arrSize = numOct.length();
if(arrSize==7) { // Если первая цифра числа равна 0, сгенерированная строка содержит только семь символов
numOct = '0' + numOct;
arrSize++;
}
for(int я = 1; я <arrSize; я ++){
for(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false // тот же столбец;
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false //Та же диагональ;
}
}
вернуть истину;
}
Расширение части 3: Проблема генерации комбинаций
Был такой вопрос на письменном тесте в прошлом году. Дана последовательность, выведите все комбинации. например,
Вывод «123»: 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321.
Вывод «abcd»: a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., абвд, ...
В версии 6.22 метод, используемый для поиска всех раскладов с восемью ферзями, заключается в увеличении номера типа int и последующей проверке одного за другим. Вышеописанную проблему можно решить аналогичным образом. Однако эффективность немного низка. Если есть более эффективный способ, обратитесь за советом к эксперту.