C++ Sudoku Solver
C++ Sudoku Solver
提问于 2018-01-19 01:57:11
我刚刚在C++完成了一个sudoku解算器。我最初在Python中完成了一个课程工作的求解程序，我想看看我能获得多少性能上的提升。正因为如此，我最终为MSVC使用了编译器本质，并自由地使用了数组。它最终比我预期的要快得多，在0到0.1毫秒内解决了大多数谜题(作为参考，我天真的Python代码花了20秒来解决相同的谜题，加速速度约为50000x)。从性能的角度来看，没有理由尝试更快地获得它，因为大部分时间都花在开销上。不过，对于其中的一些细节，我确实有一些疑问。
#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;
}
}我愿意接受所有的评论和反馈，但我也有一些具体的问题：
- 在不受性能影响的情况下，我可以更改什么来提高代码的可读性呢？
- 我只取输入范围的开头，并假定有足够的空间来容纳所有81个元素。这是个好主意吗如果我需要开始和结束，我将如何处理dist(结束-乞求)不是81的情况？
- arcs向量是一个传递的参数，还是它被认为是SudokuBoard的“状态”的一部分，因此应该是一个成员？
回答 1
Code Review用户
发布于 2018-01-21 06:24:19
在优化方面做得很好！听起来这变化是值得的！以下是我想要改变的几件事。
注释
我对你的评论有复杂的感觉。一方面，注释一些可能不是很好理解的东西是很好的，我喜欢对2 evaluate函数的描述。另一方面，作为一个不熟悉您正在实现的特定算法的人，您的评论对理解它在基本水平上的工作方式毫无帮助。
首先，在文件的顶部放置一个注释，指定您正在使用的算法(AC3推断算法)，并向其提供一个链接。
除了具体的算法之外，我还不理解您所评论的其他一些事情，比如NEIGHBOR_TABLE。这句话对我一点也不清楚。邻居是4连的还是8连的？为什么没有一种让邻居更清楚的方法呢？要求此代码的用户手动获取i * 20th值来计算邻居似乎很苛刻。
Intrinsics
我知道你想优化速度。使用本质是很好的，但您已经不必要地通过使用它们将代码绑定到特定的体系结构中。您可以通过简单地创建一个内联函数来避免这种依赖，该函数封装了内部的内容，并为其他平台编写了长时间的代码。就像这样：
#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__(或者，如果您知道低位比高位更有可能设置，则可以先检查最低位。只需注意右移位是否扩展了编译器中的符号位。)即使您没有这样做，用有意义的名称包装函数中的内部也会有帮助。(真的是情报？“人口统计”？见鬼？我不得不在谷歌上找出它的含义。)
使用2D数组实现二维数据
它可能不是很好的C++-y，但是一个标准的2D C数组将比一维std::array工作得好得多，因为你必须手动完成所有的数学运算才能得到正确的值。写一些类似于：
domains [ row ][ col ] = x;比以下内容更容易阅读和理解：
domains [ row * 9 + col ] = x;而且它更容易维护和改变。它还将消除对NEIGHBOR_TABLE的需求，因为每个邻居在任何给定的方向上都只有+或-1。
幻数
您的代码中有这么多原始数字，我无法想象试图维护它。我不知道您是否计划处理不同大小的板(比如十二大板、六角板或迷你板)，但是这样做对代码来说将是一场噩梦。即使你没有，理解为什么和所有不同的硬编码值是有一点痛苦。我建议为诸如行数和列数这样的东西设置命名常量，即使您不会更改它们，仅仅因为这样做会使很多事情变得更明显。
使用自然数
我注意到有几个地方正在用MASK索引[val - 1]数组。为什么不使用值1-9而不是0-8，并使用适当的值索引到数组中？它只花你一个32位的空间。
化妆品
对于漂亮的打印功能，我会将输出分解为3x3块，这样看起来更像这样：
[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.页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/185442
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号