// $Id: sudoku.cc,v 1.13 2007-04-05 21:10:25 cactus Exp $ -*- c++ -*-

// Sudoku, as played on an n x m hyper-board of boards sized m x n



#include <stdexcept>

class sudoku_error: public std::exception
{
};

// IO format error
class io_error: public sudoku_error
{
};

// A contradiction occured in the Sudoku board specification
class contradiction_error: public sudoku_error
{
};



//----------------------------------------------------
// FieldPossibilities: Container for the set of possible values for a field
//----------------------------------------------------

#include <bitset>

template<int n, int m>
class FieldPossibilities
{
    std::bitset<n * m> bitset;
public:
    FieldPossibilities ();

    int value () const;
    void set_single (int value);
    void eliminate (int value);

    inline bool operator[] (int value) const { return bitset[value - 1]; }
    inline bool definite () const { return bitset.count () == 1; }
    inline bool contradiction () const { return bitset.none(); }
};

template<int n, int m>
FieldPossibilities<n, m>::FieldPossibilities ()
{
    bitset.set ();
}

template<int n, int m>
int FieldPossibilities<n, m>::value() const
{
    if (bitset.count () != 1)
        return 0;

    int i;
    for (i = 0; !bitset[i]; ++i);
    return i + 1;
}

template<int n, int m>
void FieldPossibilities<n, m>::set_single (int value)
{
    bitset.reset ();
    bitset.set (value - 1);
}

template<int n, int m>
void FieldPossibilities<n, m>::eliminate (int value)
{
    bitset.reset (value - 1);
    if (contradiction ())
        throw contradiction_error ();
}



//----------------------------------------------------
// FieldMatrix: Container of [0..board_size - 1, 0..board_size - 1] FieldPossibilities'
//----------------------------------------------------

template<int n, int m>
class FieldMatrix
{
    FieldPossibilities<n, m> fields[(n * m) * (n * m)];

public:
    FieldMatrix () {}
    FieldMatrix (const FieldMatrix &src) {
        for (int i = 0; i != (n * m) * (n * m); ++i)
            fields[i] = src.fields[i];
    }
    
    inline FieldPossibilities<n, m> & operator() (int row, int col) { return fields[row * (n * m) + col]; };
    inline const FieldPossibilities<n, m> & operator() (int row, int col) const { return fields[row * (n * m) + col]; };
};



//----------------------------------------------------
// Board: A Sudoku board, including solver logic
//----------------------------------------------------

#include <iostream>

template<int n, int m>
class Board
{
    FieldMatrix<n, m> fields;
    
    void set_single (int row, int col, int v);

public:
    void solve ();
    
    void read (std::istream &stream);
    void print_state (std::ostream &stream) const;
    void print (std::ostream &stream) const;

    static void print_error (std::ostream &stream);
};

template<int n, int m>
void Board<n, m>::print (std::ostream &stream) const
{
    for (int i = 0; i < n * m; ++i)
    {
        for (int j = 0; j < n * m; ++j)
        {
            stream << fields(i, j).value ();
            
            if ((j + 1) != n * m)
            {
                if ((j + 1) % n == 0)
                    stream << " ";

                stream << " ";
            }
        }        

        if ((i + 1) % m == 0)
            stream << std::endl;

        stream << std::endl;
    }    
}

template<int n, int m>
void Board<n, m>::print_error (std::ostream &stream)
{
    for (int i = 0; i < n * m; ++i)
    {
        for (int j = 0; j < n * m; ++j)
        {
            stream << 0;
            
            if ((j + 1) != n * m)
            {
                if ((j + 1) % n == 0)
                    stream << " ";

                stream << " ";
            }
        }        

        if ((i + 1) % m == 0)
            stream << std::endl;

        stream << std::endl;
    }    
}

template<int n, int m>
void Board<n, m>::set_single (int row, int col, int v)
{
    fields (row, col).set_single (v);

    for (int i = 0; i != n * m; ++i)
    {
        if (i != row)
            fields(i, col).eliminate (v);
    }

    for (int j = 0; j != n * m; ++j)
    {
        if (j != col)
            fields(row, j).eliminate (v);
    }

    int square_row = (row / m) * m;
    int square_col = (col / n) * n;
    
    for (int i = square_row; i != square_row + m; ++i)
    {
        for (int j = square_col; j != square_col + n; ++j)
        {
            if (i != row && j != col)
                fields(i, j).eliminate (v);
        }
    }
}

template<int n, int m>
void Board<n, m>::read (std::istream &stream)
{
    int i = 0;
    int value;
    int fields_input[(n * m) * (n * m)];
    
    while (stream >> value && i < (n * m) * (n * m))
    {
        if (!(0 <= value && value <= n * m))
            throw io_error ();

        fields_input[i++] = value;
    }

    if (i != (n * m) * (n * m) || !stream.eof ())    
        throw io_error ();

    // Enter input into solution grid
    for (int i = 0; i != (n * m) * (n * m); ++i)
    {
        if (fields_input[i])
            set_single (i / (n * m), i % (n * m), fields_input[i]);
    }

}

template<int n, int m>
void Board<n, m>::solve ()
{
    // Elimination based on already deducted single values
    for (int row = 0; row != n * m; ++row)
    {
        for (int col = 0; col != n * m; ++col)
        {                
            int single_value = fields(row, col).value ();
            if (single_value)
                set_single (row, col, single_value);
        }
    }

    // Backtrack
    for (int row = 0; row != n * m; ++row)
    {
        for (int col = 0; col != n * m; ++col)
        {
            if (!fields(row, col).definite ())
            {
                for (int i = 1; i != n * m + 1; ++i)
                {
                    if (fields(row, col)[i])
                    {
                        FieldMatrix<n, m> fields_copy = fields;
                        fields(row, col).set_single (i);
                        try
                        {
                            solve ();
                            return;
                        } catch (contradiction_error&) {
                            fields = fields_copy;
                        }
                    }
                }

                throw contradiction_error();
            }
        }
    }
}

//----------------------------------------------------
// main
//----------------------------------------------------

#include <fstream>

int main (int argc, char **argv)
{
    typedef Board<3, 3> SudokuBoard;
    SudokuBoard board;

    try
    {
        std::ifstream stream (argv[1]);
        
        board.read (stream);
        board.solve ();
        board.print (std::cout);
    } catch (sudoku_error&) {
        SudokuBoard::print_error (std::cerr);
        return 1;
    }
    
    return 0;
}