6
\$\begingroup\$

I just finished up a sudoku solver in C++. I originally completed a solver in Python for coursework and I wanted to see how much of a performance gain I could get. Because of this, I ended up using compiler intrinsics for MSVC, and liberal use of arrays. It ended up being a lot faster than I expected, solving most puzzles in 0-0.1 milliseconds (For reference, my naive Python code took ~20 seconds to solve the same puzzle, a speedup of roughly 50000x). From a performance standpoint, there's no reason to try to get it any faster as most of the time is being spent on overhead. However, I do have a few questions about some of the details.

#pragma once
#include <intrin.h>
#include <vector>
#include <array>
#include <string>
#pragma intrinsic(_BitScanForward)   

//
 // Sudoku Solver
 //  Solve any 9x9 game of Sudoku using sudoku::evaluate

namespace sudoku
{


    // Parameters:
    //      first - The beginning of the input range 
    // Requirements:
    //      ForwardIt must satisfy the requirements for a ForwardIterator
    //      ForwardIt's value type must be integral
    //      ForwardIt must be able to advance at least 81 times
    // Return value:
    //      Returns true if the puzzle was solved, and false if the puzzle is impossible to solve. 
    // Side effects:
    //      If the puzzle was solved successfully, then ForwardIterator contains the solved puzzle in index form
    // Notes: Values outside 1-9 are assumed to be blank
    // Exceptions:
    //      Throws std::runtime_error if hardware does not support the __popcnt instruction.
    template<typename ForwardIt>
    bool evaluate(ForwardIt first);

    //Parameters:
    //      in - input stream. New line characters are ignored. Characters 1-9 assume its value, and all other characters are assumed to be blank.
    //      out - output stream.
    //      pretty - If true, the output stream will be prettified. 
    // Return value:
    //      Returns true if the puzzle was solved, and false if the puzzle is impossible to solve. 
    // Notes:
    //      If there are less than 81 characters in the input stream, then the rest is assumed to be blank.
    //      If there are more than 81 characters in the input stream, only the first 81 characters are read.
    // Exceptions:
    //      Throws std::runtime_error if hardware does not support the __popcnt instruction.

    // Sample output if pretty is false:
    //      295743861431865927876192543387459216612387495549216738763524189928671354154938672   

    // Sample output if pretty is true:
    //      [2][9][5][7][4][3][8][6][1]
    //      [4][3][1][8][6][5][9][2][7]
    //      [8][7][6][1][9][2][5][4][3]
    //      [3][8][7][4][5][9][2][1][6]
    //      [6][1][2][3][8][7][4][9][5]
    //      [5][4][9][2][1][6][7][3][8]
    //      [7][6][3][5][2][4][1][8][9]
    //      [9][2][8][6][7][1][3][5][4]
    //      [1][5][4][9][3][8][6][7][2]
    bool evaluate(std::istream & in, std::ostream & out, const bool pretty);
}




// --------------------------------------------------------------------------------
// ------------------IMPLEMENTATION DETAILS BELOW----------------------------------
// --------------------------------------------------------------------------------
namespace sudoku
{
    // An index refers to the flattened cell of a sudoku board, in row-major order
    // i.e. index 0 <-> (0,0), index 32 <-> (3,5)

    // Domains of each cell are represented by the 32 bitset U32.
    // If bit i is set, then the domain of the cell can contain value i+1
    typedef uint32_t U32;

    // Returns the 9 indices occupying the specified block
    constexpr std::array<int, 9> block_region(const int block_index)
    {
        const auto start = 27 * (block_index / 3) + 3 * (block_index % 3);
        return std::array<int, 9>{  start, start + 1, start + 2,
            start + 9, start + 10, start + 11,
            start + 18, start + 19, start + 20 };

    }
    // Returns the 9 indices occupying the specified row
    constexpr std::array<int, 9> row_region(const int col)
    {
        return std::array<int, 9>{ col, col + 9, col + 18, col + 27, col + 36, col + 45, col + 54, col + 63, col + 72};
    }
    // Returns the 9 indices occupying the specified col
    constexpr std::array<int, 9> col_region(const int row)
    {
        return std::array<int, 9>{9 * row, 9 * row + 1, 9 * row + 2, 9 * row + 3, 9 * row + 4, 9 * row + 5, 9 * row + 6, 9 * row + 7, 9 * row + 8};
    }

    // A lookup table to find the neighbors of a given index. Index i has all neighbors stored in NEIGHBOR_TABLE[20*i : 20*i + 20)
    const int NEIGHBOR_TABLE[1620] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20, 0, 2, 3, 4, 5, 6, 7, 8, 10, 19, 28, 37, 46, 55, 64, 73, 9, 11, 18, 20, 0, 1, 3, 4, 5, 6, 7, 8, 11, 20,
        29, 38, 47, 56, 65, 74, 9, 10, 18, 19, 0, 1, 2, 4, 5, 6, 7, 8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23, 0, 1, 2, 3, 5, 6, 7, 8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23, 0, 1, 2, 3, 4, 6, 7, 8,
        14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22, 0, 1, 2, 3, 4, 5, 7, 8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26, 0, 1, 2, 3, 4, 5, 6, 8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26, 0, 1, 2, 3, 4,
        5, 6, 7, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25, 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 1, 2, 19, 20, 9, 11, 12, 13, 14, 15, 16, 17, 1, 19, 28, 37, 46, 55, 64, 73, 0, 2, 18, 20,
        9, 10, 12, 13, 14, 15, 16, 17, 2, 20, 29, 38, 47, 56, 65, 74, 0, 1, 18, 19, 9, 10, 11, 13, 14, 15, 16, 17, 3, 21, 30, 39, 48, 57, 66, 75, 4, 5, 22, 23, 9, 10, 11, 12, 14, 15, 16, 17, 4, 22, 31, 40, 49, 58, 67,
        76, 3, 5, 21, 23, 9, 10, 11, 12, 13, 15, 16, 17, 5, 23, 32, 41, 50, 59, 68, 77, 3, 4, 21, 22, 9, 10, 11, 12, 13, 14, 16, 17, 6, 24, 33, 42, 51, 60, 69, 78, 7, 8, 25, 26, 9, 10, 11, 12, 13, 14, 15, 17, 7, 25,
        34, 43, 52, 61, 70, 79, 6, 8, 24, 26, 9, 10, 11, 12, 13, 14, 15, 16, 8, 26, 35, 44, 53, 62, 71, 80, 6, 7, 24, 25, 19, 20, 21, 22, 23, 24, 25, 26, 0, 9, 27, 36, 45, 54, 63, 72, 1, 2, 10, 11, 18, 20, 21, 22, 23,
        24, 25, 26, 1, 10, 28, 37, 46, 55, 64, 73, 0, 2, 9, 11, 18, 19, 21, 22, 23, 24, 25, 26, 2, 11, 29, 38, 47, 56, 65, 74, 0, 1, 9, 10, 18, 19, 20, 22, 23, 24, 25, 26, 3, 12, 30, 39, 48, 57, 66, 75, 4, 5, 13, 14,
        18, 19, 20, 21, 23, 24, 25, 26, 4, 13, 31, 40, 49, 58, 67, 76, 3, 5, 12, 14, 18, 19, 20, 21, 22, 24, 25, 26, 5, 14, 32, 41, 50, 59, 68, 77, 3, 4, 12, 13, 18, 19, 20, 21, 22, 23, 25, 26, 6, 15, 33, 42, 51, 60,
        69, 78, 7, 8, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 7, 16, 34, 43, 52, 61, 70, 79, 6, 8, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 8, 17, 35, 44, 53, 62, 71, 80, 6, 7, 15, 16, 28, 29, 30, 31, 32, 33, 34, 35, 0,
        9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47, 27, 29, 30, 31, 32, 33, 34, 35, 1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47, 27, 28, 30, 31, 32, 33, 34, 35, 2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46, 27, 28,
        29, 31, 32, 33, 34, 35, 3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50, 27, 28, 29, 30, 32, 33, 34, 35, 4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50, 27, 28, 29, 30, 31, 33, 34, 35, 5, 14, 23, 41, 50, 59, 68,
        77, 39, 40, 48, 49, 27, 28, 29, 30, 31, 32, 34, 35, 6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53, 27, 28, 29, 30, 31, 32, 33, 35, 7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53, 27, 28, 29, 30, 31, 32, 33, 34,
        8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52, 37, 38, 39, 40, 41, 42, 43, 44, 0, 9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47, 36, 38, 39, 40, 41, 42, 43, 44, 1, 10, 19, 28, 46, 55, 64, 73, 27, 29, 45, 47, 36, 37,
        39, 40, 41, 42, 43, 44, 2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46, 36, 37, 38, 40, 41, 42, 43, 44, 3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50, 36, 37, 38, 39, 41, 42, 43, 44, 4, 13, 22, 31, 49, 58, 67,
        76, 30, 32, 48, 50, 36, 37, 38, 39, 40, 42, 43, 44, 5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49, 36, 37, 38, 39, 40, 41, 43, 44, 6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53, 36, 37, 38, 39, 40, 41, 42, 44,
        7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53, 36, 37, 38, 39, 40, 41, 42, 43, 8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52, 46, 47, 48, 49, 50, 51, 52, 53, 0, 9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38, 45, 47,
        48, 49, 50, 51, 52, 53, 1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38, 45, 46, 48, 49, 50, 51, 52, 53, 2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37, 45, 46, 47, 49, 50, 51, 52, 53, 3, 12, 21, 30, 39, 57, 66, 75,
        31, 32, 40, 41, 45, 46, 47, 48, 50, 51, 52, 53, 4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41, 45, 46, 47, 48, 49, 51, 52, 53, 5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40, 45, 46, 47, 48, 49, 50, 52, 53, 6,
        15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44, 45, 46, 47, 48, 49, 50, 51, 53, 7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43, 55, 56,
        57, 58, 59, 60, 61, 62, 0, 9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74, 54, 56, 57, 58, 59, 60, 61, 62, 1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74, 54, 55, 57, 58, 59, 60, 61, 62, 2, 11, 20, 29, 38, 47, 65, 74,
        63, 64, 72, 73, 54, 55, 56, 58, 59, 60, 61, 62, 3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77, 54, 55, 56, 57, 59, 60, 61, 62, 4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77, 54, 55, 56, 57, 58, 60, 61, 62, 5,
        14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76, 54, 55, 56, 57, 58, 59, 61, 62, 6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80, 54, 55, 56, 57, 58, 59, 60, 62, 7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80, 54, 55,
        56, 57, 58, 59, 60, 61, 8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79, 64, 65, 66, 67, 68, 69, 70, 71, 0, 9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74, 63, 65, 66, 67, 68, 69, 70, 71, 1, 10, 19, 28, 37, 46, 55, 73,
        54, 56, 72, 74, 63, 64, 66, 67, 68, 69, 70, 71, 2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73, 63, 64, 65, 67, 68, 69, 70, 71, 3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77, 63, 64, 65, 66, 68, 69, 70, 71, 4,
        13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77, 63, 64, 65, 66, 67, 69, 70, 71, 5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76, 63, 64, 65, 66, 67, 68, 70, 71, 6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80, 63, 64,
        65, 66, 67, 68, 69, 71, 7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80, 63, 64, 65, 66, 67, 68, 69, 70, 8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79, 73, 74, 75, 76, 77, 78, 79, 80, 0, 9, 18, 27, 36, 45, 54, 63,
        55, 56, 64, 65, 72, 74, 75, 76, 77, 78, 79, 80, 1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65, 72, 73, 75, 76, 77, 78, 79, 80, 2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64, 72, 73, 74, 76, 77, 78, 79, 80, 3, 12,
        21, 30, 39, 48, 57, 66, 58, 59, 67, 68, 72, 73, 74, 75, 77, 78, 79, 80, 4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68, 72, 73, 74, 75, 76, 78, 79, 80, 5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67, 72, 73, 74,
        75, 76, 77, 79, 80, 6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80, 7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 17, 26, 35, 44, 53, 62, 71,
        60, 61, 69, 70 };

    // A table to lookup bitmasks for domain values, offset by 1. (The offset value is referred to as the zval)
    const U32 MASK[9] = {
        0x00000001,
        0x00000002,
        0x00000004,
        0x00000008,
        0x00000010,
        0x00000020,
        0x00000040,
        0x00000080,
        0x00000100 };

    // A bitmask in which all zvals 0-8 are set.
    const U32 MASK_ALL = 0x000001FF;

    // Note: a REGION can be either a BLOCK, ROW, or COL.
    const std::array<int, 9> BLOCK[9] = { block_region(0), block_region(1), block_region(2),
                                            block_region(3), block_region(4), block_region(5),
                                            block_region(6), block_region(7), block_region(8) };
    const std::array<int, 9> ROW[9] = { row_region(0), row_region(1), row_region(2),
                                        row_region(3),row_region(4), row_region(5),
                                        row_region(6), row_region(7), row_region(8) };
    const std::array<int, 9> COL[9] = { col_region(0), col_region(1), col_region(2),
                                        col_region(3),col_region(4), col_region(5),
                                        col_region(6), col_region(7), col_region(8) };

    // An inference can reach 1 of 3 conclusions: Inconcistent, Inconclusive, or Solved
    // Solved : The puzzle is in a solved state
    // Inconclusive : Not enough information is given to conclude anything
    // Inconsistent : The puzzle is inconsistent and is impossible to solve
    enum class Status
    {
        Inconsistent, Inconclusive, Solved
    };

    struct Arc
    {
        int from;
        int to;
    };


    // Whenever a value is removed from the domain of an index, we need to propogate these changes to the arcs container
    inline void revise(int from, std::vector<Arc> & arcs)
    {
        for (auto i = 0; i < 20; i++)
        {
            const auto neighbor = NEIGHBOR_TABLE[20 * from + i];
            arcs.push_back(Arc{neighbor,from });
        }
    }

    // Create a container with all valid arcs
    inline std::vector<Arc> make_arcs()
    {
        std::vector<Arc> arcs;
        arcs.reserve(1800);
        for (auto i = 0; i < 1620; i++)
        {
            arcs.push_back(Arc{ i / 20, NEIGHBOR_TABLE[i] });
        }
        return arcs;
    }   

    template<typename ForwardIt>
    class SudokuBoard
    {
        friend bool evaluate<ForwardIt>(ForwardIt first);
        std::array<U32, 81> domains;
        ForwardIt first;
        explicit SudokuBoard(ForwardIt it) : first(it)
        {
            static_assert(std::is_integral<typename std::iterator_traits<ForwardIt>::value_type>::value, "Integral value type required.");
            for (auto i = 0; i < 81; i++)
            {
                if (*it == 0)
                {
                    domains[i] = MASK_ALL;
                }
                else
                {
                    domains[i] = MASK[*it - 1];
                }
                ++it;
            }
        }

        // Runs the AC3 inference algorithm
        Status make_consistent(std::vector<Arc> & arcs)
        {
            while (!arcs.empty())
            {
                const auto arc = arcs.back();
                arcs.pop_back();
                unsigned long to_zval;
                if (__popcnt(domains[arc.to]) == 1)
                {
                    _BitScanForward(&to_zval, domains[arc.to]);
                    auto prev_domain = domains[arc.from];
                    domains[arc.from] &= ~domains[arc.to];
                    if (domains[arc.from] != prev_domain) {
                        if (!domains[arc.from])
                        {
                            return Status::Inconsistent;
                        }                       
                        revise(arc.from, arcs);
                    }
                }
            }
            return Status::Inconclusive;
        }       

        bool solved() const
        {
            for (auto domain : domains)
            {
                if (__popcnt(domain) != 1)
                {
                    return false;
                }
            }
            return true;
        }

        // Returns the index which has the smallest non-one hamming weight
        int min_weight() const
        {
            auto min_index = -1;
            auto min = 10;
            for (auto index = 0; index < 81; index++)
            {
                int hamming_weight = __popcnt(domains[index]);
                // 2 is a lower-bound
                if (hamming_weight == 2)
                {
                    return index;
                }
                if (hamming_weight != 1 && hamming_weight < min)
                {
                    min = hamming_weight;
                    min_index = index;
                }
            }
            return min_index;
        }           

        // Returns a semi-deep copy of the current SudokuBoard, with val being forced on index
        SudokuBoard branch(const int index,const int val) const
        {
            auto clone(*this);
            clone.domains[index] = MASK[val - 1];
            return clone;
        }

        // Depth-first search to find a solved configuration, using AC3 inference along the way
        bool search(std::vector<Arc> arcs)
        {
            auto res = make_consistent(arcs);
            switch (res) {
                case Status::Solved:        return true;
                case Status::Inconsistent:  return false;
                case Status::Inconclusive:  break;
            }
            if (solved())
            {
                update_iterator();
                return true;
            }
            auto unassigned_index = min_weight();
            auto value = 0;
            unsigned long pos;
            auto current = domains[unassigned_index];
            // Iterates through all values within the domain
            while (_BitScanForward(&pos, current))
            {
                value += (pos + 1);
                current >>= (pos + 1);
                auto br = branch(unassigned_index, value);
                auto br_arcs = arcs;
                revise(unassigned_index, br_arcs);
                if (br.search(br_arcs))
                {
                    return true;
                }
            }
            return false;
        }

        bool evaluate()
        {
            return search(make_arcs());
        }
        // Update the passed in ForwardIterator with SudokuBoard's internal representation
        void update_iterator()
        {
            for (auto index = 0; index < 81; index++)
            {
                if (__popcnt(domains[index]) == 1)
                {
                    unsigned long pos;
                    _BitScanForward(&pos, domains[index]);
                    auto val = pos + 1;
                    *first = val;
                    ++first;
                }
            }
        }
    };
    inline std::string str(const int dst[81])
    {
        std::string str;
        str.reserve(81);
        for (auto index = 0; index < 81; index++)
        {
            str.append(std::to_string(dst[index]));
        }
        return str;
    }

    inline std::string pretty_str(const int dst[81])
    {
        std::string str;
        str.reserve(270);
        for (auto row = 0; row < 9; row++)
        {
            for (auto col = 0; col < 9; col++)
            {
                auto index = row * 9 + col;
                if (dst[index] == 0)
                {
                    str.append("[ ]");
                }
                else
                {
                    str.append("[");
                    str.append(std::to_string(dst[index]));
                    str.append("]");
                }
            }
            str.append("\n");
        }
        return str;
    }

    template<typename ForwardIt>
    inline bool evaluate(ForwardIt first)
    {
        int cpu_info[4];
        __cpuid(cpu_info, 1);
        const U32 bitmask23 = 0x0800000;
        if (!(cpu_info[2] & bitmask23))
        {
            throw std::runtime_error("Hardware does not support __popcnt instruction.");
        }
        else
        {
            SudokuBoard<ForwardIt> su(first);
            return su.evaluate();
        }

    }

    inline bool evaluate(std::istream & in, std::ostream & out, const bool pretty = false)
    {
        int board[81];
        auto i = 0;
        for (std::string line; std::getline(in, line) && i < 81;)
        {
            for (const auto c : line)
            {
                auto val = c - '0';
                board[i++] = (val > 0 && val < 10) ? val : 0;
            }
        }
        std::fill(board + i, board + 81, 0);
        auto status = evaluate(board);
        if (status)
        {
            if (pretty)
            {
                out << pretty_str(board);
            }
            else
            {
                out << str(board);
            }
        }
        return status;
    }
}

I'm open to all comments and feedback, but I also have some specific questions as well:

  1. What could I change to make the code more readable, without suffering from performance?

  2. I only take the beginning of the input range, and assumed that there would be enough space for all 81 elements. Is this a good idea? If I require both a beginning and end, how would I handle a situation in which dist(end-beg) is not 81?

  3. Should the arcs vector be a parameter that's passed around, or is it considered part of the "state" of a SudokuBoard and thus should be a member?

\$\endgroup\$
  • \$\begingroup\$ Could you add an example of how this is to be used? \$\endgroup\$ – mkrieger1 Jan 19 '18 at 12:21
  • \$\begingroup\$ "What could I change to make the code more readable, without suffering from performance?" Comments have never affected performance and can be made to make code more readable. Not everyone is familiar with sudoku resolution; so outlining how you proceed and why you made such choices will bring a larger audience to the table \$\endgroup\$ – papagaga Jan 19 '18 at 15:46
  • 1
    \$\begingroup\$ I ended up adding a bunch of comments and a few clarifying points for some of the more mystical parts of the program. @mkrieger1 you can see an example here: github.com/glynkwei/sudoku \$\endgroup\$ – Mike Jan 20 '18 at 3:08
2
\$\begingroup\$

Nice work on your optimizations! Sounds like the change was worth it! Here are a few things I would change.

Comments

I have mixed feelings about your comments. On the one hand, it's good to comment things that might not be well understood, and I like the descriptions of the 2 evaluate functions. On the other hand, as someone who isn't familiar with the particular algorithm you're implementing, your comments aren't helpful at all in coming to an understanding of how it works on even a basic level.

I would start by putting a comment near the top of the file specifying what algorithm you're using (AC3 inference algorithm) and provide a link to it.

Beyond the specific algorithm, I also don't understand some of the other things you've commented like the NEIGHBOR_TABLE. The comment doesn't really illuminate it for me at all. Are neighbors 4-connected or 8-connected? Why isn't there a method for getting a neighbor in a more clear way? Requiring a user of this code to manually get the i * 20th value to figure out a neighbor seems harsh.

Intrinsics

I understand that you want to optimize for speed. Using the intrinsics is great for that, but you've needlessly tied your code to a specific architecture by using them. You could avoid that dependency by simply making an inline function that wraps the intrinsic and is written long-hand for other platforms. Something like this:

#if __SUPPORTS_INTRINSICS__ // Or whatever the appropriate #define is
inline int NumBitsSet(const U32 val)
{
    return __popcnt(val);
}
#else
inline int NumBitsSet(const U32 val)
{
    int numBits = 0;
    U32 nextBit = val;
    while (nextBit != 0)
    {
        if ((nextBit & 0x8000) != 0)
        {
            numBits++;
        }
        nextBit = (nextBit << 1);
    }

    return numBits;
}
#endif // __SUPPORTS_INTRINSICS__

(Or if you know that lower bits are more likely to be set than higher bits, you can check the lowest bits first. Just be aware of whether right shifting extends the sign bit or not in your compiler.) Even if you didn't do this, just wrapping the intrinsic in a function with a name that is meaningful would help. (Really Intel? "Population Count"? WTF? I had to google that to find out what it meant.)

Use a 2D Array for 2D data

It might not be very C++-y, but a standard 2D C array would work much better for this task than a 1D std::array where you have to manually do all the math to get the right value out of it. Writing something like:

domains [ row ][ col ] = x;

is way easier to read and understand than:

domains [ row * 9 + col ] = x;

And it's much easier to maintain and change. It would also remove the need for the NEIGHBOR_TABLE as every neighbor is only + or - 1 in any given direction.

Magic Numbers

You have so many raw numbers in your code, I can't imagine trying to maintain it. I don't know if you ever plan to handle different sized boards (like dodeca sudoku, hex-sudoku or mini-sudoku), but doing so for this code would be a nightmare. Even if you don't, understanding why and where all the various hard-coded values are there is a bit of a pain. I recommend making named constants for things like the number of rows and columns, even if you won't change them, just because it makes a lot of stuff more obvious.

Use Natural Numbers

I notice several places where you're indexing the MASK array with [val - 1]. Why not use values 1-9 instead of 0-8 and use the proper value for indexing into the array? It would only cost you a single 32-bit space.

Cosmetics

For the pretty-printing function, I would break up the output into 3x3 blocks so it looked more like this:

[1][2][3] [4][5][6] [7][8][9]
[4][5][6] [7][8][9] [1][2][3]
[7][8][9] [1][2][3] [4][5][6]

[3][2][1] [9][8][7] [6][5][4]
... etc.
\$\endgroup\$
  • \$\begingroup\$ Good review. Two points - I'd expect the pretty printing to be,... well... pretty and would strongly recommend ditching the [] which just adds clutter. Also the term "popcount" dates back to at least the mid-1970's (the Cray-1 implemented it) if not before. \$\endgroup\$ – Edward Jan 21 '18 at 14:35

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.