// sudoku.cpp -- a pretty fast sudoku solver
// Compile with: g++ -Wall -O2 sudoku.cpp -o sudoku
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdarg.h>
#include <string.h>
#include <vector>
#include <set>
#include <cctype>

static inline  void show_rule(const struct Board& board, const char* fmt, ...);
void show_board(const struct Board& board, const char *msg=0);

struct Config {
    bool show_board;      // show board at each step
    bool show_forced;     // show number of forced moves at each step
    bool show_rules;      // show reasoning at each step
    bool single_solution; // stop after finding a solution
    int  base;            // numeric base for displayed numbers
} config = {false, false, false, true, 1};

struct Move {
    int j, i, v, key;
    Move(int j, int i, int v): j(j), i(i), v(v), key(81*j+9*i+v) { }
    bool operator<(const Move& other) const { // for std::set
        return key < other.key;
    }
};

enum MoveState { UNTRIED=0, PLAYED, WOULD_COLLIDE };

// FIXME: BoardFlags only exists because I haven't thought about how to
//        get C-style arrays to do sensible indexing automatically.
template <typename T>
struct BoardFlags {
    T flags[9*9*9];

    bool operator==(const BoardFlags<T>& other) const {
        for (int x=0; x<9*9*9; ++x)
            if (flags[x] != other.flags[x])
                return false;
        return true;
    }

    bool operator!=(const BoardFlags<T>& other) const {
        return !(*this == other);
    }

    BoardFlags(const T& initial_state) {
        for (int x=0; x<9*9*9; ++x)
            flags[x] = initial_state;
    }

    inline  T operator()(int j, int i, int v) const {
        return flags[81*j+9*i+v];
    }

    inline  T& operator()(int j, int i, int v) {
        return flags[81*j+9*i+v];
    }
};

struct Board {
    int move_count;
    BoardFlags<MoveState> move_state;
    int cboard[9*9]; // the values, we don't really need them

    // indexed by (9*a + b):
    int ji_freedoms[9*9];  // possible values for cell (j=a, i=b)
    int jv_freedoms[9*9];  // possible cells in row j=a to hold value v=b
    int iv_freedoms[9*9];  // possible cells in col i=a to hold value v=b
    int sq_freedoms[9*9];  // possible cells in bigsq=a to hold value v=b

    bool operator==(const Board& other) const {
        for (int x=0; x<81; ++x)
            if (cboard[x] != other.cboard[x])
                return false;
        return move_state==other.move_state;
    }

    bool operator!=(const Board& other) const {
        return !(*this == other);
    }

    Board(): move_count(0), move_state(UNTRIED) {
        for (int x=0; x<81; ++x) {
            cboard[x] = -1;
            ji_freedoms[x] = 9;
            jv_freedoms[x] = 9;
            iv_freedoms[x] = 9;
            sq_freedoms[x] = 9;
        }
    }

    Board(int cb[81]): move_count(0), move_state(UNTRIED) {
        for (int x=0; x<81; ++x) {
            cboard[x] = -1;
            ji_freedoms[x] = 9;
            jv_freedoms[x] = 9;
            iv_freedoms[x] = 9;
            sq_freedoms[x] = 9;
        }
    }
    inline  int& get(int j, int i)        { return cboard[9*j+i]; }
    inline  int  get(int j, int i) const  { return cboard[9*j+i]; }
    inline  void set(int j, int i, int v) { cboard[9*j+i] = v; }

    inline  bool is_ok_move(int j, int i, int v) {
        return move_state(j, i, v)==UNTRIED;
    }

    // index into ji_freedoms etc.
    static inline  int ji_idx(int j, int i, int  ) { return 9*j+i; }
    static inline  int jv_idx(int j, int  , int v) { return 9*j+v; }
    static inline  int iv_idx(int  , int i, int v) { return 9*i+v; }
    static inline  int sq_idx(int j, int i, int v) { return 9*(3*(j/3)+(i/3)) + v; }

    inline  void mark_collisions(int J, int I, int V) {
        // Decrease the freedoms associated with this move
        ji_freedoms[ji_idx(J, I, V)]--;
        jv_freedoms[jv_idx(J, I, V)]--;
        iv_freedoms[iv_idx(J, I, V)]--;
        sq_freedoms[sq_idx(J, I, V)]--;

        // same cell, different values
        for (int v=0; v < 9; ++v)
            if (v != V  &&  move_state(J, I, v)==UNTRIED) {
                move_state(J, I, v) = WOULD_COLLIDE;
                ji_freedoms[ji_idx(J, I, v)]--;
                jv_freedoms[jv_idx(J, I, v)]--;
                iv_freedoms[iv_idx(J, I, v)]--;
                sq_freedoms[sq_idx(J, I, v)]--;
            }
        // rows
        for (int i=0; i < 9; ++i)
            if (i != I  &&  move_state(J, i, V)==UNTRIED) {
                move_state(J, i, V) = WOULD_COLLIDE;
                ji_freedoms[ji_idx(J, i, V)]--;
                jv_freedoms[jv_idx(J, i, V)]--;
                iv_freedoms[iv_idx(J, i, V)]--;
                sq_freedoms[sq_idx(J, i, V)]--;
            }
        // cols
        for (int j=0; j < 9; ++j)
            if (j != J  &&  move_state(j, I, V)==UNTRIED) {
                move_state(j, I, V) = WOULD_COLLIDE;
                ji_freedoms[ji_idx(j, I, V)]--;
                jv_freedoms[jv_idx(j, I, V)]--;
                iv_freedoms[iv_idx(j, I, V)]--;
                sq_freedoms[sq_idx(j, I, V)]--;
            }
        // big squares
        int Y=(J/3)*3, X=(I/3)*3;
        for (int j=0; j<3; ++j)
            for (int i=0; i<3; ++i)
                if ((Y+j != J  ||  X+i != I) && move_state(Y+j, X+i, V)==UNTRIED) {
                    move_state(Y+j, X+i, V) = WOULD_COLLIDE;
                    ji_freedoms[ji_idx(Y+j, X+i, V)]--;
                    jv_freedoms[jv_idx(Y+j, X+i, V)]--;
                    iv_freedoms[iv_idx(Y+j, X+i, V)]--;
                    sq_freedoms[sq_idx(Y+j, X+i, V)]--;
                }
        if (jv_freedoms[jv_idx(J, I, V)]!=0)
            assert(0);
        assert(ji_freedoms[ji_idx(J, I, V)]==0);
        assert(jv_freedoms[jv_idx(J, I, V)]==0);
        assert(iv_freedoms[iv_idx(J, I, V)]==0);
        assert(sq_freedoms[sq_idx(J, I, V)]==0);
        ji_freedoms[ji_idx(J, I, V)] = -1;
        jv_freedoms[jv_idx(J, I, V)] = -1;
        iv_freedoms[iv_idx(J, I, V)] = -1;
        sq_freedoms[sq_idx(J, I, V)] = -1;
    }

    inline  bool make_move(const Move& m) {
        if (move_state(m.j, m.i, m.v)!=UNTRIED)
            return move_state(m.j, m.i, m.v)==PLAYED;
        bool ok = is_ok_move(m.j, m.i, m.v);
        if (ok) {
            move_state(m.j, m.i, m.v) = PLAYED;
            set(m.j, m.i, m.v);
            mark_collisions(m.j, m.i, m.v);
            if (++move_count==81)
                found_solution();
        } else {
            move_state(m.j, m.i, m.v) = WOULD_COLLIDE;
        }
        return ok;
    }

    std::set<Move> next_moves() const;

    void found_solution() const {
        show_board(*this, "Found solution.\n");
        if (config.single_solution)
            exit(0);
    }
};

typedef enum {JI=0, JV, IV, SQ} FreedomType;

// A helper used inside Board::next_moves().
// Must be declared at top level due to C++ templates sucking.
struct ConstrainedMove {
    int index;
    FreedomType ftype;
    ConstrainedMove(int index, FreedomType ftype):
        index(index), ftype(ftype) { }
};

std::set<Move> Board::next_moves() const {
    // Pick a most constrained next move, or all forced moves if there are any
    std::vector<ConstrainedMove> constrained_moves;
    int min_freedoms = 10, testval = 10;
    for (int x=0; x < 81; ++x) {
        if (ji_freedoms[x] == 0 || jv_freedoms[x] == 0 ||
            iv_freedoms[x] == 0 || sq_freedoms[x] == 0) {
            return std::set<Move>();
        }
        if (ji_freedoms[x] > 0  &&  ji_freedoms[x] < testval) {
            if (min_freedoms!=1) constrained_moves.clear();
            min_freedoms = ji_freedoms[x];
            constrained_moves.push_back(ConstrainedMove(x, JI));
            testval = (min_freedoms==1)? 2 : min_freedoms;
        }
        if (jv_freedoms[x] > 0  &&  jv_freedoms[x] < testval) {
            if (min_freedoms!=1) constrained_moves.clear();
            min_freedoms = jv_freedoms[x];
            constrained_moves.push_back(ConstrainedMove(x, JV));
            testval = (min_freedoms==1)? 2 : min_freedoms;
        }
        if (iv_freedoms[x] > 0  &&  iv_freedoms[x] < testval) {
            if (min_freedoms!=1) constrained_moves.clear();
            min_freedoms = iv_freedoms[x];
            constrained_moves.push_back(ConstrainedMove(x, IV));
            testval = (min_freedoms==1)? 2 : min_freedoms;
        }
        if (sq_freedoms[x] > 0  &&  sq_freedoms[x] < testval) {
            if (min_freedoms!=1) constrained_moves.clear();
            min_freedoms = sq_freedoms[x];
            constrained_moves.push_back(ConstrainedMove(x, SQ));
            testval = (min_freedoms==1)? 2 : min_freedoms;
        }
    }
    if (constrained_moves.size() > 1)
        assert(min_freedoms==1);

    static const char* freedom_strs[] = {
        "The only", "One of two", "One of three",
        "One of four", "One of five", "One of six",
        "One of seven", "One of eight", "One of nine"
    };
    const char* freedom_str = freedom_strs[min_freedoms-1];
    const char* plural = (min_freedoms==1)? "" : "s";
    const char punc = (min_freedoms==1)? '.' : '?';

    std::set<Move> result;
    for (std::vector<ConstrainedMove>::const_iterator
         it = constrained_moves.begin();
         it != constrained_moves.end();
         ++it
    ) {
        if (min_freedoms > 1 && result.size())
            break;
        int a = it->index/9, b = it->index%9;
        int N = config.base;
        switch (it->ftype) {
            case JI: {
                for (int v=0; v < 9; ++v) {
                    if (move_state(a, b, v)==UNTRIED) {
                        if (result.insert(Move(a, b, v)).second) {
                            show_rule(*this,
                                "Row %d, column %d = %d%c  "
                                "%s value%s that this cell could hold.\n",
                                a+N, b+N, v+N, punc,
                                freedom_str, plural);
                        }
                        break;
                    }
                }
                break;
            }
            case JV: {
                for (int i=0; i < 9; ++i) {
                    if (move_state(a, i, b)==UNTRIED) {
                        if (result.insert(Move(a, i, b)).second) {
                            show_rule(*this,
                                "Row %d, column %d = %d%c  "
                                "%s cell%s in row %d that "
                                "could hold value %d.\n",
                                a+N, i+N, b+N, punc,
                                freedom_str, plural, a+N, b+N);
                        }
                        break;
                    }
                }
                break;
            }
            case IV: {
                for (int j=0; j < 9; ++j) {
                    if (move_state(j, a, b)==UNTRIED) {
                        if (result.insert(Move(j, a, b)).second) {
                            show_rule(*this,
                                "Row %d, column %d = %d%c  "
                                "%s cell%s in column %d that "
                                "could hold value %d.\n",
                                j+N, a+N, b+N, punc,
                                freedom_str, plural, a+N, b+N);
                        }
                        break;
                    }
                }
                break;
            }
            case SQ: {
                int y=a/3, x=a%3;  assert(a==(3*y+x)); // bigsq(y,x) (y<3, x<3)
                int Y=3*y, X=3*x;  // optimisation: avoid extra multiplications
                for (int n=0; n<9; ++n) {
                    int j=n/3, i=n%3;
                    if (move_state(Y+j, X+i, b)==UNTRIED) {
                        if (result.insert(Move(Y+j, X+i, b)).second) {
                            show_rule(*this,
                                "Row %d, column %d = %d%c  "
                                "%s cell%s in 3x3-square %d that "
                                "could hold value %d.\n",
                                Y+j+N, X+i+N, b+N, punc,
                                freedom_str, plural, a+N, b+N);
                        }
                        break;
                    }
                }
            }
        }
    }
    if (config.show_forced) {
        if (min_freedoms==1)
            printf("%d forced moves of %d, %d%%.\n",
                   result.size(), 81-move_count,
                   ((200*result.size()+1)/(81-move_count))/2);
        else
            printf("No forced moves, guessing one of %d options.\n", min_freedoms);
    }
    if (result.size() > 1)
        assert(min_freedoms==1);
    return result;
}

void show_board(const Board& board, const char* msg) {
    if (msg) printf("%s", msg);
    int N = config.base;
    printf("[\n");
    for (int j=0; j < 9; j++) {
        for (int i=0; i<9; i++) {
            if (i%3==0) printf("  ");
            if (board.get(j,i)==-1) printf("x "); else printf("%d ", board.get(j,i)+N);
        }
        printf("\n");
        if (j==2 || j==5) printf("\n");
    }
    printf("]\n");
}

static inline
void show_rule(const Board& board, const char* fmt, ...) {
    if (config.show_rules) {
        printf("[%02d] ", board.move_count);
        va_list ap;
        va_start(ap, fmt);
        vprintf(fmt, ap);
        va_end(ap);
    }
}

static
void solve(const Board& board_, int depth=0) {
    if (config.show_board)
        show_board(board_);
    Board board(board_);
    while (1) {
        Board rollback_board(board);
        std::set<Move> moves = board.next_moves();
        if (moves.size()==0)
            return;
        // Make all of the recommended moves
        bool ok = true;
        for (std::set<Move>::const_iterator move = moves.begin();
             move != moves.end(); ++move) {
            if (!board.make_move(*move)) {
                ok = false;
                break;
            }
        }
        if (ok)
            solve(board, depth+1);
        // Returned => failed, rollback
        //printf("rollback from move %d to %d\n", board.move_count, rollback_board.move_count);
        board = rollback_board;
        for (std::set<Move>::const_iterator move = moves.begin();
             move != moves.end(); ++move) {
            board.move_state(move->j, move->i, move->v) = WOULD_COLLIDE;
            board.ji_freedoms[Board::ji_idx(move->j, move->i, move->v)]--;
            board.jv_freedoms[Board::jv_idx(move->j, move->i, move->v)]--;
            board.iv_freedoms[Board::iv_idx(move->j, move->i, move->v)]--;
            board.sq_freedoms[Board::sq_idx(move->j, move->i, move->v)]--;
        }
    }
}

int main(int argc, const char* argv[]) {
    config.show_board = 1;
    config.show_rules = 1;
    config.show_forced = 0;
    config.base = 1;

    Board board;

    // easy:   xx5x1xx949xxx36x1xx2x7xxxxxxxx36x875837xxx946456x87xxxxxxxx8x5xx8x15xxx351xx4x2xx
    // evil:   7xxxxx4xxxxx78xx5x2xx31xxxxx87xxxx2x4xxx7xxx5x9xxxx17xxxxx52xx8x2xx46xxxxx4xxxxx9
    // imposs: 7xxx2x4xxxxx78xx5x2xx31xxxxx87xxxx2x4xxx7xxx5x9xxxx17xxxxx52xx8x2xx46xxxxx4xxxxx9
    // figaro: 1xxxx2x4xx321xxxxxxx43xxx6x82xxx6xxxxxx2x4xxxxxx7xxx98x7xxx94xxxxxxx538xx5x4xxxx6
    // sparse: xxxxxxxxxxxxxxxxxx2xx31xxxxxx7xxxx2x4xxxxxxx5xxxxxx17xxxxx52xx8x2xxx6xxxxxxxxxxx9
    // telegr: x7xx5xx4xxx53x72xx24xxxxx79x3xxxxx1x4xx5x3xx6xxx482xxxx1x9x8x6xxxx6x5xxx6xxxxxxx2

    --argc, ++argv; // skip program name

    static const char test_board[] = "xxxxxxxxxxxxxxxxxx2xx31xxxxxx7xxxx2x4xxxxxxx5xxxxxx17xxxxx52xx8x2xxx6xxxxxxxxxxx9";
    const char* boardstr = 0;
    while (argc>=1 && argv[0][0]=='-') {
        if (strcmp(argv[0], "-q")==0) {
            config.show_board = 0;
        }
        else if (strcmp(argv[0], "-qq")==0) {
            config.show_rules = 0;
        }
        else if (strcmp(argv[0], "--forced")==0) {
            config.show_forced = 1;
        }
        else if (strcmp(argv[0], "--test")==0) {
            boardstr = test_board;
        }
        else if (strcmp(argv[0], "-")==0) {
            boardstr = "-";
        }
        else
            printf("Ignoring unknown argument '%s'.\n", argv[0]);
        --argc, ++argv;
    }
    if (argc==1 && strlen(argv[0])>=81) {
        if (boardstr) printf("Board specified, not using --test board.\n");
        boardstr = argv[0];
    }
    if (boardstr) {
        for (int stridx=0, posidx=0; posidx < 81; ) {
            char c = (strcmp(boardstr, "-")==0)? getchar() : boardstr[stridx++];
            if (!isspace(c) && c!=',') {
                if (c >= '1' && c <= '9') {
                    board.make_move(Move(posidx/9, posidx%9, c - '1'));
                }
                ++posidx;
            }
        }
    } else {
        printf("usage: sudoku [-q] [-qq] [--forced] [--test or BOARD]\n"
               "where BOARD is an 81-character board (non-digit = blank)");
        exit(1);
    }

    solve(board);
    printf("Done.\n");
}