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:
What could I change to make the code more readable, without suffering from performance?
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?
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?
