25
\$\begingroup\$

Some time ago, this question was posed, asking for help in optimizing a Sudoku solver implemented in C++.

I decided to reimplement the code using C++11, but without guessing. That is, this Sudoku solver does not make guesses or backtracks, but instead only solves based on valid logical inference. With that in mind, here is the first part of the file, including header includes and class declaration.

#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];
};

To speed things along, this version uses a number of static tables. Sudoku uses three kinds of sets of nine squares. They are rows, columns and subsquares. Each square on the 9x9 grid belongs to exactly one of each of those. The static tables work by allowing a generic routine to be able to step through all of the values in the associated subsquare. For example, if we wanted to check the lower right square (number 80), we could check each item in its row by using the rows[] array. Each entry contains the index of the next square to be visited, (in this case 72, which is the far left square on the last row).

/ 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
};

The code includes a number of utility and convenience functions.

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];
}

The main solving routines are 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);
}

As the code comments note, the main solve() routine simply applies various strategies until either the board is solved or no progress is made.

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;
}

Using this code with the following board:

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

yields the correct solution in 0.05 seconds on my laptop:

875941632
264583179
391627845
786294351
159376428
423815796
538762914
947158263
612439587

I'm looking for a general code review and comments on how to improve this code.

\$\endgroup\$
  • 2
    \$\begingroup\$ I really wish there was more detail about how the rows, cols and ssquare arrays were structured, the numbers do not make sense to me.... more comments? \$\endgroup\$ – rolfl Jul 1 '14 at 13:17
  • \$\begingroup\$ @rolfl: I have added some comments and also fixed some omissions in the code (since there aren't any answers yet). The nineElim() routine is probably the clearest illustration of how the static tables are used. \$\endgroup\$ – Edward Jul 1 '14 at 13:50
  • \$\begingroup\$ You have implemented the two simplest rules and you have a framework for exposing the data structures. You can now ask other questions and just show knew rules that you can apply (referring back to this question to show the framework). \$\endgroup\$ – Martin York Jul 2 '14 at 17:57
  • \$\begingroup\$ Some standard rules (you can google these terms): "Naked Single", "Locked Candidates", "Naked Pairs/Triples/Quads", "Unique Rectangle", "BUG", "Hidden Pair/Triple/Quad", "Remote Pair", "X-Wing", "Swordfish", "JellyFish", "W-Wing", "Almost Locked Candidates", "Hidden Unique Rectangle", "XY-Wing", "XYZ-Wing", "WXYZ-Wing", "X-Chain", "XY-Chain", "Fish Cycle", "Colouring", "Sue-de-Coq", "Medusa Coloring", "ALS-XY", "Interference Chain". \$\endgroup\$ – Martin York Jul 2 '14 at 18:04
11
\$\begingroup\$

The solving rules for Sudoku are very symmetrical. You can usually apply the same rule to row/col/block and this is seen in your initial solution block where you call doPairElimination() and doOnlyInNine() both three times.

It might be easier to read if you generalized this code. Tell some handler function to apply a solver in the three situations (i.e. DRY).

I am not particularly found of your de-serializer (though it probably works). Because of the manual calculation of the int value. I don't think speed in reading the puzzle from a stream is the priority here (thus I would prefer (though if one of my team did it) I would not insist on the change) to a solution that used a more type consistent method of getting the value.

    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);

Don't use std::endl unless you really want to flush. Prefer "\n" for a simple new-line character.

Extended on first point based on comments:

    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");
    }

The main loop then becomes:

    do
    {
        tryOperation(doPairElimination, "Pair Elimination ");
        tryOperation(doOnlyInNine,      "Only in Nine");
        doSoleValues();
    } while (unsolved && unsolved < initial);
\$\endgroup\$
6
\$\begingroup\$

A tiny adjustment:

Since you are using a C++11 compatible compiler, use constexpr whenever possible:

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

Can be replaced with:

static constexpr int given      = 0x8000;
static constexpr int calculated = 0x4000;
static constexpr int allnums    = 0x03fe;
\$\endgroup\$
  • 2
    \$\begingroup\$ There is no difference in the resulting binary with any of the compilers I tried. It's hard to imagine how that would make any difference in this use. \$\endgroup\$ – Edward Jul 6 '14 at 16:26
  • 1
    \$\begingroup\$ I know that the generated code should be the same, but constexpr forces a compile-time constant, which can have a few advantages. stackoverflow.com/a/13347355/1198654 \$\endgroup\$ – glampert Jul 6 '14 at 18:59
  • 1
    \$\begingroup\$ But just to clarify, this is a suggestion to make the code more "C++11-ish". \$\endgroup\$ – glampert Jul 6 '14 at 19:01
  • 2
    \$\begingroup\$ @Edward: constexpr would be the more correct version to use (as the expression is const). So getting used to doing it correctly will help in subsequent code (where it potetnally can make a difference). Its like when const became a big thing in C++. Retroactively adding cost was really hard but putting it in correctly in the first place gave you advantages in the long term. \$\endgroup\$ – Martin York Jul 7 '14 at 17:45

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.