#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;
}