バックトラック。
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define TOP 0 #define RIGHT 1 #define BOTTOM 2 #define LEFT 3 vector<string> puz(9); vector<string> cur(9); bool done[9]; int ret; bool diff(char a,char b){ if(a != b && tolower(a) == tolower(b))return true; return false; } bool check(int p){ const int di[] = {3,-1,-3,1}; const int target[] = {TOP,RIGHT,BOTTOM,LEFT}; const int self[] = {BOTTOM,LEFT,TOP,RIGHT}; rep(i,4){ if( p%3==0 && i == 1)continue; if( p%3==2 && i == 3)continue; int t = p+di[i]; if(t<0 || t>=9 || cur[t]== "")continue; if(!diff(cur[t][target[i]],cur[p][self[i]]))return false; } return true; } void bt(int x){ if( x == 9){ ret++; return; } rep(i,9){ if(done[i])continue; rep(loop,4){ rotate(puz[i].begin(),puz[i].begin()+1,puz[i].end()); cur[x] = puz[i]; done[i] = true; if(check(x))bt(x+1); done[i] = false; cur[x] = ""; } } return; } int main(){ int n; cin >> n; while(n--){ rep(i,9)cin >> puz[i]; ret = 0 , bt(0); cout << ret << endl; } }