Данная статья в большей мере является уточнением моей предыдущей статьи по оптимизации перебора на шахматной доске с ферзями.
https://habr.com/ru/post/679200/
Оптимизация перебора в данной задаче, это не только лишь хардкорное скоростное решение на базе 64-битной арифметики и SIMD-стиля. Это внесение в алгоритм решений, позволяющее сократить само количество шагов перебора. Пока я представляю начальный позиционный анализ.
Уточнением к моей предыдущей статье, является то что я добавил позиционный анализ не только к столбцам, но и к строкам. Пришлось довольно долго помучится для наиболее эффектной реализации. Задача крылась в решении, как быстро просуммировать атаки в строке шахматной доски, если я базовое движение совершаю по столбцам. Перепробовав несколько вариантов с битовыми играми, я остановился на том чтобы во время маркировки атак, вести альтернативную шахматную доску повернутую так, что X и Y просто меняются местами (инверсия осей). Для этого потребовалось ввести только три дополнительные переменные.
Некоторые коллеги читавшие мою статью, видимо не уловили смысл происходящего и пытаются утверждать, что всё равно совершается полный перебор позиций на доске. Но это совершенно не так.
Оптимизирующий алгоритм выглядит сейчас так:
Перед установкой нового ферзя:
Проверить, что на доске стоит полный комплект ферзей. Если да, то рапортовать об успехе. Снять последнего установленного ферзя, шаг назад.
Определить есть ли такой столбец на ВСЕЙ доске, в котором нет ферзя, но все клетки этого столбца являются атакованными. Если такой столбец имеется, то прервать перебор, шаг назад
Определить есть ли такая строка на ВСЕЙ доске, в которой нет ферзя, но все клетки этой стоки являются атакованными. Если такая строка имеется, то прервать перебор, шаг назад.
Определить есть ли такой столбец на ВСЕЙ доске, в котором нет ферзя, но можно поставить только одного ферзя. Если такой столбец имеется, то поставить туда ферзя, перейти к пункту №1.
Определить есть ли такая строка на ВСЕЙ доске, в которой нет ферзя, но можно поставить только одного ферзя. Если такая строка имеется, то поставить туда ферзя, перейти к пункту №1.
Берем свободный столбец ближе к началу, определяем свободные места в нем, начинаем перебором ставить туда ферзей. Поставив очередного ферзя идем к пункту №1.
Для понимания практичности этого анализа приведу иллюстрации:
По классике базовое движение по столбцам A-H, выставляем перебором ферзей по строкам №1-8. Имеем трёх установленных ферзей A1,B3,C5. "Как бы" собираемся прогуляться перебором по столбцу D в котором осталось три свободные клетки: D2,D7 и D8.
Но тут "Как бы" выключается и включается мой механизм оптимизации перебора...
Когда приступаем к установке 4-го ферзя, обнаруживаем, что на доске образовался такой столбец, что в него можно поставить только одного ферзя. Это позиция F4. Эта позиция отстоит вперёд на два столбца, то есть не является следующей-очередной. Установка туда ферзя уже не засчитывается, как перебор, так как "очередной" столбец D имеет три свободные клетки. Внеочередную установку ферзя в F4 я называю - реверсом.
Установкой ферзя F4 - замечательным образом мы заодно выбьем клетку D2 с которой бы начался классический перебор на 4-го ферзя. Но тут уже видно, что следующим кандидатом на ферзя будет клетка H7, поскольку она осталась единственной в колонке H.
Проставив H7 мы атакуем клетку G6. И в следствии атаки на G6 возникает ситуация, что строка №6 не имеет ферзя, но все клетки строки №6 являются атакованными. В данном случае после установки пятого ферзя, выясняется, что данная комбинация не имеет продолжения, два ферзя F4 и H7 снимаются с доски, ферзь с C5 перемещается на C6.
На доске после 5-го ферзя остались "не перебранными" клетки: D8, E2, E8, G2
Как бы сказал шахматист, - поставив ферзей на A1+B3+C5 - мы получаем образно выражаясь - "мат в два хода".
Классические алгоритмы по расстановке ферзей обычно движутся строго линейно, и циклично осуществляют маркировки атак "вперед". В моём алгоритме все маркировки атак заготовлены заранее и предусматривают маркировку атак "назад".
Хардкорные битово-арифметические операции мне позволяют достаточно быстро производить анализ текущих атак. Новый листинг алгоритма прилагается.
using System;
//using System.Numerics.BitOperations;
using System.Runtime.InteropServices;
namespace Queen_8x8
{
delegate void Solution(int[] queens);
class Program
{
static Queen_8x8 task = new Queen_8x8();
static void Main(string[] args)
{
print("Hello Queens!");
print(":");
task.init(print_solution);
//task.init(null);
task.run();
print(":");
print("solution_count = " + task.solution_count);
print("solve_count = " + task.solve_count);
print("reverse_count = " + task.reverse_count);
print("break_count = " + task.break_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 = null;
public const int total_queens_count = 8;
public const int diag_count = total_queens_count * 2 - 1;
//public ulong markers = 0xFFFF_FFFF_FFFF_FFFF;
public int[] queens = new int[total_queens_count];
int current_queens_count = 0;
ulong[] diag_LR = new ulong[diag_count];
ulong[] diag_RL = new ulong[diag_count];
public ulong attacks_VT = 0; // атака по вертикали
public ulong attacks_VZ = 0;
public ulong attacks_HZ = 0; // атака по горизонтали
public ulong attacks_HT = 0;
public ulong attacks_LR = 0; // атака по диагонали BL-TR [\]
public ulong attacks_RL = 0; // атака по диагонали BR-TL [/]
// Инверсные атаки по диагоналям. X и Y меняются местами
// Введедены для последующего быстрого суммирования атак по строкам
public ulong attacks_LRZ = 0;
public ulong attacks_RLZ = 0;
// Statisticks
public int solution_count = 0;
public int solve_count = 0;
public int reverse_count = 0;
public int break_count = 0;
static void print(String s)
{
Console.WriteLine(s);
}
private int get_LR(int x, int y) { return x + y; }
private int get_RL(int x, int y) { return (total_queens_count - 1 - x) + y; }
private void reset()
{
solution_count = 0;
solve_count = 0;
reverse_count = 0;
break_count = 0;
current_queens_count = 0;
attacks_VT = 0;
attacks_HT = 0;
attacks_HZ = 0;
attacks_VZ = 0;
attacks_LR = 0;
attacks_RL = 0;
attacks_LRZ = 0;
attacks_RLZ = 0;
for (int i = 0; i < queens.Length; i++)
{
queens[i] = -1;
}
current_queens_count = 0;
}
public void run()
{
reset();
solve();
}
public void init(Solution solution)
{
this.solution = solution;
for (int i = 0; i < diag_count; i++)
{
diag_LR[i] = 0;
diag_RL[i] = 0;
}
for (int x = 0; x < total_queens_count; x++)
{
for (int y = 0; y < total_queens_count; y++)
{
ulong mask = 1UL << ((x << 3) + y);
diag_LR[get_LR(x, y)] |= mask;
diag_RL[get_RL(x, y)] |= mask;
}
}
}
protected void step(int qx, int qy)
{
ulong a_VT = 0xFFUL << (qx << 3);
ulong a_HT = 0xFFUL << (qy << 3);
ulong a_VZ = 0x0101_0101_0101_0101UL << qx;
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)];
ulong a_LRZ = diag_LR[get_LR(qy, qx)];
ulong a_RLZ = diag_RL[get_RL(qy, qx)];
// Set Queeen
++current_queens_count;
queens[qx] = qy;
attacks_VT |= a_VT;
attacks_HT |= a_HT;
attacks_HZ |= a_HZ;
attacks_VZ |= a_VZ;
attacks_LR |= a_LR;
attacks_RL |= a_RL;
attacks_LRZ |= a_LRZ;
attacks_RLZ |= a_RLZ;
// Recurse
solve();
// Remove Queeen
attacks_VT &= ~a_VT;
attacks_HT &= ~a_HT;
attacks_HZ &= ~a_HZ;
attacks_VZ &= ~a_VZ;
attacks_LR &= ~a_LR;
attacks_RL &= ~a_RL;
attacks_LRZ &= ~a_LRZ;
attacks_RLZ &= ~a_RLZ;
queens[qx] = -1;
--current_queens_count;
}
protected void solve()
{
if (current_queens_count == total_queens_count)
{
++solution_count;
solution?.Invoke(queens);
return;
}
// Проверка по столбцам
ulong attacks_v = attacks_HZ | attacks_VT | attacks_LR | attacks_RL;
// Получаем в каждом байте 64-разрядного числа -
// сумму занятых мест по столбцам
// Каждый байт обозначает столбец таблицы и содержит число
// атак в интервале от 0 до 8
ulong sum_vec_8_columns = BitOp.popcnt64_bv(attacks_v);
// Проверка, что остались незаполненные столбцы
// Определяем что в каком либо столбце присуствует число 8
// Если в каком-либо столбце присутствует число 8,
// то общее значение теста станет ненулевым
ulong test = sum_vec_8_columns & 0x0808_0808_0808_0808UL; // Маскируем байты для обнаружения числа 8
test &= ~attacks_VT; // Отбрасывем столбцы (columns), где уже установлены ферзи
if (test != 0)
{
++break_count;
return; // Нашёлся столбец, куда невозможно установить ферзя
}
// Проверка по строкам
ulong attacks_h = attacks_HT | attacks_VZ | attacks_LRZ | attacks_RLZ;
// Получаем в каждом байте 64-разрядного числа -
// сумму занятых мест по строкам
// Каждый байт обозначает строку таблицы и содержит число
// атак в интервале от 0 до 8
ulong sum_vec_8_rows = BitOp.popcnt64_bv(attacks_h);
test = sum_vec_8_rows & 0x0808_0808_0808_0808UL; // Маскируем байты для обнаружения числа 8
test &= ~attacks_HT; // Отбрасывем строки (rows), где уже установлены ферзи
if (test != 0)
{
++break_count;
return; // Нашлась строка, куда невозможно установить ферзя
}
int qx, qy;
ulong column, row;
// Проверка, на то что есть столбцы, только с одим возможным ходом
// Поскольку мы отбросили вариант, что в столбцах присутствует число 8
// прибавляем к каждому столбцу единицу и опять проверяем все столбцы
// на наличие числа 8
// Если изначально в каком-либо столбце присутствовало число 7,
// то общее значение теста станет ненулевым
test = sum_vec_8_columns + 0x0101_0101_0101_0101UL;
test &= 0x0808_0808_0808_0808UL & ~attacks_VT;
if (test != 0)
{
++reverse_count;
qx = BitOp.bsf64((test >> 3)) >> 3;
column = (~attacks_v >> (qx << 3)) & 0xFFUL;
qy = BitOp.bsf64(column);
step(qx, qy);
return;
}
// Аналогичным образом, проверяем, что есть такая строка в которую можно
// поставить только одного ферзя
test = sum_vec_8_rows + 0x0101_0101_0101_0101UL;
test &= 0x0808_0808_0808_0808UL & ~attacks_HT;
if (test != 0)
{
++reverse_count;
qy = BitOp.bsf64((test >> 3)) >> 3;
row = (~attacks_h >> (qy << 3)) & 0xFFUL;
qx = BitOp.bsf64(row);
step(qx, qy);
return;
}
// Делаем перебор по столбцу
test = sum_vec_8_columns + 0x0202_0202_0202_0202UL;
test &= 0x0808_0808_0808_0808UL & ~attacks_VT;
if (test != 0)
{
qx = BitOp.bsf64((test >> 3)) >> 3;
}
else
{
qx = BitOp.bsf64(~attacks_VT) >> 3;
}
//--
column = (~attacks_v >> (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) // 6-итерационный проход
{
if ((value & (mask >>= step)) == 0)
{
value >>= step;
bitpos |= step;
}
}
return bitpos;
}
}
}
2056 ./ 592 = 3,5 - Сокращение вариантов перебора.
2056 - как говорилось в предыдущей статье, количество. шагов перебора без моего позиционного анализа.
Если двигать первого ферзя только по клеткам A1-A4, кол-во переборов уменьшается вдвое
592 / 2 = 296
Я предварительно для статьи пытаюсь убрать из алгоритма всё обрамление и мои исследования, чтобы осталась только чистая логика оптимизации.
P.S. Продолжение возможно последует...
