using System;
namespace Queen_8x8
{
delegate void Solution(int[] queens);
class Program
{
static void Main(string[] args)
{
var watch = System.Diagnostics.Stopwatch.StartNew();
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);
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds;
Console.WriteLine(elapsedMs + " milliseconds");
}
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.bsr64((test >> 3)) >> 3;
column = (~attacks >> (qx << 3)) & 0xFFUL;
qy = BitOp.bsr64(column);
step(qx, qy);
return;
}
// Делаем перебор по столбцу
qx = BitOp.bsr64(markers) >> 3;
column = (~attacks >> (qx << 3)) & 0xFFUL;
while (column != 0)
{
solve_count++;
qy = BitOp.bsr64(column);
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 bsr64(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;
}
}
}
