#include <iostream>
#include <string>
#include <ctime>
#include <cmath>

using namespace std;

class Sudoku {
public:
    static const int SIZE = 4;    
    Sudoku();
    string GetPrize();
    void ShowPuzzle(ostream &);
    void ShowSolution(ostream &);
    bool IsSolution(istream &);
private:
    int board[SIZE][SIZE];
    int puzzle[SIZE][SIZE];
    string prize;    
    void Init();
    bool IsSudoku(int board[][SIZE]);
    void Introduction();
    void Show(ostream &, const int [][SIZE]);
};

bool Sudoku::IsSudoku(int board[][SIZE]) {
    int numbers[SIZE];

    // check verticals
    for(int j = 0; j < SIZE; j++) {
        for(int k = 0; k < SIZE; k++)
            numbers[k] = 1;
        for(int i = 0; i < SIZE; i++) {
            if(numbers[board[i][j] - 1] == 0)
                return false;
            numbers[board[i][j] - 1] = 0;
        }
    }

    // check sub-grids
    int subSize = sqrt(SIZE);
    for(int i = 0; i < subSize; i++)
        for(int j = 0; j < subSize; j++) {
            for(int k = 0; k < SIZE; k++)
                numbers[k] = 1;
            for(int k = subSize * i; k < subSize * i + subSize; k++)
                for(int l = subSize * j; l < subSize * j + subSize; l++) {
                    if(numbers[board[k][l] - 1] == 0)
                        return false;
                    numbers[board[k][l] - 1] = 0;
                }
        }

    // all good!
    return true;
}

void Sudoku::Init() {
    prize = "bonsai";
    do {
        for(int i = 0; i < SIZE; i++)
            for(int j = 0; j < SIZE; j++) {
                int r;
                bool found;
                do {
                    r = rand() % SIZE + 1;
                    found = false;
                    for(int k = 0; k < j; k++)
                        if(r == board[i][k]) {
                            found = true;
                            break;
                        }
                }
                while(found);
                board[i][j] = r;
            }
    }
    while(!IsSudoku(board));

    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(rand() % 4 < 1) 
                puzzle[i][j] = 0;
            else
                puzzle[i][j] = board[i][j];
}

Sudoku::Sudoku() {
    srand(time(NULL));
    Init();
    Introduction();
}

void Sudoku::Introduction() {
    cout << "Welcome! Do you like Sudoku?" << endl;
    cout << "To win a prize, you must find the answer." << endl;
}

string Sudoku::GetPrize() {
    return prize;
}

void Sudoku::Show(ostream &out, const int board[][SIZE]) {
    for(int i = 0; i < SIZE; i++) {
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] == 0)
                out << " _ ";
            else
                out << " " << board[i][j] << " ";
        out << endl;
    }
}

void Sudoku::ShowSolution(ostream &out) {
    Show(out, board);
}

void Sudoku::ShowPuzzle(ostream &out) {
    Show(out, puzzle);
}

bool Sudoku::IsSolution(istream &in) {
    cout << "Enter your solution separated by white space." << endl;
    cout << "You should enter the WHOLE Sudoku." << endl;
    cout << endl; 
    
    int solution[SIZE][SIZE];

    // read solution
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            in >> solution[i][j];

    // check if the solution is valid
    if(!IsSudoku(solution))
        return false;

    // check if it is a solution for the puzzle
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(puzzle[i][j] != 0 && puzzle[i][j] != solution[i][j])
                return false;

    return true;
}

int main() {
    Sudoku sudoku;
    sudoku.ShowPuzzle(cout);
    cout << endl;
    if(sudoku.IsSolution(cin))
        cout << "Nice job! Your prize is a " << sudoku.GetPrize() << endl;
    else {
        cout << "Sorry, but this is not a solution. Best of luck next time!" << endl;
        cout << "Here is one possible solution: " << endl;
        sudoku.ShowSolution(cout);
    }

    return EXIT_SUCCESS;
}