#include <iostream>
#include <stdint.h>
#include <iomanip>
#include <sys/time.h>
#include <string>
 
using namespace std;
 
int p[12][3][3] = {{{15, 4, 3},{0, 0, 0},{0, 0, 0}},{{4, 0, 0},{1, 0, 0},{6, 0, 0}},{{6, 0, 0},{3, 0, 0},{3, 0, 0}},{{15, 1, 1},{0, 0, 0},{0, 0, 0}},{{6, 0, 0},{1, 4, 0},{0, 0, 0}},{{0, 1, 0},{3, 4, 0},{0, 0, 0}},{{5, 0, 0},{1, 3, 0},{0, 0, 0}},{{0, 21, 0},{60, 1, 0},{0, 6, 0}},{{12, 0, 0},{60, 6, 0},{0, 0, 0}},{{0, 1, 0},{2, 3, 0},{0, 0, 0}},{{12, 0, 0},{3, 0, 0},{0, 0, 0}},{{0, 12, 0},{1, 5, 0},{0, 0, 0}}};
 
string colors[12] = {"yellow", "red", "green", "magenta", "blue", "lightblue", "orange", "cyan", "lightgreen", "brown", "purple", "grey"};
 
bool u[12];
int32_t g[7][7];
int32_t c[7][7];
uint64_t t;
 
inline int32_t off(int32_t s) {
	return (s == 5 || s == 7 || s == 9 || s == 11) ? -1 : 0;
}
 
inline bool valid(int32_t xx, int32_t yy, int32_t s) {
	if (xx < 0) return false;
	for (int32_t x = 0; x < 3; ++x) {
		for (int32_t y = 0; y < 3; ++y) {
			if (p[s][y][x] == 0) continue;
			if (g[xx + x][yy + y] || (xx + x > 0 && g[xx + x - 1][yy + y] != 0 && !(!(p[s][y][x] % g[xx + x - 1][yy + y]) || !(g[xx + x - 1][yy + y] % p[s][y][x]))) || (yy + y > 0 && g[xx + x][yy + y - 1] != 0 && !(!(p[s][y][x] % g[xx + x][yy + y - 1]) || !(g[xx + x][yy + y - 1] % p[s][y][x]))) || (xx + x < 5 && g[xx + x + 1][yy + y] != 0 && !(!(p[s][y][x] % g[xx + x + 1][yy + y]) || !(g[xx + x + 1][yy + y] % p[s][y][x]))) || (yy + y < 5 && g[xx + x][yy + y + 1] != 0 && !(!(p[s][y][x] % g[xx + x][yy + y + 1]) || !(g[xx + x][yy + y + 1] % p[s][y][x])))) return false;
		}
	}
	return true;
}
 
void find(int32_t x, int32_t y) {
	if (x == 6 && y == 6) {
		cout << "Solution: " << endl;
		cout << "<table>";
		for (int32_t i = 0; i < 6; ++i) {
			cout << "<tr>" << endl;
			for (int32_t j = 0; j < 6; ++j) {
				cout << "<td style=\"font-weight: bold; text-align: center; width:30px; height:30px; background:" << colors[c[j][i]] << "\">" << setw(3) << g[j][i] << "</td>";
			}
			cout << "</tr>" << endl;
		}
		cout << "</table>";
		return;
	}
	if (x == 6) return find(0, y + 1);
	if (g[x][y] > 0) return find(x + 1, y);
	for (int32_t i = 0; i < 12; ++i) {
		if (!u[i] && valid(x + off(i), y, i)) {
			u[i] = true;
			for (int32_t xx = 0; xx < 3; ++xx) {
				for (int32_t yy = 0; yy < 3; ++yy) {
					if (p[i][yy][xx]) {
						g[x + xx + off(i)][y + yy] = p[i][yy][xx];
						c[x + xx + off(i)][y + yy] = i;
					}
				}
			}
			t++;
			find(x + 1, y);
			for (int32_t xx = 0; xx < 3; ++xx) {
				for (int32_t yy = 0; yy < 3; ++yy) {
					if (p[i][yy][xx]) {
						g[x + xx + off(i)][y + yy] = 0;
						c[x + xx + off(i)][y + yy] = i;
					}
				}
			}
			u[i] = false;
		}
	}
} 
 
int main() {
	for (int32_t i = 0; i < 7; i++) g[6][i] = g[i][6] = 1;
 
	struct timeval begin, end;
 
	gettimeofday(&begin, (struct timezone*)NULL);	
	find(0, 0);
	gettimeofday(&end, (struct timezone*)NULL);
 
	cout << "Solving took " << end.tv_usec - begin.tv_usec << " microseconds. Total of " << t << " tries." << endl;
 
	return 0;
}