Отказ от ответственности: оригинальный вопрос помечен java, так что это решение Java.
Шахматная доска состоит из 64 клеток, и мы хотим разместить 8 королев, которые не могут атаковать каждогоДругой.Для быстрого поиска открытого квадрата, то есть квадрата, который не может быть атакован уже размещенными королевами, мы можем использовать 64-битную long для представления всей шахматной доски, а также использовать битовые манипуляции и Long.numberOfTrailingZeros() метод, чтобы найти открытый квадрат.
Нам нужны некоторые вспомогательные методы.Во-первых, метод маркировки квадратов, заблокированных королевой в заданной позиции.
private static long blockedSquaresWithQueenAt(int pos) {
// Set vertical bits
long board = 1L << (pos & 7);
board |= board << 8;
board |= board << 16;
board |= board << 32;
// Set horizontal bits
long mask2 = 1L << (pos & ~7);
board |= ((mask2 << 8) - 1) ^ (mask2 - 1);
// Set diagonal bits
for (int p = pos - 9; p >= 0 && (p & 7) != 7; p -= 9)
board |= 1L << p;
for (int p = pos - 7; p >= 0 && (p & 7) != 0; p -= 7)
board |= 1L << p;
for (int p = pos + 7; p < 64 && (p & 7) != 7; p += 7)
board |= 1L << p;
for (int p = pos + 9; p < 64 && (p & 7) != 0; p += 9)
board |= 1L << p;
return board;
}
Во-вторых, метод печати доски с необязательным маркером для одной позиции ферзя.Печать с маркером была полезна во время разработки / тестирования.
private static void printBoard(long board, int markPos) {
for (int pos = 0; pos < 64; pos++) {
System.out.print(pos == markPos ? '\u25CB' : (board & (1L << pos)) == 0 ? '\u00B7' : '\u25CF');
if ((pos & 7) == 7)
System.out.println();
else
System.out.print(' ');
}
}
Вот пример того, как это работает, с ферзем в строке 2, столбце 4, иначе в позиции 20 (все на основе 0) .
printBoard(blockedSquaresWithQueenAt(20), 20);
· · ● · ● · ● ·
· · · ● ● ● · ·
● ● ● ● ○ ● ● ●
· · · ● ● ● · ·
· · ● · ● · ● ·
· ● · · ● · · ●
● · · · ● · · ·
· · · · ● · · ·
Поскольку мы хотим быстро пропустить заблокированные квадраты, используя метод numberOfTrailingZeros(), мы хотим, чтобы заблокированные квадраты были 0-битными, поэтому мы инвертируем это:
printBoard(~ blockedSquaresWithQueenAt(20), -1);
● ● · ● · ● · ●
● ● ● · · · ● ●
· · · · · · · ·
● ● ● · · · ● ●
● ● · ● · ● · ●
● · ● ● · ● ● ·
· ● ● ● · ● ● ●
● ● ● ● · ● ● ●
Это пример нашей long доски с одним ферзем.
Теперь о основной логике.Мы используем массив размером 8, чтобы при необходимости быстро возвращаться назад.Наличие массива устраняет необходимость в рекурсии.
Затем мы помещаем первую королеву (королева 0), отмечаем заблокированные квадраты, находим первый разблокированный квадрат для второй королевы и повторяем до тех пор, пока все 8 ферзей не будут размещены, возвращаясь по мере необходимости.
Когда у нас есть 8 королев, мы строим и распечатываем доску из этих 8 ферзей, а затем возвращаемся назад, чтобы найти больше решений.
private static void solve() {
int[] posForQueen = new int[8];
long[] board = new long[8];
posForQueen[0] = -1;
// Keep trying until we backtrack from queen 0
for (int queen = 0; queen >= 0; ) {
// Find next open square for current queen
posForQueen[queen]++;
if (queen != 0)
posForQueen[queen] += Long.numberOfTrailingZeros(board[queen - 1] >>> posForQueen[queen]);
// Backtrack if no open square found
if (posForQueen[queen] >= 64) {
queen--;
} else {
// Build new board with open squares, accounting for all queens placed so far
board[queen] = ~ blockedSquaresWithQueenAt(posForQueen[queen]);
if (queen > 0)
board[queen] &= board[queen - 1];
// Advance to next queen if there are more queens to place
if (queen < 7) {
posForQueen[queen + 1] = posForQueen[queen];
queen++;
} else {
// Build and print board with all 8 queen positions
long queens = 0;
for (int i = 0; i < 8; i++)
queens |= 1L << posForQueen[i];
System.out.println();
printBoard(queens, -1);
}
}
}
}
Все решения:
● · · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· ● · · · · · ·
· · · · · ● · ·
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · · · ●
· · ● · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
· · · · ● · · ·
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · · · ●
● · · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · ● · · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · ● · · · ·
● · · · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · · ●
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · ● · · · ·
· · · · · · · ●
· · · · ● · · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
● · · · · · · ·
· · · · · · · ●
· · · ● · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
● · · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
● · · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · · · ●
· · · · ● · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
● · · · · · · ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · · · ●
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · ● · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
● · · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · · · ● · ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
● · · · · · · ·
· · · · ● · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
· · · · ● · · ·
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
● · · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
● · · · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
· · ● · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
● · · · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · ● · ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · · ●
· · · ● · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · · · ●
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · ● · · · ·
· · · · · · · ●
● · · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · ● · · · ·
· · · · · · · ●
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · · · ● · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · ● · · ·
● · · · · · · ·
· · · · · · · ●
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · · ● · · ·
● · · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · · · ●
· · · · · ● · ·
● · · · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · ● · ·
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · · · ●
· · ● · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
● · · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · · · ●
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · · ●
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · · ●
· · · ● · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · ● · · · ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · · ●
· · · · · ● · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · ● · · · ·
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · · · ●
· · · ● · · · ·
● · · · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · ● · ·
● · · · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
· · ● · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · · ●
· · · ● · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · ● · · · ·
· · · · · · · ●
· · · · ● · · ·
· · ● · · · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · · ●
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · · ●
● · · · · · · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · · ●
● · · · · · · ·
· · · · ● · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · · · ●
· · · · ● · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · ● · ·
· · ● · · · · ·
· · · · · · ● ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
· · · · · ● · ·
· · · ● · · · ·
● · · · · · · ·
· · · · ● · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· · · · · · ● ·
● · · · · · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · · ● ·
● · · · · · · ·
· · ● · · · · ·
· · · · · · · ●
· · · · · ● · ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· ● · · · · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · · ●
· · · · ● · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · ● ·
· ● · · · · · ·
· · · · · ● · ·
· · ● · · · · ·
● · · · · · · ·
· · · ● · · · ·
· · · · · · · ●
· · · · ● · · ·
· · · · · · ● ·
· · ● · · · · ·
● · · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· · · · ● · · ·
· ● · · · · · ·
· · · ● · · · ·
· · · · · · ● ·
· · ● · · · · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
● · · · · · · ·
· · · · · ● · ·
· · · ● · · · ·
· · · · · · ● ·
· · · ● · · · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · · ●
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · ● ·
· · · ● · · · ·
· ● · · · · · ·
· · · · · · · ●
· · · · · ● · ·
● · · · · · · ·
· · ● · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
· · · · · · · ●
· ● · · · · · ·
· · · ● · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · · ● · · ·
· · ● · · · · ·
· · · · · ● · ·
· · · · · · · ●
· ● · · · · · ·
· · · · ● · · ·
· · ● · · · · ·
● · · · · · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · ● · ·
· · · · · · · ●
· · ● · · · · ·
● · · · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · ● · · ·
· · · · · · ● ·
· · · ● · · · ·
· · · · · · · ●
· · · ● · · · ·
● · · · · · · ·
· · ● · · · · ·
· · · · · ● · ·
· ● · · · · · ·
· · · · · · ● ·
· · · · ● · · ·