/*
    Sudoku solver by Rudi Bjørn Rasmussen.
    This program solves a Sudoku puzzle by reursively guessing until
    the puzzle.
    To speed up the guessing, only numbers not already in row, col or
    3 by 3 cell are tried.
*/


#include <iostream>

//    dimension of the Sudoku board, 9 by 9 fields
const int NSIZE = 9;

//    dimension of sub cells
const int CELLSIZE = 3;

//    the sum of rows, columns and the 9 3x3 cells, 1+2+...9=45
const int SUM = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;

//    prints the given board to stdout
void print(int b[NSIZE][NSIZE])
{
    std::cout << std::endl;
    for (int col = 0; col < NSIZE; ++col)
    {
        for (int row = 0; row < NSIZE; ++row)
        {
            if (b[col][row] == 0)
                std::cout << ". ";
            else
                std::cout << b[col][row] << " ";
            if (row == 2 || row == 5)
                std::cout << "| ";
        }
        std::cout << std::endl;
        if (col == 2 || col == 5)
            std::cout << "------+-------+------" << std::endl;
    }
    std::cout << std::endl;
}

//    returns true if the given board has been solved
bool solved(int b[NSIZE][NSIZE])
{
    // check column sums
    for (int c = 0; c < NSIZE; ++c)
    {
        int sum = 0;
        for (int r = 0; r < NSIZE; ++r)
        {
            //    If one of the fields is zero, no solution has been found.
            //    This check only needs to be done here, since the column check scans all fields.
            if (b[c][r] == 0)
                return false;
            sum += b[c][r];
        }
        if (sum != SUM)
            return false;
    }

    // check row sums
    for (int r = 0; r < NSIZE; ++r)
    {
        int sum = 0;
        for (int c = 0; c < NSIZE; ++c)
            sum += b[c][r];
        if (sum != SUM)
            return false;
    }

    //    check 3x3 cell sums
    for (int cc = 0; cc < CELLSIZE; ++cc)
    {
        for (int rr = 0; rr < CELLSIZE; ++rr)
        {
            int sum = 0;
            for (int c = cc * CELLSIZE; c < (cc + 1) * CELLSIZE; ++c)
            {
                for (int r = rr * CELLSIZE; r < (rr + 1) * CELLSIZE; ++r)
                    sum += b[c][r];
            }
            if (sum != SUM)
                return false;
        }
    }

    //    no errors found, the Sudoku puzzle is solved
    return true;
}

//    check if the given row is missing the number N
int rowMissing(int board[NSIZE][NSIZE], int r, int N)
{
    for (int c = 0; c < NSIZE; ++c)
    {
        if (board[c][r] == N)
            return false;
    }
    return true;
}

//    check if the given column is missing the number N
int colMissing(int board[NSIZE][NSIZE], int c, int N)
{
    for (int r = 0; r < NSIZE; ++r)
    {
        if (board[c][r] == N)
            return false;
    }
    return true;
}

//    check if the given 3x3 cell is missing the number N
int cellMissing(int board[NSIZE][NSIZE], int c, int r, int N)
{
    int cc = (c/CELLSIZE)*CELLSIZE;
    int rr = (r/CELLSIZE)*CELLSIZE;
    for (int _c = cc; _c < cc + CELLSIZE; ++_c)
    {
        for (int _r = rr; _r < rr + CELLSIZE; ++_r)
        {
            if (board[_c][_r] == N)
                return false;
        }
    }
    return true;
}

//    This function recursively tries to guess next number on the board.
bool guess(int board[NSIZE][NSIZE], int index, int& guessCount)
{
    //    search for next cell containg 0
    for (int i = index; i < NSIZE * NSIZE; ++i)
    {
        int c = i % NSIZE;
        int r = i / NSIZE;
        if (board[c][r] == 0)
        {
            for (int num = 1; num < NSIZE + 1; ++num)
            {
                if (rowMissing(board,r,num) && colMissing(board,c,num) && cellMissing(board,c,r,num))
                {
                    ++guessCount;
                    board[c][r] = num;
                    if (guess(board, i + 1, guessCount))
                        return true;
                }
            }
            board[c][r] = 0;    //    reset number, all guess failed
            return false;
        }
    }

    return solved(board);
}

void solve(int b[NSIZE][NSIZE])
{
    std::cout << "-------------------------" << std::endl;
    std::cout << "Sudoku solver by guessing" << std::endl;
    int guessCount = 0;
    if (!guess(b,0,guessCount))
        std::cout << "no ";
    std::cout << "solution found after " << guessCount << " guesses" << std::endl;
    print(b);
}

//    example:
int main(int argc, char* argv[])
{
    int board[NSIZE][NSIZE] =
    {
        {0,9,0, 2,0,3, 0,0,0},
        {4,6,0, 0,5,0, 0,1,0},
        {5,0,8, 1,0,0, 9,0,0},

        {9,0,0, 0,0,1, 0,0,0},
        {0,0,0, 5,0,2, 0,0,1},
        {0,0,0, 8,0,0, 0,0,5},

        {0,0,2, 0,0,5, 6,0,9},
        {0,5,0, 0,7,0, 0,2,3},
        {0,0,0, 4,0,6, 0,7,0}
    };

    solve(board);    
}