IMPA/p10957/p10957.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <list>

using namespace std;

typedef unsigned int nat;

vector<vector<nat>> sudoku(9, vector<nat>(9,0));

void reset_sudoku()
{
    for(auto &c : sudoku)
    {
        for(auto &cell : c)
        {
            cell = 0;
        }
    }
}

bool set_pos(pair<nat,nat> pos, nat val)
{
    if(val)
    {
        for(auto &c : sudoku)
        {
            if(c[pos.second] == val)
                return false;
        }
        for(auto &cell : sudoku[pos.first])
        {
            if(cell == val)
                return false;
        }
        for(nat y = 3*(pos.second/3); y < 3*(pos.second/3)+3; ++y)
        {
            for(nat x = 3*(pos.first/3); x < 3*(pos.first/3)+3; ++x)
            {
                if(sudoku[x][y] == val)
                    return false;
            }
        }
    }

    sudoku[pos.first][pos.second] = val;
    return true;
}

bool get_next(pair<nat,nat> &pos)
{
    for(nat y = 0; y < 9; ++y)
    {
        for(nat x = 0; x < 9; x++)
        {
            if(!sudoku[x][y])
            {
                pos = {x,y};
                return true;
            }
        }
    }

    return false;
}

void print_sudoku()
{
    for(nat y = 0; y < 9; ++y)
    {
        for(nat x = 0; x < 9; x++)
        {
            cout << sudoku[x][y] << " ";
        }
        cout << endl;
    }
}

nat solve( )
{
    pair<nat,nat> next_cell;
    nat solutions = 0;
    if(get_next(next_cell))
    {
        bool possible = false;
        for(nat i = 1; i < 10; ++i)
        {
            if(set_pos(next_cell, i))
            {
                possible = true;
                solutions += solve();
                set_pos(next_cell, 0);
                if(solutions > 1)
                    return solutions;
            }
        }
        if(!possible)
            return 0;
        else
            return solutions;
    }
    //cout << "One solution is:" << endl;
    //print_sudoku();
    return 1;
}



int main()
{
    nat test_case = 1;
    while(true)
    {
        reset_sudoku();
        bool success = true;
        for(nat y = 0; y < 9; ++y)
        {
            for(nat x = 0; x < 9; x++)
            {
                nat val;
                cin >> val;
                if(cin.eof())
                    return 0;

                success = success && set_pos( {x, y}, val );
            }
        }

        cout << "Case " << test_case++ << ": ";

        if(success)
        {
            //print_sudoku();

            nat s = solve();

            if(s == 0)
                cout << "Impossible." << endl;
            else if(s == 1)
                cout << "Unique." << endl;
            else
                cout << "Ambiguous." << endl;
        }
        else
        {
            cout << "Illegal." << endl;
        }
    }
    return 0;
}