hacks/sudoku/sudoku.cc

// Sudoku solver
// MIT license  michaelh@juju.net.nz
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cassert>
#include <ctime>
#include <cstdint>

// Uses sets to find out what's used and what the possibilities are.
// Implemented as a bitmask so an empty cell has the value 0, a cell
// with a 3 in contains 1 << 3, etc.

class Board
{
public:
    uint16_t cells[9][9];
    void Read();
    void Print() const;
};

struct CellRef
{
    int x;
    int y;
};

class Stats
{
public:
    int solutions;

    void Init();
    void Print();
    void Bump();

private:
    clock_t start;
    uint64_t tests;
};

Stats stats;

static int FFS(int v)
{
    return sizeof(v)*8 - 1 - __builtin_clz(v);
}

void Stats::Init()
{
    solutions = 0;
    tests = 0;
    start = clock();
}

void Stats::Print()
{
    double elapsed = (clock() - stats.start) / double(CLOCKS_PER_SEC);
    printf("%llu tests %d solutions %.3f s (%.1f M/s)\n",
           stats.tests, stats.solutions, 
           elapsed, stats.tests / elapsed / 1e6);
}

void Stats::Bump()
{
    stats.tests++;

    if ((stats.tests & 0x3ffffff) == 0) {
        stats.Print();
    }
}

void Board::Read()
{
    int x = 0;
    int y = 0;
    int ch;

    memset(cells, 0, sizeof(cells));

    while ((ch = fgetc(stdin)) != EOF) {
        if (ch == '#') {
            // Drop comment lines (kind of)
            while ((ch = fgetc(stdin)) != EOF && ch != '\n') {
            }
        } else if (ch == '\n') {
            x = 0;
            y++;
        } else if (ch == '\r') {
            // Drop
        } else if (ch == '.') {
            cells[y][x++] = 0;
        } else if (isdigit(ch)) {
            cells[y][x++] = 1 << (ch - '0');
        } else {
            assert(false);
        }
    }
}

void Board::Print() const
{
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            if (cells[y][x] == 0) {
                putchar('.');
            } else {
                putchar('0'+ FFS(cells[y][x]));
            }
        }
        printf("\n");
    }
    printf("\n");
}

// Find all of the blank cells.  Terminate the list with -1.
static void FindBlanks(const Board& board, CellRef* prefs)
{
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            if (board.cells[y][x] == 0) {
                prefs->x = x;
                prefs->y = y;
                prefs++;
            }
        }
    }

    prefs->x = -1;
}

static void OnSolution(const Board& board)
{
    stats.solutions++;

    // Print the first solution and keep going.
    if (stats.solutions == 1) {
        board.Print();
    }
}

static void Solve(Board& board, const CellRef* pref)
{
    // Mask for 1 to 9
    const int All = (1 << 10) - 1 - 1;

    int x = pref->x;
    int y = pref->y;

    if (x == -1) {
        OnSolution(board);
    }
    else {
        int present = 0;
        // Scan across the row and down the column to see which digits
        // are already used.
        for (int i = 0; i < 9; i++) {
            present |= board.cells[y][i];
            present |= board.cells[i][x];
        }
        // Calculate the unused values.
        int possibles = (present & All) ^ All;

        while (possibles != 0) {
            // Find the next and mark it as done.
            int next = 1 << FFS(possibles);
            possibles &= ~next;
            stats.Bump();

            // Solve for the next blank cell.
            board.cells[y][x] = next;
            Solve(board, pref+1);
            board.cells[y][x] = 0;
        }
    }
}

int main()
{
    Board board;
    CellRef refs[100];
    board.Read();
    board.Print();

    stats.Init();

    FindBlanks(board, refs);
    Solve(board, refs);
    stats.Print();

    return 0;
}