domino

#include<iostream>
#define endl '\n'
using namespace std;

int map[8][9];
int visit[8][9];
int ans;
bool domino[7][7];

void input()
{
	for(int i = 0; i < 7; ++i)
		for(int j = 0; j < 8; ++j)
			cin >> map[i][j];
}

void init_domino()
{
	for(int i = 0; i < 7; ++i)
		for(int j = 0; j < 7; ++j)
			domino[i][j] = 1;
}

bool check (int x, int y, int nx, int ny)
{
	if(domino[map[x][y]][map[nx][ny]])	return true;
	return false;
}

void backtrack(int x, int y)
{
	if(y == 8 && x == 6)	{ans++;	return;}
	if(y == 8 && x != 6)	{backtrack(x+1,0); return;}	//Neu o ria duyet ngang ma x chua end -> xuong dong
	if(visit[x][y] == 1)	{backtrack(x,y+1); return;}	//Neu o visit -> duyet ngang
	
	visit[x][y] = 1;
	if(y + 1 < 8 && visit[x][y+1] == 0 && check(x,y,x,y+1))	//check xem backtrack ngang duoc khong
	{
		visit[x][y+1] = 1;
		domino[map[x][y]][map[x][y+1]] = 0;
		domino[map[x][y+1]][map[x][y]] = 0;
		backtrack(x,y+2);
		domino[map[x][y+1]][map[x][y]] = 1;
		domino[map[x][y]][map[x][y+1]] = 1;
		visit[x][y+1] = 0;
	}

	if(x + 1 < 7 && visit[x+1][y] == 0 && check(x,y,x+1,y))	//check xem backtrack ngang duoc khong
	{
		visit[x+1][y] = 1;
		domino[map[x][y]][map[x+1][y]] = 0;
		domino[map[x+1][y]][map[x][y]] = 0;
		backtrack(x,y+1);
		domino[map[x][y]][map[x+1][y]] = 1;
		domino[map[x+1][y]][map[x][y]] = 1;
		visit[x+1][y] = 0;
	}
	visit[x][y] = 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		ans = 0;
		input();
		init_domino();
		backtrack(0,0);

		cout << "#" << tc << " " << ans << endl;
	}

	return 0;
}