Skip to content

Instantly share code, notes, and snippets.

@jin-x

jin-x/queen_dance1.cpp

Last active June 6, 2021 09:48
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jin-x/9cc9e85ae356c1bd25ab1eefd8210d70 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jin-x/9cc9e85ae356c1bd25ab1eefd8210d70 to your computer and use it in GitHub Desktop.
Download ZIP
@jinxonik / UniLecs #270
Raw
queen_dance1.cpp
/***********************************************************************************************************************
Задача UniLecs №270: https://telegra.ph/Anons-270-SHahmatnyj-ehtyud-05-21
Алгоритм №1 решения задачи о ферзях (самый быстрый и минималистичный по коду и использованию памяти).
Будем расставлять по 1 ферзю в каждом ряду доски. Сначала будем перебирать позиции первого ряда (с некоторой поправкой,
см. ниже), затем рекурсивно второго, третьего и т.д. Для хранения информации о недоступных позициях (позициях, находящихся
под ударом других ферзей) заведём 3 переменные: busy_x (занятые вертикальные колонки), busy_ldiag (занятые колонки левой
диагонали для текущего ряда), busy_rdiag (занятые колонки правой диагонали для текущего ряда). Данные в этих переменных
будут храниться побитно (0-й бит - 1-я колонка, 1-й бит - 2-я колонка и т.д.), значение 0 будет означать, что клетка в
определённой позиции текущего ряда не находится под ударом, значение 1 - что она находится под ударом.
Итак, первый ряд мы будем заполнять, перебирая колонки только до середины (для нечётной ширины доски - без учёта средней
колонки), поскольку все расстановки могут быть зеркально отражены по горизонтали. После вычисления кол-ва вариантов
расстановок, результат будет удвоен. Для нечётной ширины доски дополнительно добавим кол-во вариантов расстановок для
средней колонки (без удвоения). Для первого ряда принимаем busy_x = busy_ldiag = busy_rdiag = 1 и вызываем рекурсивную
функцию go_deeper для следующего ряда.
Функция go_deeper проверяет номер ряда, и если он выходит за пределы доски, считает, что все ферзи расставлены, и
увеличивает счётчик вариантов расстановок, после чего завершает работу. В противном случае функция сдвигает позиции
колонок левой диагонали влево (busy_ldiag >>= 1 - здесь сдвиг вправо, т.к. нумерация битов идёт в обратном порядке),
а позиции колонок правой диагонали вправо (busy_rdiag <<= 1), после чего объединяет все 3 переменные занятости в одну
(busy = busy_x | busy_ldiag | busy_rdiag), т.к. все три переменные отражают занятость колонок именно для текущего ряда.
После этого функция перебирает все колонки текущего ряда, и когда бит busy соответствующей колонки не установлен (что
означает, что клетка не находится под ударом), вызывает рекурсивно саму себя для нижеследующего ряда, передав также
обновлённые значения busy_x, busy_ldiag и busy_rdiag.
После завершения всех переборов функция возвращает значение счётчика вариантов расстановок.
***********************************************************************************************************************/
#include <cstdint>
// Maximum number of queens (and also maximum size of chessboard), not more than 32
const unsigned MAX_QUEENS = 20;
// Type of 'busy' parameters
using BusyType = uint32_t;
static_assert(MAX_QUEENS >= 1 && MAX_QUEENS <= 32, "MAX_QUEENS must be in range from 1 to 32 !!!");
// Queen task class
class QueenDance
{
public:
// Calculate number queen placement variats for chessboard 'size x size' (with 'size' queens)
size_t get_count(unsigned size);
private:
// Internal calculation function
void go_deeper(unsigned y, BusyType busy_x, BusyType busy_ldiag, BusyType busy_rdiag);
// Variables (attributes)
unsigned m_size; // chessboard size
size_t m_count; // placement counter
}; // class QueenDance
size_t QueenDance::get_count(unsigned size)
{
// Check size
if (size < 1 || size > MAX_QUEENS) { return 0; }
// Save size and reset counter
m_size = size;
m_count = 0;
// Place queen in each column position on the left chessboard half of the 1st row
for (unsigned bit_x = 1, limit = 1 << ((size+1)/2), middle = 1 << (size/2-1); bit_x != limit; bit_x <<= 1) {
// Place queen here and try to place another queen in a row below
go_deeper(1, bit_x, bit_x, bit_x);
// Double placement counter for right row (and do one more iteration for middle column if size is odd)
if (bit_x == middle) { m_count *= 2; }
}
// Return result
return m_count;
} // QueenDance::get_count
void QueenDance::go_deeper(unsigned y, BusyType busy_x, BusyType busy_ldiag, BusyType busy_rdiag)
{
// Check the row
if (y == m_size) { // maximum depth is reached (all queens are placed)
++m_count;
return;
}
// Shift left diagonals left, right diagonals right (because of increasing row) and join all busy positions
busy_ldiag >>= 1;
busy_rdiag <<= 1;
unsigned busy = busy_x | busy_ldiag | busy_rdiag;
// Try to place queen in each column position of 'next_y' row
for (unsigned bit_x = 1, limit = 1 << m_size; bit_x != limit; bit_x <<= 1) {
if ((busy & bit_x) == 0) { // is position free?
// Place queen here and try to place another queen in a row below
go_deeper(y + 1, busy_x | bit_x, busy_ldiag | bit_x, busy_rdiag | bit_x);
}
}
} // QueenDance::go_deeper
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <chrono>
using std::cout;
using std::endl;
int main()
{
QueenDance qd;
for (unsigned i = 0; i <= MAX_QUEENS; ++i) {
// Start time measurement
using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
auto start_time = Clock::now();
// Calculate
size_t count = qd.get_count(i);
// Finish time measurement
auto stop_time = Clock::now();
double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();
// Display results
cout << "Chessboard " << i << 'x' << i << ": " << count << " (" << std::fixed << duration << " sec)" << endl;
}
} // main
Raw
queen_dance1_multithread.cpp
/***********************************************************************************************************************
Задача UniLecs №270: https://telegra.ph/Anons-270-SHahmatnyj-ehtyud-05-21
Алгоритм №1 решения задачи о ферзях (самый быстрый и минималистичный по коду и использованию памяти).
Модифицированный многопоточный алгоритм (примитивный вариант многопоточности).
Будем расставлять по 1 ферзю в каждом ряду доски. Сначала будем перебирать позиции первого ряда (с некоторой поправкой,
см. ниже), затем рекурсивно второго, третьего и т.д. Для хранения информации о недоступных позициях (позициях, находящихся
под ударом других ферзей) заведём 3 переменные: busy_x (занятые вертикальные колонки), busy_ldiag (занятые колонки левой
диагонали для текущего ряда), busy_rdiag (занятые колонки правой диагонали для текущего ряда). Данные в этих переменных
будут храниться побитно (0-й бит - 1-я колонка, 1-й бит - 2-я колонка и т.д.), значение 0 будет означать, что клетка в
определённой позиции текущего ряда не находится под ударом, значение 1 - что она находится под ударом.
Итак, первый ряд мы будем заполнять, перебирая колонки только до середины (для нечётной ширины доски - без учёта средней
колонки), поскольку все расстановки могут быть зеркально отражены по горизонтали. После вычисления кол-ва вариантов
расстановок, результат будет удвоен. Для нечётной ширины доски дополнительно добавим кол-во вариантов расстановок для
средней колонки (без удвоения). Для первого ряда принимаем busy_x = busy_ldiag = busy_rdiag = 1 и вызываем рекурсивную
функцию go_deeper для следующего ряда. Для размера доски 12 клеток и более вызовы функций go_deeper из главной функции
get_count производятся в отдельных потоках (многопоточный режим). Также в этой модификации алгоритма вместо одного
счётчика вариантов расстановок используется несколько счётчиков, кол-во которых соответствует кол-ву вызовов go_deeper
из функции get_count. Это сделано для того, чтобы не нарушалось корректное увеличение счётчиков из-за многопоточности
(атомарное увеличение одного счётчика, судя по тестам, требует большего расхода ресурсов), плюс так легче считать
итоговое значение для досок нечётного размера (где удвоение результата используется не для всех столбцов).
Функция go_deeper проверяет номер ряда, и если он выходит за пределы доски, считает, что все ферзи расставлены, и
увеличивает счётчик вариантов расстановок, после чего завершает работу. В противном случае функция сдвигает позиции
колонок левой диагонали влево (busy_ldiag >>= 1 - здесь сдвиг вправо, т.к. нумерация битов идёт в обратном порядке),
а позиции колонок правой диагонали вправо (busy_rdiag <<= 1), после чего объединяет все 3 переменные занятости в одну
(busy = busy_x | busy_ldiag | busy_rdiag), т.к. все три переменные отражают занятость колонок именно для текущего ряда.
После этого функция перебирает все колонки текущего ряда, и когда бит busy соответствующей колонки не установлен (что
означает, что клетка не находится под ударом), вызывает рекурсивно саму себя для нижеследующего ряда, передав также
обновлённые значения busy_x, busy_ldiag и busy_rdiag.
После завершения всех переборов функция возвращает значение счётчика вариантов расстановок.
***********************************************************************************************************************/
#include <cstdint>
#include <numeric>
#include <vector>
#include <thread>
// Maximum number of queens (and also maximum size of chessboard), not more than 32
const unsigned MAX_QUEENS = 18;
// Type of 'busy' parameters
using BusyType = uint32_t;
static_assert(MAX_QUEENS >= 1 && MAX_QUEENS <= 32, "MAX_QUEENS must be in range from 1 to 32 !!!");
// Queen task class
class QueenDance
{
public:
// Calculate number queen placement variats for chessboard 'size x size' (with 'size' queens)
size_t get_count(unsigned size);
private:
// Internal calculation function
void go_deeper(unsigned y, BusyType busy_x, BusyType busy_ldiag, BusyType busy_rdiag, size_t& counter);
// Variables (attributes)
unsigned m_size; // chessboard size
}; // class QueenDance
size_t QueenDance::get_count(unsigned size)
{
// Check size
if (size < 1 || size > MAX_QUEENS) { return 0; }
// Save chessboard size
m_size = size;
// Vector of threads and counters
std::vector<std::thread> threads;
std::vector<size_t> counters((size+1)/2);
// Place queen in each column position on the left chessboard half of the 1st row
for (unsigned i = 0, bit_x = 1, limit = 1 << ((size+1)/2); bit_x != limit; ++i, bit_x <<= 1) {
// Place queen here and try to place another queen in a row below
if (size < 12) { go_deeper(1, bit_x, bit_x, bit_x, counters[i]); } // single thread
else { threads.emplace_back(&QueenDance::go_deeper, this, 1, bit_x, bit_x, bit_x, std::ref(counters[i])); } // multithread
}
// Wait for threads to finish (if any)
for (auto& thread : threads) {
thread.join();
}
// Double placement counter for right row (and subtract the last if 'size' is odd)
size_t result = std::accumulate(counters.begin(), counters.end(), size_t(0)) * 2;
if ((size & 1) != 0) { result -= counters.back(); }
// Return result (sum of counter)
return result;
} // QueenDance::get_count
void QueenDance::go_deeper(unsigned y, BusyType busy_x, BusyType busy_ldiag, BusyType busy_rdiag, size_t& counter)
{
// Check the row
if (y == m_size) { // maximum depth is reached (all queens are placed)
++counter;
return;
}
// Shift left diagonals left, right diagonals right (because of increasing row) and join all busy positions
busy_ldiag >>= 1;
busy_rdiag <<= 1;
unsigned busy = busy_x | busy_ldiag | busy_rdiag;
// Try to place queen in each column position of 'next_y' row
for (unsigned bit_x = 1, limit = 1 << m_size; bit_x != limit; bit_x <<= 1) {
if ((busy & bit_x) == 0) { // is position free?
// Place queen here and try to place another queen in a row below
go_deeper(y + 1, busy_x | bit_x, busy_ldiag | bit_x, busy_rdiag | bit_x, counter);
}
}
} // QueenDance::go_deeper
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <chrono>
using std::cout;
using std::endl;
int main()
{
QueenDance qd;
for (unsigned i = 0; i <= MAX_QUEENS; ++i) {
// Start time measurement
using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
auto start_time = Clock::now();
// Calculate
size_t count = qd.get_count(i);
// Finish time measurement
auto stop_time = Clock::now();
double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();
// Display results
cout << "Chessboard " << i << 'x' << i << ": " << count << " (" << std::fixed << duration << " sec)" << endl;
}
} // main
Raw
queen_dance2.cpp
/***********************************************************************************************************************
Задача UniLecs №270: https://telegra.ph/Anons-270-SHahmatnyj-ehtyud-05-21
Алгоритм №2 решения задачи о ферзях.
Будем расставлять по 1 ферзю в каждом ряду доски. Сначала будем перебирать позиции первого ряда (с некоторой поправкой,
см. ниже), затем рекурсивно второго, третьего и т.д. Для хранения информации о доступности позиций заведём массив board,
хранящий информацию о каждой клетке шахматной доски (0 - доступна, 1 - под ударом), которую будем заполнять после
установки каждого ферзя. Причём, заполнять будем только нижние ряды, т.к. в текущий и вышестоящие ряды мы других ферзей
ставить уже не будем. Для сокращения объёма памяти используется массив значений типа uint16_t (для размеров доски до 16
клеток) или uint32_t (до 32 клеток), каждый элемент которого соответствует ряду, а отдельные биты - колонкам (клеткам в
этом ряду).
Итак, первый ряд мы будем заполнять, перебирая колонки только до середины (для нечётной ширины доски - без учёта средней
колонки), поскольку все расстановки могут быть зеркально отражены по горизонтали. После вычисления кол-ва вариантов
расстановок, результат будет удвоен. Для нечётной ширины доски дополнительно добавим кол-во вариантов расстановок для
средней колонки (без удвоения).
Сначала заполним массив board всех нижних рядов единичными значениями в текущей колонке, а также по диагоналям (правой и
левой). После заполнения вызываем рекурсивную функцию go_deeper для следующего (нижерасположенного) ряда. Данная функция
проверяет номер ряда, и если он выходит за пределы доски, считает, что все ферзи расставлены, и увеличивает счётчик
вариантов расстановок, после чего завершает работу. В противном случае функция перебирает все клетки нового ряда по
горизонтали, проверяя их доступность. В случае доступности она также заполняет вертикальные и диагональные линии нижних
рядов массива board и вызывает саму себя для нижеследующего ряда.
После завершения всех переборов функция возвращает значение счётчика вариантов расстановок.
***********************************************************************************************************************/
#include <cstdint>
#include <type_traits>
#include <array>
// Maximum number of queens (and also maximum size of chessboard), not more than 32
const unsigned MAX_QUEENS = 16;
// 16-bit unsigned int for MAX_QUEENS <= 16, else 32-bit unsigned int
using BoardType = std::conditional_t<MAX_QUEENS <= 16, uint16_t, uint32_t>;
static_assert(MAX_QUEENS >= 1 && MAX_QUEENS <= 32, "MAX_QUEENS must be in range from 1 to 32 !!!");
// Queen task class
class QueenDance
{
public:
// Calculate number queen placement variats for chessboard 'size x size' (with 'size' queens)
size_t get_count(unsigned size);
private:
// Internal calculation function
inline void go_deeper(unsigned next_y, const std::array<BoardType,MAX_QUEENS>& board);
// Fill chessboard (verticals and diagonals)
inline std::array<BoardType,MAX_QUEENS> fill_board(std::array<BoardType,MAX_QUEENS> board, unsigned x, unsigned y);
// Variables (attributes)
unsigned m_size; // chessboard size
size_t m_count; // placement counter
}; // class QueenDance
size_t QueenDance::get_count(unsigned size)
{
// Check size
if (size < 1 || size > MAX_QUEENS) { return 0; }
// Save size and reset counter
m_size = size;
m_count = 0;
// Place queen in each column position on the left chessboard half of the 1st row
for (unsigned x = 0, limit = (size + 1) / 2, middle = size / 2 - 1; x < limit; ++x) {
// Fill chessboard (place queen here) and try to place another queen in a row below
go_deeper(1, fill_board({}, x, 0));
// Double placement counter for right row (and do one more iteration for middle column if size is odd)
if (x == middle) { m_count *= 2; }
}
// Return result
return m_count;
} // QueenDance::get_count
void QueenDance::go_deeper(unsigned next_y, const std::array<BoardType,MAX_QUEENS>& board)
{
// Check the row
if (next_y == m_size) { // maximum depth is reached (all queens are placed)
++m_count;
return;
}
// Try to place queen in each column position of 'next_y' row
for (unsigned x = 0; x < m_size; ++x) {
if ((board[next_y] & (1 << x)) == 0) { // is position free?
// Fill chessboard (place queen here) and try to place another queen in a row below
go_deeper(next_y + 1, fill_board(board, x, next_y));
}
}
} // QueenDance::go_deeper
std::array<BoardType,MAX_QUEENS> QueenDance::fill_board(std::array<BoardType,MAX_QUEENS> board, unsigned x, unsigned y) {
++y; // start from the next row
for (unsigned shift = 1; y < m_size; ++y, ++shift) { // move down
board[y] |= 1 << x; // fill vertical cells
if (x+shift < m_size) { board[y] |= 1 << (x+shift); } // fill right diagonal cells
if (x-shift < m_size) { board[y] |= 1 << (x-shift); } // fill left diagonal cells
}
return board;
} // QueenDance::fill_board
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <chrono>
using std::cout;
using std::endl;
int main()
{
QueenDance qd;
for (unsigned i = 0; i <= MAX_QUEENS; ++i) {
// Start time measurement
using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
auto start_time = Clock::now();
// Calculate
size_t count = qd.get_count(i);
// Finish time measurement
auto stop_time = Clock::now();
double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();
// Display results
cout << "Chessboard " << i << 'x' << i << ": " << count << " (" << std::fixed << duration << " sec)" << endl;
}
} // main
Raw
results-queen_dance1-x64.txt
clang version 10.0.0 x86_64-pc-windows-msvc:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000000 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000007 sec)
Chessboard 8x8: 92 (0.000023 sec)
Chessboard 9x9: 352 (0.000107 sec)
Chessboard 10x10: 724 (0.000407 sec)
Chessboard 11x11: 2680 (0.002151 sec)
Chessboard 12x12: 14200 (0.010748 sec)
Chessboard 13x13: 73712 (0.056674 sec)
Chessboard 14x14: 365596 (0.309031 sec)
Chessboard 15x15: 2279184 (2.121441 sec)
Chessboard 16x16: 14772512 (13.419855 sec)
gcc version 10.1.0 (Rev3, Built by MSYS2 project) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000000 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000006 sec)
Chessboard 8x8: 92 (0.000020 sec)
Chessboard 9x9: 352 (0.000094 sec)
Chessboard 10x10: 724 (0.000358 sec)
Chessboard 11x11: 2680 (0.001899 sec)
Chessboard 12x12: 14200 (0.009555 sec)
Chessboard 13x13: 73712 (0.054218 sec)
Chessboard 14x14: 365596 (0.305540 sec)
Chessboard 15x15: 2279184 (2.132814 sec)
Chessboard 16x16: 14772512 (13.631294 sec)
Microsoft Visual C++ (cl 19.28.29915) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000000 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000007 sec)
Chessboard 8x8: 92 (0.000023 sec)
Chessboard 9x9: 352 (0.000109 sec)
Chessboard 10x10: 724 (0.000470 sec)
Chessboard 11x11: 2680 (0.002333 sec)
Chessboard 12x12: 14200 (0.011469 sec)
Chessboard 13x13: 73712 (0.061913 sec)
Chessboard 14x14: 365596 (0.339210 sec)
Chessboard 15x15: 2279184 (2.349046 sec)
Chessboard 16x16: 14772512 (16.210735 sec)
Raw
results-queen_dance1_multithread-x64.txt
gcc version 10.1.0 (Rev3, Built by MSYS2 project) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000004 sec)
Chessboard 2x2: 0 (0.000001 sec)
Chessboard 3x3: 0 (0.000001 sec)
Chessboard 4x4: 2 (0.000001 sec)
Chessboard 5x5: 10 (0.000002 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000007 sec)
Chessboard 8x8: 92 (0.000019 sec)
Chessboard 9x9: 352 (0.000085 sec)
Chessboard 10x10: 724 (0.000406 sec)
Chessboard 11x11: 2680 (0.001759 sec)
Chessboard 12x12: 14200 (0.005567 sec)
Chessboard 13x13: 73712 (0.017659 sec)
Chessboard 14x14: 365596 (0.090847 sec)
Chessboard 15x15: 2279184 (0.598329 sec)
Chessboard 16x16: 14772512 (3.392821 sec)
Chessboard 17x17: 95815104 (25.216607 sec)
Chessboard 18x18: 666090624 (180.188117 sec)
clang version 10.0.0 x86_64-pc-windows-msvc:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000001 sec)
Chessboard 2x2: 0 (0.000001 sec)
Chessboard 3x3: 0 (0.000001 sec)
Chessboard 4x4: 2 (0.000001 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000007 sec)
Chessboard 8x8: 92 (0.000020 sec)
Chessboard 9x9: 352 (0.000086 sec)
Chessboard 10x10: 724 (0.000323 sec)
Chessboard 11x11: 2680 (0.001705 sec)
Chessboard 12x12: 14200 (0.008075 sec)
Chessboard 13x13: 73712 (0.019841 sec)
Chessboard 14x14: 365596 (0.082950 sec)
Chessboard 15x15: 2279184 (0.596408 sec)
Chessboard 16x16: 14772512 (3.442609 sec)
Chessboard 17x17: 95815104 (25.818428 sec)
Chessboard 18x18: 666090624 (183.441666 sec)
Microsoft Visual C++ (cl 19.28.29915) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000001 sec)
Chessboard 2x2: 0 (0.000001 sec)
Chessboard 3x3: 0 (0.000001 sec)
Chessboard 4x4: 2 (0.000001 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000002 sec)
Chessboard 7x7: 40 (0.000007 sec)
Chessboard 8x8: 92 (0.000021 sec)
Chessboard 9x9: 352 (0.000093 sec)
Chessboard 10x10: 724 (0.000363 sec)
Chessboard 11x11: 2680 (0.002023 sec)
Chessboard 12x12: 14200 (0.006206 sec)
Chessboard 13x13: 73712 (0.020649 sec)
Chessboard 14x14: 365596 (0.097734 sec)
Chessboard 15x15: 2279184 (0.710544 sec)
Chessboard 16x16: 14772512 (4.298710 sec)
Chessboard 17x17: 95815104 (32.645197 sec)
Chessboard 18x18: 666090624 (234.670111 sec)
Raw
results-queen_dance2-x64.txt
gcc version 10.1.0 (Rev3, Built by MSYS2 project) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000001 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000003 sec)
Chessboard 7x7: 40 (0.000010 sec)
Chessboard 8x8: 92 (0.000031 sec)
Chessboard 9x9: 352 (0.000144 sec)
Chessboard 10x10: 724 (0.000504 sec)
Chessboard 11x11: 2680 (0.002618 sec)
Chessboard 12x12: 14200 (0.012826 sec)
Chessboard 13x13: 73712 (0.079818 sec)
Chessboard 14x14: 365596 (0.449104 sec)
Chessboard 15x15: 2279184 (3.142571 sec)
Chessboard 16x16: 14772512 (19.950110 sec)
clang version 10.0.0 x86_64-pc-windows-msvc:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000000 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000003 sec)
Chessboard 7x7: 40 (0.000012 sec)
Chessboard 8x8: 92 (0.000036 sec)
Chessboard 9x9: 352 (0.000164 sec)
Chessboard 10x10: 724 (0.000631 sec)
Chessboard 11x11: 2680 (0.003364 sec)
Chessboard 12x12: 14200 (0.016739 sec)
Chessboard 13x13: 73712 (0.103579 sec)
Chessboard 14x14: 365596 (0.560437 sec)
Chessboard 15x15: 2279184 (3.863467 sec)
Chessboard 16x16: 14772512 (24.541340 sec)
Microsoft Visual C++ (cl 19.28.29915) x64:
Chessboard 0x0: 0 (0.000000 sec)
Chessboard 1x1: 1 (0.000000 sec)
Chessboard 2x2: 0 (0.000000 sec)
Chessboard 3x3: 0 (0.000000 sec)
Chessboard 4x4: 2 (0.000000 sec)
Chessboard 5x5: 10 (0.000001 sec)
Chessboard 6x6: 4 (0.000003 sec)
Chessboard 7x7: 40 (0.000012 sec)
Chessboard 8x8: 92 (0.000037 sec)
Chessboard 9x9: 352 (0.000163 sec)
Chessboard 10x10: 724 (0.000612 sec)
Chessboard 11x11: 2680 (0.003251 sec)
Chessboard 12x12: 14200 (0.015920 sec)
Chessboard 13x13: 73712 (0.098343 sec)
Chessboard 14x14: 365596 (0.552957 sec)
Chessboard 15x15: 2279184 (3.972668 sec)
Chessboard 16x16: 14772512 (25.443302 sec)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment