Казалось бы, что можно добавить на тему о популярной задачке о расстановке ферзей на шахматной доске стандартной размерности 8x8 клеток? Но как оказалось и тут можно внести свою толику программистской мысли.
Классически задача решается последовательным перебором ферзей на заданной линии и бонусом предлагается анализировать диагонали которые покрываются установкой ферзя в нужную клетку. Но те реализации алгоритмов, что я видел, установкой или снятием ферзя с маркировкой диагоналей, едва ли перекрывают по быстродействию расстановку ферзей по-принципу ладьи.
Как оказывается в алгоритм можно привнести существенные улучшения отказавшись от линейного обхода/перебора клеток и внеся понятие анализа состояния атак шахматной доски.
Я добавил два улучшающих принципа в алгоритм, которые позволяют снизить общее кол-во переборов в три раза.
Двигаемся по столбцам (A-H). В столбцах перебираем строки (1-8)
Установить ферзя, означает - промаркировать все атаки (горизонтальную и диагональные) и пометить столбец с ферзём, как занятый.
Снять ферзя, означает снять маркировку атак и пометить столбец, который он занимал, как свободный.
Проверить поставлены ли все ферзи во всех столбцах. Если да, то выдать удачный результат.
Вернуться на шаг назад в переборе (снять последнего установленного ферзя).
Рекурсивно переходим к пункту №1.Проверить, есть ли такой свободный столбец, в который нельзя поставить ферзя?. Если такой столбец имеется - шаг назад в рекурсивном обходе, дальнейшие ходы - бессмысленны.
Вернуться на шаг назад в переборе (снять последнего установленного ферзя).
Рекурсивно переходим к пункту №1.Проверить, есть ли такой свободный столбец в который можно поставить только одного ферзя? Если такой такой имеется, разумеется туда и ставим ферзя, жертвуя линейностью обхода. Рекурсивно переходим к пункту №1.
Находим ближайший к началу доски свободный столбец, выполняем в нем перебор всех не атакованных позиций. Устанавливаем ферзя в не атакованную позицию.
Рекурсивно переходим к пункту №1
Для реализации алгоритма я выбрал 64-х битную математику в арифметических и логических операциях. [ + - AND NOT XOR OR << >>].
Шахматная доска 8x8 в 64 клетки отлично ложится в 64-х битовую переменную.
Чтобы не использовать внутренние циклы для маркировки состояний по диагонали, я инициализирую их заранее. Есть три раздельных слоя для маркировки атак ферзя. Два диагональных слоя и один горизонтальный. В один слой все три атаки сливать нельзя, так как это не позволит восстановить предыдущее состояние шахматной доски.
Для демонстрации своего алгоритма я выбрал язык C#, как наиболее легкий и понятный. JS не содержит поддержки целочисленной 64-х битной арифметики, и чтобы не усугублять демо-пример кластеризацией на 32-х битную арифметику - я от него отказался.
Язык СИ несколько тяжелей, по тексту, но содержит поддержку нужных для ускорения работы алгоритма инструкций процессора - POPCNT и BSF в виде "intrinsics"-функций.
С JVM на момент написания этой статьи существуют некоторые неопределённости, о которых не будем распространяться.
В итоге выбран C# с дополнительным классом битовой логики, который пытливый программист сам может переложить на процессорную аппаратную поддержку.
Итак приступим!
Размещаем шахматную доску в 64-битную переменную следующим образом
Первого ферзя в алгоритме ставим на [A1] (x = 0, y = 0). Базовое движение делаем по X-оси (по столбцам), на каждой оси перебираем позицию Y (строки). Как видно из иллюстрации, каждый столбец представляет из себя байт (8-мь бит).
Теперь промаркируем диагонали:
Номер LR-диагонали считается по формуле: N = X+Y
Так например, для позиций (xy): 3:2 (26), 4:1 (33), 1:4 (12) - Номером диагонали будет - 5;
для позиций (xy): 7:4 (60), 5:6 (46), 4:7 (39) - Номером диагонали будет - 11;
Диагональ LR: (LEFT+BOTTOM : RIGHT+TOP)
Номер RL-диагонали считается по формуле: N = 7 - X+Y
Ну а дальше - дело техники:
Вводим массивы:
ulong diag_LR[15]
ulong diag_RL[15]
Массивы содержат шахматную доску где биты установленные в 1 означают атаку по диагонали. Предварительно инициализируем их. Данные массивы нужны для того, чтобы не вводить в основной цикл внутренние циклы для маркировки атак. Массив для горизонтальной атаки не нужен, поскольку легко накладывается 64-битным числомВводим переменную "ulong markers". Каждый байт markers содержит либо 0x00, либо 0xFF, чтобы обозначать доступен ли X-столбец для установки ферзя.
0xFF - доступен
0x00 - занятВводим три переменные (ulong): attacks_HZ, attacks_LR, attacks_RL, чтобы держать состояния атак по горизонтали и вертикалям. Чтобы получить полное состояние всех атак клетки, надо слить их по операции OR: attacks_HZ | attacks_LR | attacks_RL.
Для понимания работы алгоритма надо также понимать, что часть операций над 64-х разрядными числами можно совершать параллельно над байтами числа, если числа хранимые в байтах не вызывают арифметического переполнения относительно друг-друга. Например число 0x0303_0303_0303_0303 - можно рассматривать, как вектор из 8-ми байтов установленных в 3-и. Тогда операцией инкрементации вектора будет прибавление к числу - значения 0x0101_0101_0101_0101. Результатом будет - 0x0404_0404_0404_0404.
Ответом на вопрос - "В байт векторе присутствуют байты со значениями в диапазоне от 0 до 8. Есть ли в байт-векторе, хотя бы одно число 8?" - будет наложение на вектор маски - 0x0808_0808_0808_0808 операцией AND. Ненулевое значение означает, что байт-векторе есть такие числа.
0x0108_0304_0708_0506
AND
0x0808_0808_0808_0808 =
-----------------------------------
0x0800_0000_0008_0000 - ЕСТЬ (ненулевой результат)
0x0106_0304_0700_0506
AND
0x0808_0808_0808_0808 =
-----------------------------------
0x0000_0000_0000_0000 - НЕТ (нулевой результат)
Код прототипа:
Выражения предельно упрощены, для понимания логики происходящего, и для трассировки алгоритма в отладочном режиме
Алгоритм оптимизирован под инструкцию процессора BSF (Bit Scan Forward), которая в прототипе дана, как функция "BitOp.bsf64()". Также может применяться инструкция процессора
BLSR(BMI1).
using System;
namespace Queen_8x8
{
delegate void Solution(int[] queens);
class Program
{
static void Main(string[] args)
{
print("Hello Queens!");
print(":");
Queen_8x8 task = new Queen_8x8();
task.smart_check = true;
task.init(print_solution);
task.run();
print("solution_count = " + task.solution_count);
print("solve_count = " + task.solve_count);
print("reverse_count = " + task.reverse_count);
}
static void print(String s)
{
Console.WriteLine(s);
}
static void print_solution(int[] queens)
{
String s = "";
s += "[ ";
for (int i = 0; i < queens.Length; i++)
{
s += Char.ConvertFromUtf32(i + 65) + (queens[i] + 1).ToString();
if (i < (queens.Length - 1)) s += ", ";
}
s += " ]";
print(s);
}
}
class Queen_8x8
{
protected Solution solution;
public const int queens_count = 8;
public const int diag_count = queens_count * 2 - 1;
public ulong markers = 0xFFFF_FFFF_FFFF_FFFF;
public int[] queens = new int[queens_count];
ulong[] diag_LR = new ulong[diag_count];
ulong[] diag_RL = new ulong[diag_count];
ulong attacks_HZ = 0; // атака по горизонтали
ulong attacks_LR = 0; // атака по диагонали BL-TR [\]
ulong attacks_RL = 0; // атака по диагонали BR-TL [/]
public bool smart_check = true;
// Statisticks
public int solution_count = 0;
public int solve_count = 0;
public int reverse_count = 0;
private int get_LR(int x, int y) { return x + y; }
private int get_RL(int x, int y) { return (queens_count - 1 - x) + y; }
public void init(Solution solution)
{
this.solution = solution;
solution_count = 0;
solve_count = 0;
reverse_count = 0;
markers = 0xFFFF_FFFF_FFFF_FFFF;
for (int i = 0; i < queens.Length; i++)
{
queens[i] = -1;
}
for (int i = 0; i < diag_count; i++)
{
diag_LR[i] = 0;
diag_RL[i] = 0;
}
for (int x = 0; x < queens_count; x++)
{
for (int y = 0; y < queens_count; y++)
{
ulong mask = 1UL << ((x << 3) + y);
diag_LR[get_LR(x, y)] |= mask;
diag_RL[get_RL(x, y)] |= mask;
}
}
}
public void run()
{
solve();
}
protected void step(int qx, int qy)
{
ulong q_CM = 0xFFUL << (qx << 3);
ulong a_HZ = 0x0101_0101_0101_0101UL << qy;
ulong a_LR = diag_LR[get_LR(qx, qy)];
ulong a_RL = diag_RL[get_RL(qx, qy)];
// Set Queeen
queens[qx] = qy;
markers &= ~q_CM;
attacks_HZ |= a_HZ;
attacks_LR |= a_LR;
attacks_RL |= a_RL;
// Recurse
solve();
// Remove Queeen
attacks_HZ &= ~a_HZ;
attacks_LR &= ~a_LR;
attacks_RL &= ~a_RL;
markers |= q_CM;
queens[qx] = -1;
}
protected void solve()
{
if (markers == 0)
{
solution_count++;
solution(queens);
return;
}
ulong attacks = attacks_HZ | attacks_LR | attacks_RL;
// Получаем в каждом байте 64-разрядного числа -
// сумму занятых мест по столбцам
// Каждый байт обозначает столбец таблицы и содержит число
// в интервале от 0 до 8
ulong sum_vec_8 = BitOp.popcnt64_bv(attacks);
// Проверка, что остались незаполненные столбцы
// Определяем что в каком либо столбце присуствует число 8
// Если в каком-либо столбце присутствует число 8, то общее значение теста
// станет ненулевым
ulong test = sum_vec_8 & 0x0808_0808_0808_0808UL;
test &= markers; // Отбрасывем столбцы (columns), где уже установлены ферзи
if (smart_check && test != 0)
{
return; // Есть столбец не занятый ферзем, но поставить в этот столбец ферзя - невозможно
}
// Проверка, на то что есть столбцы, только с одим возможным ходом
// Поскольку мы отбросили вариант, что в столбцах присутствует число 8
// прибавляем к каждому столбцу единицу и опять проверяем все столбцы на наличие числа 8
// Если изначально в каком-либо столбце присутствовало число 7, то общее значение теста
// станет ненулевым
test = sum_vec_8 + 0x0101_0101_0101_0101UL;
test &= 0x0808_0808_0808_0808UL;
test &= markers; // Отбрасывем столбцы (columns), где уже установлены ферзи
int qx;
int qy;
ulong column;
if (smart_check && test != 0)
{
reverse_count++;
qx = BitOp.bsf64((test >> 3)) >> 3;
column = (~attacks >> (qx << 3)) & 0xFFUL;
qy = BitOp.bsf64(column);
step(qx, qy);
return;
}
// Делаем перебор по столбцу
qx = BitOp.bsf64(markers) >> 3;
column = (~attacks >> (qx << 3)) & 0xFFUL;
while (column != 0)
{
solve_count++;
qy = BitOp.bsf64(column);
column &= column - 1; // BLSR BMI1!!! column &= ~(1UL << qy); // Сбросить самый младший единичный бит
step(qx, qy);
}
return;
}
}
class BitOp
{
// Просумировать все биты в байтах 64-разрядного числа
public static ulong popcnt64_bv(ulong value)
{
ulong result = value;
result = result - ((result >> 1) & 0x5555_5555_5555_5555UL); // Результат сумм по 2-а бита
result = (result & 0x3333_3333_3333_3333UL) + ((result >> 2) & 0x3333_3333_3333_3333UL); // Результат сумм по 4-е бита
result = (result + (result >> 4)) & 0x0F0F_0F0F_0F0F_0F0F; // Результат сумм по 8-ь бит
return result;
}
public static byte add64_bv(ulong value)
{
ulong result = value;
result += result >> 8; // Результат сумм по 16-ь бит
result += result >> 16; // Результат сумм по 32-ь бит
result += result >> 32; // Результат
return (byte)(result);
}
/*
* Подсчитать кол-во битов установленных в 1 в 64-разрядном числе
* Полностью эквивалентна машинной инструкции Intel x86/x64 - POPCNT
*/
public static byte popcnt64(ulong value)
{
ulong result = value;
result = result - ((result >> 1) & 0x5555_5555_5555_5555UL); // Результат сумм по 2-а бита
result = (result & 0x3333_3333_3333_3333UL) + ((result >> 2) & 0x3333_3333_3333_3333UL); // Результат сумм по 4-е бита
result = (result + (result >> 4)) & 0x0F0F_0F0F_0F0F_0F0F; // Результат сумм по 8-ь бит
result += result >> 8; // Результат сумм по 16-ь бит
result += result >> 16; // Результат сумм по 32-ь бит
result += result >> 32; // Результат
return (byte)(result);
}
public static byte popcnt8(byte value)
{
ulong result = value;
result = result - ((result >> 1) & 0x55); // Результат сумм по 2-а бита
result = (result & 0x33) + ((result >> 2) & 0x33); // Результат сумм по 4-е бита
result = (result + (result >> 4)) & 0x0F; // Результат сумм по 8-ь бит
return (byte)(result);
}
public static int bsf64(ulong value)
{
if (value == 0) return -1;
int bitpos = 0;
ulong mask = 0xFFFF_FFFF_FFFF_FFFFUL;
int step = 64;
while ((step >>= 1) > 0)
{
if ((value & (mask >>= step)) == 0)
{
value >>= step;
bitpos |= step;
}
}
return bitpos;
}
}
}
Результат программы:
В консоли видно эталонное число найденных комбинаций равное 92, и количество переборов равное 672.
В прототипе присутствует флажок-переменная "smart_check". Установка его в FALSE приведет к отключению моей оптимизации. Тогда вывод в консоль станет классическим.
2056 ./ 672 = 3,05
Оптимизация на количестве переборов выше в 3-и раза.
P.S. Продолжение возможно последует...
UPDATE!!! 27/07/2022
P.P.S. Уже появилась уточненная версия алгоритма (1а), где дополнительно анализируются не только колонки, но и строки, на возможность поставить в них ферзя или поставить единственно возможного ферзя. На данный момент вывод результата выглядит, так:
Упало количество ходов перебора (-80) и реверс-шагов (-140).
