5
\$\begingroup\$

I wrote a quick sodoku solver as an exercise and am curious how to make it faster. Parsing and printing is largely irrelevant only there for readability. How can I make the code cleaner and faster?

#include <array>
#include <tuple>
#include <bitset>
#include <cassert>
#include <optional>
#include <iostream>

constexpr std::size_t blocks_per_side = 3;
constexpr std::size_t numbers = blocks_per_side * blocks_per_side;
using Value = std::bitset<numbers>;
using Row = std::array<Value, numbers>;
using Grid = std::array<Row, numbers>;
using NiceRow = std::array<std::size_t, numbers>;
using NiceGrid = std::array<NiceRow, numbers>;

namespace MapArrayDetail
{
template <std::size_t index, typename Callable, typename... Args>
constexpr auto MapIndex(const Callable& cal, const Args&... args)
{
    return cal(std::get<index>(args)...);
}

template <typename OutType, std::size_t size, typename Callable,
    std::size_t... Is, typename... Arrays>
constexpr std::array<OutType, size> MapWithIndex(
    const Callable& cal, std::index_sequence<Is...>, const Arrays&... arrays)
{
    return {MapIndex<Is>(cal, arrays...)...};
}
}

template <typename Callable, typename... Arrays>
constexpr auto Map(const Callable& cal, const Arrays&... arrays)
{
    using OutType =
        std::invoke_result_t<decltype(cal), typename Arrays::value_type...>;
    constexpr auto size =
        std::get<0>(std::make_tuple(std::tuple_size_v<Arrays>...));
    return MapArrayDetail::MapWithIndex<OutType, size>(
        cal, std::make_index_sequence<size>(), arrays...);
}

constexpr Value DeSerialize(std::size_t s)
{
    Value v{};
    if (s != 0) {
        v.set(s - 1);
    }
    return v;
}

std::size_t Serialize(Value s)
{
    assert(s.count() <= 1);
    for (std::size_t v = 0; v < numbers; v++) {
        if (s[v]) {
            return v + 1;
        }
    }
    return 0;
}

constexpr Grid DeSerialize(NiceGrid nice)
{
    return Map(
        [](const auto& r) constexpr {
            return Map([](const auto& v) constexpr { return DeSerialize(v); },
                r);
        },
        nice);
}

NiceGrid Serialize(Grid g)
{
    return Map(
        [](const auto& r) -> NiceRow {
            return Map([](const auto& v) { return Serialize(v); }, r);
        },
        g);
}

void print(NiceGrid g)
{
    for (std::size_t row = 0; row < numbers; row++) {
        for (std::size_t col = 0; col < numbers; col++) {
            std::cout << g[row][col] << ",";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

constexpr Row GetRow(const Grid& grid, std::size_t i) { return grid.at(i); }

template <std::size_t... indexes>
constexpr Row GetColImpl(
    const Grid& grid, std::size_t i, std::index_sequence<indexes...>)
{
    return {grid[indexes][i]...};
}

constexpr Row GetCol(const Grid& grid, std::size_t i)
{
    return GetColImpl(grid, i, std::make_index_sequence<numbers>());
}

template <std::size_t i>
using ValFromIndex = Value;

template <std::size_t... indexes>
constexpr std::tuple<ValFromIndex<indexes>...> GetBlockCol(const Grid& grid,
    std::size_t row, std::size_t top_col, std::index_sequence<indexes...>)
{
    return {grid.at(row).at(top_col + indexes)...};
}

template <std::size_t... indexes>
constexpr Row GetBlockImpl(const Grid& grid, std::size_t row, std::size_t col,
    std::index_sequence<indexes...>)
{
    constexpr auto seq = std::index_sequence<indexes...>{};
    const auto top_row = (row / blocks_per_side) * blocks_per_side;
    const auto top_col = (col / blocks_per_side) * blocks_per_side;
    return std::apply([](const auto&... v) { return Row{v...}; },
        std::tuple_cat(GetBlockCol(grid, top_row + indexes, top_col, seq)...));
}

constexpr Row GetBlock(const Grid& grid, std::size_t row, std::size_t col)
{
    return GetBlockImpl(
        grid, row, col, std::make_index_sequence<blocks_per_side>());
}

Value GetRemaining(const Grid& grid, std::size_t row_ind, std::size_t col_ind)
{
    Value v{};
    constexpr auto or_op = [](const auto&... a) { return (a | ...); };
    const auto ored = Map(or_op, GetCol(grid, col_ind), GetRow(grid, row_ind),
        GetBlock(grid, row_ind, col_ind));
    for (const auto& c : ored) {
        v = v | c;
    }
    return ~v;
}

using StartStop = std::tuple<std::size_t, std::size_t, Value>;
constexpr StartStop start{numbers + 1, numbers + 1, {}};
StartStop GetMinPos(const Grid& grid)
{
    auto count = 2 * numbers;
    StartStop row_col = start;
    for (std::size_t row = 0; row < numbers; row++) {
        for (std::size_t col = 0; col < numbers; col++) {
            if (grid[row][col].none()) {
                auto r = GetRemaining(grid, row, col);
                const auto rcount = r.count();
                if (rcount < count) {
                    count = rcount;
                    row_col = {row, col, r};
                }
            }
        }
    }
    return row_col;
}

bool Done(const Grid& g)
{
    constexpr auto row_has_zero = [](const Row& r) {
        return std::find_if(r.begin(), r.end(),
                   [](const auto& a) { return a.none(); }) != r.end();
    };
    return std::find_if(g.begin(), g.end(), row_has_zero) == g.end();
}

std::optional<Grid> BruteForce(const Grid& g)
{
    if (Done(g)) {
        return g;
    }
    const auto[row, col, val] = GetMinPos(g);
    if ((row > numbers) | val.none()) {
        return std::nullopt;
    }
    for (std::size_t i = 0; i < numbers; i++) {
        if (val[i]) {
            auto g2 = g;
            assert(g2[row][col].count() == 0);
            g2[row][col].set(i);
            auto res = BruteForce(g2);
            if (res) {
                return res;
            }
        }
    }
    return std::nullopt;
}

constexpr NiceGrid ex1_nice{
NiceRow{4, 0, 3, 0, 0, 0, 7, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 9}, 
    {7, 0, 0, 0, 1, 9, 3, 4, 8},
    {0, 0, 0, 7, 4, 0, 0, 0, 3}, 
    {0, 0, 4, 0, 0, 0, 1, 0, 0},
    {8, 0, 0, 0, 2, 3, 0, 0, 0}, 
    {1, 6, 7, 3, 9, 0, 0, 0, 2},
    {3, 0, 0, 0, 0, 0, 0, 0, 0}, 
    {0, 5, 2, 0, 0, 0, 6, 0, 1}};

const Grid ex1 = DeSerialize(ex1_nice);

int main(int argc, char** argv)
{
    auto z = BruteForce(ex1);
    if (!z) {
        std::cout << "Failed" << std::endl;
    }
    print(Serialize(*z));
}
\$\endgroup\$
  • \$\begingroup\$ Do you want a faster solution without changing strategy (brute force), or is a complete re-write an option? \$\endgroup\$ – dfhwze Jun 18 at 15:49
  • \$\begingroup\$ I'm interested in all options, potentially I might wish to extend it to be 16*16 however \$\endgroup\$ – Bomaz Jun 18 at 15:52
1
\$\begingroup\$

I've put this through a profiler (the built in one in VS2017), though I had to significantly amplify the signal by doing 10k calls to the solver, otherwise it is too quick. It's also quite a simple puzzle, here is a harder one for this type of solver:

constexpr NiceGrid ex2_nice{
NiceRow{0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 3, 0, 8, 5},
    {0, 0, 1, 0, 2, 0, 0, 0, 0},
    {0, 0, 0, 5, 0, 7, 0, 0, 0},
    {0, 0, 4, 0, 0, 0, 1, 0, 0},
    {0, 9, 0, 0, 0, 0, 0, 0, 0},
    {5, 0, 0, 0, 0, 0, 0, 7, 3},
    {0, 0, 2, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 4, 0, 0, 0, 9} };

The main result is that most time is spent calling GetMinPos and GetRemaining (85%), which down the line spends a significant amount of time in GetBlockImpl. Of course GetRemaining is expected to take some time as it does a significant amount of useful work, but GetBlockImpl - that's not so good. Apparently MSVC could not see the forest through the C++ templated algorithm trees. You probably won't like this suggestion if you like writing this style of C++, but I recommend not trying to be so clever with index sequences and apply and so on and just write raw loops.. With that change, not only is there less code, the solver now takes about one third of the time, bringing it down from 0.15ms per solve to 0.05ms on my PC for the easy puzzle, and from 60ms down to 20ms for the hard puzzle.

There are algorithmic tricks too. A common principle for solving constraint satisfaction problems is to try the most-constrained variable first (MCV), while choosing the least-constraining value (LCV). These may sound like opposites, but they're not. The goal of both of them is "move pruning up in the tree". MCV moves pruning up by trying to make hard choices early, leaving "easy decisions" for later, hoping that hard choices lead to contradictions early. LCV moves pruning up by trying to "make later choices easier".

Pruning high in the tree means the effect of skipping a branch is as high as possible, skipping as much of the search space as possible. In order to do this, the entire approach of GetRemaining would have to change, since the MCV branching heuristic needs access to the current "set of possibilities" for all cells so it can choose which of them to work on. Calling GetRemaining on all cells is a waste, instead an other technique can be used: maintaining the sets at all times, removing options when a cell in the same row/col/block is filled in and restoring them when un-filling the cell.

Additionally, the sets of remaining possibilities per cell may be filtered down more by looking for Naked Pairs, Hidden Pairs, Hidden Singles, and so forth. Naked Singles are even picked up by MCV automatically, but why recurse when you can filter. Using the Dual Sets can help with some of these. A dual set is a set associated with a value, indicating which cell(s) of a row/col/block it can go into (in contrast with the primal sets: for each cell, the set of values it can have). A Hidden Single for example would take a non-trivial algorithm to detect in the primal sets, but in the dual sets a Hidden Single manifests as a singleton set which is trivial to detect. In the extreme, full all_different global constraint pruning can be applied to every column, row, and block.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.