不久前，提出了这个问题，寻求帮助来优化以C ++实现的Sudoku求解器。

我决定使用C ++ 11重新实现代码，但没有猜测。也就是说，此Sudoku求解器不会进行猜测或回溯，而只会基于有效的逻辑推断进行求解。考虑到这一点，这是文件的第一部分，包括标头包含和类声明。

#include <iostream>
#include <iomanip>
#include <string>

// Sudoku solver
class Board
{
public:
    // default ctor
    Board();
    friend std::istream& operator >>(std::istream &in, Board &b);
    friend std::ostream& operator <<(std::ostream& out, const Board &b);
    std::ostream &printSimple(std::ostream &out) const;
    bool setVerbose(bool v) {return verbose = v;}
    bool solve();
    bool solved() { return unsolved==0; }
private:
    void doPairElimination(const int *nine, const int *start, const char *msg);
    void doOnlyInNine(const int *nine, const int *start, const char *msg);
    void nineElim(int index, const int *nine, int bitnum);
    void doSoleValues();
    char ch(int value, int bitnum) const;
    std::ostream &detailline(std::ostream &out, int index, int dline) const;
    std::ostream &printDetailed(std::ostream &out) const;
    static const int given=0x8000;
    static const int calculated=0x4000;
    static const int allnums = 0x03fe;

    int getbit(int square) const;
    int clrbit(int square, int bitnum);
    int getsquare(int index) const;
    int setsquare(int index, int value);
    int clrsquare(int index, int bitnum);
    int setcount(int index, int value);
    int getcount(int index) const;
    bool update(int index, int bitnum, int flags, const std::string="");
    int onenum(int index, bool showcalc=true) const;

    // representation is as follows:
    // 15 : given
    // 14 : calculate
    //  9-1 : possible values
    //  0 : guess
    int brd[81];
    // array containing counts of remaining possibilities for each cell
    int counts[81];
    // maintain count of unsolved squares
    unsigned unsolved;
    // verbosity for printing intermediate steps
    bool verbose;
    // to speed calculation, we make three static boards 
    // for rows, columns and subsquares, so that for any 
    // given index, all 9 related squares may be quickly
    // visited.
    const static int rows[81];
    const static int columns[81];
    const static int subsquares[81];
    const static int rstart[9];
    const static int cstart[9];
    const static int sstart[9];
};


为了加快进度，该版本使用了许多静态方法。表。数独使用三种套九个方块。它们是行，列和子正方形。 9x9网格上的每个正方形恰好属于其中每个正方形。静态表通过允许通用例程能够逐步浏览关联子正方形中的所有值来工作。例如，如果我们要检查右下角的正方形（数字80），则可以使用rows[]数组检查其行中的每个项目。每个条目都包含要访问的下一个正方形的索引（在本例中为72，这是最后一行的最左边的正方形）。 

/ here is how the board is laid out in memory
/*
     0,  1,  2,  3,  4,  5,  6,  7,  8,
     9, 10, 11, 12, 13, 14, 15, 16, 17,
    18, 19, 20, 21, 22, 23, 24, 25, 26,

    27, 28, 29, 30, 31, 32, 33, 34, 35,
    36, 37, 38, 39, 40, 41, 42, 43, 44,
    45, 46, 47, 48, 49, 50, 51, 52, 53,

    54, 55, 56, 57, 58, 59, 60, 61, 62,
    63, 64, 65, 66, 67, 68, 69, 70, 71,
    72, 73, 74, 75, 76, 77, 78, 79, 80
*/
// each array contains 9 starting values from which each [row,col,subsquare]
// may be visited
const int Board::rstart[] = { 0,  9, 18, 27, 36, 45, 54, 63, 72 };
const int Board::cstart[] = { 0,  1,  2,  3,  4,  5,  6,  7,  8 };
const int Board::sstart[] = { 0,  3,  6, 27, 30, 33, 54, 57, 60 };

const int Board::rows[] = {
     1,  2,  3,  4,  5,  6,  7,  8,  0,
    10, 11, 12, 13, 14, 15, 16, 17,  9,
    19, 20, 21, 22, 23, 24, 25, 26, 18,

    28, 29, 30, 31, 32, 33, 34, 35, 27,
    37, 38, 39, 40, 41, 42, 43, 44, 36,
    46, 47, 48, 49, 50, 51, 52, 53, 45,

    55, 56, 57, 58, 59, 60, 61, 62, 54,
    64, 65, 66, 67, 68, 69, 70, 71, 63,
    73, 74, 75, 76, 77, 78, 79, 80, 72
};

const int Board::columns[] = {
     9, 10, 11, 12, 13, 14, 15, 16, 17, 
    18, 19, 20, 21, 22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, 32, 33, 34, 35,
    36, 37, 38, 39, 40, 41, 42, 43, 44,
    45, 46, 47, 48, 49, 50, 51, 52, 53,
    54, 55, 56, 57, 58, 59, 60, 61, 62,
    63, 64, 65, 66, 67, 68, 69, 70, 71,
    72, 73, 74, 75, 76, 77, 78, 79, 80,
     0,  1,  2,  3,  4,  5,  6,  7,  8
};

const int Board::subsquares[] = {
     1,  2,  9,  4,  5, 12,  7,  8, 15,
    10, 11, 18, 13, 14, 21, 16, 17, 24,
    19, 20,  0, 22, 23,  3, 25, 26,  6,

    28, 29, 36, 31, 32, 39, 34, 35, 42,
    37, 38, 45, 40, 41, 48, 43, 44, 51,
    46, 47, 27, 49, 50, 30, 52, 53, 33,

    55, 56, 63, 58, 59, 66, 61, 62, 69,
    64, 65, 72, 67, 68, 75, 70, 71, 78,
    73, 74, 54, 76, 77, 57, 79, 80, 60
};


该代码包含许多实用程序和便利功能。

Board::Board() : unsolved(81) , verbose(false)
{
    for (int index=0; index<81; ++index) {
        setsquare(index, allnums);
        setcount(index, 9);
    }
}

std::istream& operator >>(std::istream &in, Board &b)
{
    std::string line;

    for (int row=0; row < 9; ++row) {
        std::getline(in, line);
        for(int col=0; col< 9; ++col) {
            int ch = line[col]-'0';
            if ((ch >= 1) && (ch <=9))
                b.update(row*9+col,ch,b.given);
        }
    }
    return in;
}

std::ostream& operator <<(std::ostream& out, const Board &b)
{
    if (b.verbose)
        return b.printDetailed(out);
    return b.printSimple(out);
}

char Board::ch(int value, int bitnum) const
{
    if (!(value & (1<<bitnum)))
        return '.';
    if (value & given) {
        return 'G';
    } else if (value & calculated) {
        return 'C';
    }
    return "0123456789"[bitnum];
}

std::ostream &Board::detailline(std::ostream &out, int index, int dline) const
{
    int sq = getsquare(index);
    switch (dline) {
        case 0:
            out << ch(sq,1) << ch(sq,2) << ch(sq,3) << ' ';
            break;
        case 1:
            out << ch(sq,4) << ch(sq,5) << ch(sq,6) << ' ';
            break;
        case 2:
            out << ch(sq,7) << ch(sq,8) << ch(sq,9) << ' ';
            break;
        default:
            out << "    ";
    }

    return out;
}

std::ostream &Board::printDetailed(std::ostream &out) const
{
    int index = 0;
    for (int row=0; row < 9; ++row) {
        for (int dline = 0; dline < 4; ++dline) {
            index = row*9;
            for(int col=0; col< 9; ++col, ++index) {
                detailline(out, index, dline);
                if (col %3 == 2)
                    out << "  ";
            }
            out << std::endl;
        }
        if (row%3 == 2) 
            out << std::endl;
    }
    return out;
}

std::ostream &Board::printSimple(std::ostream &out) const
{
    for (int index=0; index < 81; ++index) {
        int sq = onenum(index);
        if (sq > 0)
            out << sq;
        else
            out << '.';
        if (index % 9 == (9-1))
            out << std::endl;
    }
    return out;
}

int Board::getbit(int square) const
{
    for (int i=1; i <= 9; i++)
        if (square & 1<<i)
            return i;
    return 0;
}

int Board::clrbit(int square, int bitnum) 
{
   if ((square & given) || (square & calculated))
       return square;
   else
       return square & ~(1 << bitnum);
}

int Board::getsquare(int index) const
{
    return brd[index];
}

int Board::setsquare(int index, int value)
{
    return brd[index]=value;
}

int Board::clrsquare(int index, int bitnum)
{
    int sq = getsquare(index);
    int sq2 = setsquare(index, clrbit(sq, bitnum));
    if (sq != sq2)
        setcount(index, getcount(index)-1);
    return sq2;
}

int Board::setcount(int index, int value)
{
    return counts[index]=value;
}

int Board::getcount(int index) const
{
    return counts[index];
}


主要的求解例程是next：

/**
 * Given a cell index and bitnum, set the given bit and eliminate it
 * from all three associated nines.
 */
bool Board::update(int index, int bitnum, int flags, const std::string msg)
{
    int sq = getsquare(index);
    // if this was not a candidate bit, reject the update
    if (!(sq & (1<<bitnum)))
        return false;
    --unsolved;
    if (verbose) {
        std::cout << "[" << index/9 << ", " << index%9 << "]=" << bitnum << ' ';
        if (flags & given)
            std::cout << "G\n";
        else 
            std::cout << "c (" << msg << ")\n"; 
    }
    // set just the one bit
    setsquare(index, (sq & ~allnums) | (1<<bitnum) | flags);
    counts[index]=0;
    // clear the bit in each of the other squares by
    // row, column and subsquare
    nineElim(index, rows, bitnum);
    nineElim(index, columns, bitnum);
    nineElim(index, subsquares, bitnum);

    return true;
}

void Board::nineElim(int index, const int *nine, int bitnum)
{
    for (int r=nine[index]; r != index; r=nine[r])
        clrsquare(r, bitnum);
}

int Board::onenum(int index, bool showcalc) const
{
    int square = getsquare(index);
    if ((square & given) || (showcalc && (square & calculated)))
        return getbit(square);
    return 0;
}

void Board::doSoleValues()
{
    bool more;
    do {
        more = false;
        for (int index=0; index < 81; ++index) {
            if (1 == getcount(index)) {
                int sq = getsquare(index);
                update(index,getbit(sq),calculated, "doSoleValues");
                more = true;
            }
        }
    } while (more);
}

/**
 * For each given nine, if there is a pair of unsolved cells each
 * having exactly the same two remaining possibilities, then none of the 
 * other seven cells may have those numbers as possibilities.
 */
void Board::doPairElimination(const int *nine, const int *start, const char *msg)
{
    for (int row=0; row < 9; ++row) {
        for (int col=0, i=start[row]; col < 9; ++col, i=nine[i]) {
            // does this cell have exactly 2 possibilities left?
            if (2 == getcount(i)) {
                // yes; see if there's an identical cell in this nine
                for (int j=nine[i], k=col+1; k < 9; ++k, j=nine[j]) {
                    if (getsquare(i) == getsquare(j)) {
                        // so clear these bits in the other seven cells
                        // we do this using the nineElim call which 
                        // actually clears eight cells, but then we restore 
                        // the value.
                        if (verbose) std::cout << msg << " clearing pair " << i << ", " << j << std::endl;
                        nineElim(i, nine, getbit(getsquare(i)));
                        nineElim(i, nine, getbit(getsquare(j)));
                        setsquare(j, getsquare(i));
                        setcount(j,2);
                    }
                }
            }
        }
    }
}

/*
 * For each given Nine, if there is a square which contains, as a 
 * remaining possibility, the ONLY instance of a particular digit,
 * then that square must be assigned that digit.
 */
void Board::doOnlyInNine(const int *nine, const int *start, const char *msg)
{
    int index = 0;
    bool more;

    do {
        more = false;
        /* 
         * The variable is labelled "row" but it's really just the index
         * into the particular square within the Nine.
         */
        for (int row=0; row < 9; ++row) {
            index = start[row];
            /*
             * for each digit, count the number of squares that could 
             * still possibly contain it.
             */
            for (int bitnum = 1; bitnum <= 9; ++bitnum) {
                int count=0;
                for (int col=0, i=index; col < 9; ++col, i=nine[i]) {
                    int sq = getsquare(i);
                    if (!(sq & (given | calculated))) {
                        if (sq & (1<<bitnum))
                            ++count;
                    }
                }
                /*
                 * If only one square could possibly contain the digit,
                 * then set that square to be be the digit.
                 */
                if (count == 1) {
                    for (int col=0, i=index; col < 9; ++col, i=nine[i]) {
                        int sq = getsquare(i);
                        if (sq & (1<<bitnum)) {
                            update(i,bitnum,calculated,msg);
                            if (verbose) printDetailed(std::cout);
                            more = true;
                        }
                    }
                }
            }
        }
    } while (more);
}


如代码注释所示，主要的solve()例程仅应用各种策略，直到解决了电路板或没有进展。

bool Board::solve() 
{
    bool result = false;
    unsigned initial;
    /*
     * Continue working on the board until either:
     *   - the board is solved    OR
     *   - no progress was made in the last round
     */
    do {
        if (verbose) std::cout << "unsolved pr = " << unsolved << std::endl;
        doPairElimination(rows, rstart, "rowPairs");
        if (verbose) std::cout << "unsolved pc = " << unsolved << std::endl;
        doPairElimination(columns, cstart, "rowColumns");
        if (verbose) std::cout << "unsolved pq = " << unsolved << std::endl;
        doPairElimination(subsquares, sstart, "rowSubsquares");
        initial = unsolved;
        if (verbose) std::cout << "unsolved r = " << unsolved << std::endl;
        doOnlyInNine(rows, rstart, "doOnlyInRow");
        if (verbose) std::cout << "unsolved c = " << unsolved << std::endl;
        doOnlyInNine(columns, cstart, "doOnlyInCol");
        if (verbose) std::cout << "unsolved q = " << unsolved << std::endl;
        doOnlyInNine(subsquares, sstart, "doOnlyInSubsquares");
        if (verbose) std::cout << "unsolved s = " << unsolved << std::endl;
        doSoleValues();
    } while (unsolved && unsolved < initial);
    if (verbose) std::cout << "unsolved = " << unsolved << std::endl;
    return result;
}


int main()
{
    Board b;

    std::cout << "Reading board from stdin\n";
    std::cin >> b;
    std::cout << b;
    b.solve();
    std::cout << "Writing board to stdout\n";
    std::cout << b;
    // b.printSimple(std::cout);

    return 0;
}


在以下主板上使用此代码：

.75..1..2
........9
.9..27.4.
....943..
.........
..381....
.3.76..1.
9........
6..4..58.


在笔记本电脑上以0.05秒的时间即可得出正确的解决方案：

875941632
264583179
391627845
786294351
159376428
423815796
538762914
947158263
612439587


我正在寻找有关如何改进此代码的常规代码评论和评论。

评论

我真的希望有更多关于行，列和平方数组的结构的详细信息，这些数字对我来说没有意义....更多评论？
@rolfl：我添加了一些注释，并修复了代码中的一些遗漏（因为还没有任何答案）。 nineElim（）例程可能是如何使用静态表的最清楚的说明。
您已经实现了两个最简单的规则，并且具有用于暴露数据结构的框架。现在，您可以提出其他问题，并仅显示可以应用的已知规则（请参考此问题以显示框架）。
一些标准规则（您可以在Google上搜索这些术语）：“裸身”，“锁定候选人”，“裸对/三元组/四元组”，“唯一矩形”，“ BUG”，“隐藏对/三元组/四元组”，“远程”对”，“ X翼”，“箭鱼”，“ JellyFish”，“ W翼”，“几乎锁定的候选对象”，“隐藏的唯一矩形”，“ XY翼”，“ XYZ翼”，“ WXYZ-机翼”，​​“ X链”，“ XY链”，“鱼周期”，“着色”，“ Sue-de-Coq”，“美杜莎着色”，“ ALS-XY”，“干扰链”。

#1 楼

Sudoku的求解规则非常对称。通常，您可以将相同的规则应用于row / col / block，这在您最初的解决方案块中都可以看到，在您同时调用doPairElimination()和doOnlyInNine()的情况下。
如果将此代码概括化，可能会更容易阅读。告诉一些处理程序函数在三种情况下（即DRY）应用求解器。
我对您的反序列化器并不特别满意（尽管它可能有效）。由于需要手动计算int值。我不认为从流中读取难题的速度是这里的优先事项（因此，我倾向于（尽管如果我的团队中的一个做到了）我不会坚持更改），而不是使用类型更一致的方法的解决方案。 
    for(int col=0; col< 9; ++col) {
        int ch = line[col]-'0';
        if ((ch >= 1) && (ch <=9))
            b.update(row*9+col,ch,b.given);

除非您真的要刷新，否则不要使用std::endl。首选"\n"作为简单的换行符。
基于注释在第一点上进行了扩展：
    template<typename F>
    void tryOperation(F func, std::string const& msg)
    {
        if (verbose) std::cout << msg << " row = " << unsolved << "\n";
        func(rows, rstart, "row");

        if (verbose) std::cout << msg << " col = " << unsolved << "\n";
        func(columns, cstart, "col");
    
        if (verbose) std::cout << msg << " sqr = " << unsolved << "\n";
        func(subsquares, sstart, "sqr");
    }

然后主循环变为：
    do
    {
        tryOperation(doPairElimination, "Pair Elimination ");
        tryOperation(doOnlyInNine,      "Only in Nine");
        doSoleValues();
    } while (unsolved && unsolved < initial);


#2 楼

微小调整：

由于使用的是C ++ 11兼容编译器，请尽可能使用constexpr：

static const int given      = 0x8000;
static const int calculated = 0x4000;
static const int allnums    = 0x03fe;


可以替换为：

static constexpr int given      = 0x8000;
static constexpr int calculated = 0x4000;
static constexpr int allnums    = 0x03fe;


评论

\ $ \ begingroup \ $
我尝试使用的任何编译器在生成的二进制文件中都没有差异。很难想象这会对使用产生什么影响。
\ $ \ endgroup \ $
–爱德华
14年7月6日在16:26
\ $ \ begingroup \ $
我知道生成的代码应该是相同的，但是constexpr强制使用编译时常量，这可能有一些优点。 stackoverflow.com/a/13347355/1198654
\ $ \ endgroup \ $
–glampert
2014年7月6日在18:59


\ $ \ begingroup \ $
但是，为了澄清一下，这是使代码更“ C ++ 11-ish”的建议。
\ $ \ endgroup \ $
–glampert
2014年7月6日在19:01


\ $ \ begingroup \ $
@Edward：constexpr将是更正确的版本（因为表达式是const）。因此，习惯正确地执行此操作将有助于后续代码（可能会有所作为）。就像const在C ++中成为一件大事一样。追溯增加成本确实很困难，但从长远来看，正确地把成本放在首位可以为您带来好处。
\ $ \ endgroup \ $
–马丁·约克
2014年7月7日在17:45