#include <iostream>
#include <tuple>
#include <vector>
#include <unordered_map>


#define YELLOW      0
#define BLUE        1
#define GREEN       2
#define ORANGE      3
#define RED         4

#define MAX_COLOURS 5


void row_moved(std::vector<unsigned char> & board, unsigned row)
{
    using std::swap;

    int row_start = row * 4;

    swap(board[row_start + 3], board[row_start + 2]);
    swap(board[row_start + 2], board[row_start + 1]);
    swap(board[row_start + 1], board[row_start + 0]);
}

void col_moved(std::vector<unsigned char> & board, unsigned col)
{
    using std::swap;

    swap(board[col + 12], board[col + 8]);
    swap(board[col + 8], board[col + 4]);
    swap(board[col + 4], board[col + 0]);
}


bool check_fill(std::vector<unsigned char> & board, unsigned char value)
{
    std::vector<unsigned char> zeroes;
    int I;
    for(I = 0; I < 16; I++)
    {
        if(board[I] == value)
        {
            zeroes.push_back(I);
            break;
        }
    }

    while(!zeroes.empty())
    {
        int i = zeroes.back();
        zeroes.pop_back();

        int x = i % 4;
        int y = i / 4;

        board[i] = 255;

        // left
        if(x > 0 && (board[i - 1] == value))
            zeroes.push_back(i - 1);
        // right
        if(x < 3 && (board[i + 1] == value))
            zeroes.push_back(i + 1);
        // up
        if(y > 0 && (board[i - 4] == value))
            zeroes.push_back(i - 4);
        // down
        if(y < 3 && (board[i + 4] == value))
            zeroes.push_back(i + 4);
    }

    for(int i = I + 1; i < 16; i++)
    {
        if(board[i] == value)
        {
            return false;
        }
    }

    return true;
}

/* passage par copie obligatoire */
bool solution(std::vector<unsigned char> board)
{
    for(unsigned char colour = 0; colour < MAX_COLOURS; colour++)
    {
        if(!check_fill(board, colour))
        {
            return false;
        }
    }
    return true;
}

void display(const std::vector<unsigned char>& board) {
    int i = 0;
    for(auto & cell : board)
    {
        ++i;
        std::cout << (int)cell << " ";
        if(i % 4 == 0) std::cout << std::endl;
    }
    std::cout << std::endl;
}

// use this type for cache
#define T   uint64_t

int checkedGrids = 0;
int solutions = 0;
std::unordered_map<T, int> cache;


// peut fonctionner jusqu'à 8 couleurs différentes
inline uint64_t hashable(const std::vector<unsigned char>& v)
{
    uint64_t ret = 0;
    for (unsigned i=0,j=0; i<16; ++i,j+=3) {
        ret |= ((uint64_t)v[i]) << j;
    }
    return ret;
}

void check_solution(const std::vector<unsigned char>& board,
                    std::vector<std::tuple<char, int, int>>& moves,
                    int remaining_moves)
{
    T sboard = hashable(board);
    auto cached = cache.find(sboard);
    if(cached != cache.end() && cached->second >= remaining_moves)
        return;
    cache[sboard] = remaining_moves;

    ++checkedGrids;
/*
    if(checkedGrids % 100000 == 0)
        std::cout << checkedGrids << " checkedGrids" << std::endl;
*/

    if (solution(board))
    {
        solutions++;
/*
        for(auto & move : moves)
        {
            std::cout << std::get<0>(move) << " " << std::get<1>(move) << " " << std::get<2>(move) << std::endl;
        }
        std::cout << std::endl;
*/
    }
    else if (remaining_moves > 0)
    {
        const int j = std::get<1>(moves.back());
        const char axis = std::get<0>(moves.back());

        moves.emplace_back('*', -1, -1); // placeholder

        for(int i = 0; i < 4; ++i)
        {
            // assign current row/col
            std::get<1>(moves.back()) = i;

            auto gridR = board;
            std::get<0>(moves.back()) = 'r';
            for(int move = 1; move <= 3; ++move)
            {
                row_moved(gridR, i); // rotate one by one

                // don't move twice on the same axis
                if(axis != 'r' || j != i)
                {
                    // assign current rotation
                    std::get<2>(moves.back()) = move;
                    check_solution(gridR, moves, remaining_moves - 1);
                }
            }

            auto gridC = board;
            std::get<0>(moves.back()) = 'c';
            for(int move = 1; move <= 3; ++move)
            {
                col_moved(gridC, i); // rotate one by one

                // don't move twice on the same axis
                if(axis != 'c' || j != i)
                {
                    // assign current rotation
                    std::get<2>(moves.back()) = move;
                    check_solution(gridC, moves, remaining_moves - 1);
                }
            }
        }

        moves.pop_back();
    }
}

#define MAX_DEPTH   5
int main()
{
    std::vector<unsigned char> board =
    {
        GREEN,  ORANGE, GREEN,  ORANGE,
        BLUE,   BLUE,   BLUE,   BLUE,
        BLUE,   YELLOW, RED,    BLUE,
        BLUE,   RED,    YELLOW, BLUE,
    };

    auto v = std::vector<std::tuple<char, int, int>>();
    v.reserve(MAX_DEPTH+1);
    v.emplace_back('*',-1,-1); // hack
    check_solution(board, v, MAX_DEPTH);

    std::cout << checkedGrids << " checkedGrids" << std::endl;
    std::cout << solutions << " solutions" << std::endl;
    std::cout << cache.size() << " grids in cache" << std::endl;

    return 0;
}