count-n-queens.cpp

#include <functional>
#include <future>
#include <numeric>
#include <vector>

// count the number of solutions to the n-queens problem
// could be optimized if we leveraged symmetry

int count_solutions(int size)
{
    const auto job = [size](auto first_column) {
        std::function<int(int, int, int, int)> do_count = [size, &do_count](auto row, auto left, auto down, auto right) {
            if (row == size)
            {
                return 1;
            }
            else
            {
                const auto used = ~(left | down | right);
                auto count = 0;
                for (auto bit = 1; bit != 1 << size; bit <<= 1)
                {
                    if (bit & used)
                        count += do_count(row + 1, (left | bit) << 1, down | bit, (right | bit) >> 1);
                }
                return count;
            }
        };
        const auto bit = 1 << first_column;
        return do_count(1, bit << 1, bit, bit >> 1);
    };

    std::vector<std::future<int>> futures;
    futures.reserve(size);
    for (auto col = 0; col < size; ++col)
        futures.push_back(std::async(std::launch::async, job, col));

    return std::accumulate(futures.begin(), futures.end(), 0, [](auto s, auto &job) { return s + job.get(); });
}