Gears Out!


- 基本的には多色ライツアウトなので、(bitsetからvalarrayに変更した上で)排他的論理和をmod int演算に置き換えればよいです。
- ただし、掃き出すときに、最初になるべく1や3の要素を残すようにする必要があります。(3の回転を3回やれば1回分になりますが)2の回転から1回分を作ることはできないためです。
- それにしても、やはりまだ解の存在判定部分が苦手と感じた。 **というか4x4/9x9は解が1対1対応しないので確認部分の実装が厳しい。**
- 0解(quiet pattern)の重ね合わせを全探索して最短手数を出力する処理は未実装です。

```cpp:tyama_henae26.cpp
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <valarray>
#include <algorithm>
#define coor(i,j) ((i)+(j)*m)
#define in(i,j) (0<=(i)&&(i)<m&&0<=(j)&&(j)<n)
using namespace std;

int main(){
	int t=0,T,m,n,d=2;
	int i,j,k;
	int success,ans;
	for(cin>>T;t<T;t++){
		if(t)puts("");
		printf("%d\n",t);
		cin>>m;n=m;
		vector<valarray<int>> M;
		for(int i=0;i<m*n;i++)M.push_back(valarray<int>(m*n*2));
		for(j=0;j<n;j++){
			for(i=0;i<m;i++){
				M[coor(i,j)][coor(i,j)]=1;
				M[coor(i,j)][m*n+i+j*m]=1;
				if(in(i-1,j))M[coor(i-1,j)][coor(i,j)]=3;
				if(in(i+1,j))M[coor(i+1,j)][coor(i,j)]=3;
				if(in(i,j-1))M[coor(i,j-1)][coor(i,j)]=3;
				if(in(i,j+1))M[coor(i,j+1)][coor(i,j)]=3;
			}
		}

		//solve
		k=0;
		for(i=0;i<m*n;i++){
			for(j=k;j<m*n&&M[j][i]%2==0;j++);
			if(j!=m*n){
				swap(M[k],M[j]);
				if(M[k][i]==3)M[k]*=3,M[k]%=4;
			}else{
				for(j=k;j<m*n&&M[j][i]%4!=2;j++);
				if(j==m*n)continue; /// todo
				swap(M[k],M[j]);
			}
			for(j=0;j<m*n;j++)if(j!=k&&M[j][i]){
				if(M[j][i]==2)M[j]-=(M[k][i]==2?1:2)*M[k],M[j]+=8,M[j]%=4;
				else if(M[j][i]==M[k][i])M[j]-=M[k],M[j]+=4,M[j]%=4;
				else M[j]-=3*M[k],M[j]+=12,M[j]%=4;
			}
			k++;
		}
		map<string,int>ma;
		for(i=0;i<k;i++){
			int q;cin>>q;q=(5-q)%4;
			int g=0;
			for(j=0;j<i;j++)g+=M[j][i];
			g%=4;
			if((q-g)%M[i][i]){return -1;}
			int f=(q-g+4)%4/M[i][i];
			M[i]*=f,M[i]%=4;
			if(g==q)continue;
			for(j=m*n;j<m*n*2;j++){
				for(int k=0;k<M[i][j]%4;k++)ma[to_string((j-m*n)%m+1)+" "+to_string((j-m*n)/m+1)]++;
			}
		}
		for(;i<m*n;i++){
			cin>>k;
			// k...m*n: quiet patterns; implement searching shortest answer
		}
		for(auto &e:ma){
			for(i=0;i<e.second%4;i++)cout<<e.first<<endl;
		}
	}
}
```

なお、以下のケースを3.85秒で解くことができます(2414手)。
`ruby -e '40.times{puts 40.times.map{[*1..4].sample}*" "}'`

```
1
40
3 3 3 3 4 3 2 3 2 3 2 2 3 2 4 2 4 1 4 3 3 2 3 4 3 2 4 1 2 1 4 3 4 1 1 3 2 3 1 4
3 3 4 3 1 4 3 3 2 3 3 4 4 1 4 3 4 3 1 4 3 4 4 3 4 2 3 3 2 4 3 2 4 1 2 3 4 1 3 1
3 3 4 3 2 1 2 1 1 3 3 2 2 2 3 2 4 3 1 1 1 4 4 4 4 2 1 4 4 3 4 2 3 2 2 2 3 3 3 3
2 3 1 3 3 2 2 4 2 3 3 1 1 1 1 2 4 1 3 4 3 3 4 1 2 3 3 1 4 2 1 1 1 1 1 3 2 3 2 1
4 2 2 3 4 2 2 3 2 4 4 2 4 4 1 4 3 1 1 3 2 4 4 4 3 2 2 3 3 1 4 2 4 1 4 1 2 3 3 2
1 2 1 4 3 1 1 1 1 4 1 1 4 1 2 3 3 1 2 3 3 2 2 4 3 3 1 4 3 4 1 2 2 3 4 4 1 4 3 1
4 2 1 3 1 3 4 4 4 2 4 2 4 1 2 4 3 3 1 2 1 2 2 1 4 1 4 2 1 2 4 3 2 3 2 2 3 2 1 2
1 3 3 4 3 3 1 3 4 4 4 1 1 2 1 2 2 3 3 1 2 1 3 2 4 3 2 4 1 1 2 4 1 4 4 1 2 3 1 3
2 2 4 1 2 1 2 1 3 2 1 4 3 3 3 4 3 1 1 4 1 4 1 2 2 3 4 4 4 3 1 3 1 1 4 4 3 3 3 4
2 2 4 2 1 3 3 3 3 1 2 3 4 1 3 2 1 1 3 3 1 1 2 2 1 3 3 2 3 4 2 3 3 3 2 4 1 3 4 2
2 4 1 4 2 4 4 2 1 2 3 1 3 3 3 3 2 3 4 2 3 3 1 2 2 2 2 3 1 1 1 1 4 4 1 4 1 2 2 4
1 3 2 3 1 2 1 3 2 4 4 2 4 3 2 1 2 2 2 4 1 1 1 4 3 4 4 3 1 1 2 2 1 1 3 1 4 4 4 1
4 1 3 2 4 3 1 2 3 3 4 3 1 4 3 3 4 4 1 3 1 3 1 2 4 2 3 1 2 1 2 3 2 2 1 1 1 4 4 2
1 4 3 4 1 2 4 3 1 4 4 3 4 2 2 3 4 1 3 3 2 2 3 4 1 2 1 2 4 4 2 1 1 1 3 4 1 2 1 1
3 2 2 1 3 1 2 3 4 1 2 1 1 3 2 1 2 4 2 2 4 4 3 2 1 1 4 4 4 3 1 3 1 4 1 4 3 2 2 3
2 1 3 3 1 3 2 2 4 2 1 3 2 3 2 2 2 4 4 1 1 4 3 4 3 2 1 4 1 4 3 1 4 1 1 2 2 2 2 4
3 1 2 3 2 4 4 3 4 1 1 1 2 2 1 1 1 2 4 4 2 1 2 3 1 4 3 1 1 4 3 1 1 1 4 3 2 1 3 2
3 1 1 3 2 4 1 3 1 4 2 3 4 1 1 4 4 3 3 3 2 1 2 2 3 3 1 1 2 1 3 3 1 2 1 4 3 1 1 2
3 2 1 4 1 2 1 2 3 3 2 1 4 1 3 3 2 1 4 3 1 2 4 2 3 1 2 4 3 3 1 1 3 4 4 1 2 2 1 2
2 4 1 3 1 1 2 1 3 2 3 4 3 4 2 4 2 2 3 2 4 3 4 3 3 3 4 3 1 2 1 1 2 2 2 1 3 2 1 2
2 1 3 2 1 4 1 1 4 4 3 2 1 4 1 4 4 4 2 1 1 4 2 4 1 3 3 3 2 3 3 4 1 4 4 3 3 4 4 3
4 2 3 3 2 2 4 4 3 1 2 2 4 1 4 1 3 3 4 2 1 3 3 3 1 1 3 1 2 4 4 1 2 1 4 4 4 2 1 1
1 1 3 4 3 3 3 2 4 3 3 1 3 2 2 3 2 2 1 2 3 4 1 2 2 1 1 2 1 2 1 4 1 1 4 4 2 1 1 3
2 4 1 3 4 1 3 3 3 1 1 4 1 1 3 1 2 3 1 2 2 2 2 1 2 1 3 1 3 3 1 3 4 2 4 1 3 3 4 1
2 1 4 3 2 2 4 2 2 4 3 4 3 1 3 3 2 4 4 2 2 2 4 3 4 3 4 4 1 2 1 2 2 3 1 1 2 3 2 1
2 3 4 4 2 3 2 4 2 4 3 3 4 4 4 1 4 3 1 3 3 4 2 2 3 4 1 4 1 4 2 1 1 3 2 2 1 2 2 1
1 4 3 1 2 3 2 4 4 3 4 1 1 2 1 3 4 4 4 1 1 2 4 1 2 2 1 3 3 1 2 2 4 2 3 4 4 4 4 3
1 1 1 4 2 2 4 2 1 2 1 3 3 4 4 1 3 4 3 2 4 4 1 3 1 1 1 4 3 4 3 2 3 1 1 1 4 1 1 2
1 3 4 2 2 2 1 3 4 1 2 2 1 2 4 2 4 4 2 1 1 4 4 1 3 1 3 3 2 1 1 1 4 4 1 4 1 1 2 3
2 3 1 3 2 1 4 3 2 1 3 4 2 1 4 4 2 1 2 4 1 2 1 1 4 2 1 4 3 2 2 1 2 2 2 3 1 3 1 2
2 2 2 4 2 3 3 2 3 4 2 4 1 2 4 2 3 3 4 2 4 1 1 4 4 3 4 1 3 3 3 4 4 2 4 4 3 3 3 4
1 2 1 2 4 4 4 2 3 1 2 1 1 2 2 4 1 4 4 2 2 2 2 4 2 3 2 4 3 2 2 2 3 1 2 2 1 1 2 1
2 2 3 1 2 2 2 4 1 2 3 2 3 2 2 1 2 3 2 1 3 2 1 2 4 1 2 3 4 4 2 1 2 4 1 2 4 4 2 1
3 2 1 1 3 2 4 2 1 3 2 3 3 3 3 4 2 3 2 1 2 1 1 4 4 4 2 4 3 1 4 3 3 2 3 2 1 2 2 2
2 2 3 1 2 2 1 3 4 2 2 2 2 4 2 4 1 4 4 3 2 3 3 4 2 4 2 3 2 2 2 1 2 4 1 3 1 4 2 4
2 4 1 2 2 2 1 3 1 2 1 4 4 1 4 3 2 3 1 3 3 2 1 1 2 1 3 3 4 4 4 2 1 1 3 4 2 2 4 2
4 1 1 2 2 2 2 3 3 2 2 1 1 3 2 2 1 1 3 1 1 1 1 1 4 3 2 4 1 2 3 4 2 1 4 4 4 4 4 2
1 3 3 2 1 4 4 4 1 4 1 1 3 2 4 1 4 2 4 1 2 2 2 3 2 1 2 1 1 2 2 1 4 1 1 4 1 1 1 3
4 2 2 4 4 2 3 1 4 4 4 1 1 2 2 1 2 4 1 2 1 1 4 4 3 2 3 2 3 3 3 3 2 4 3 3 3 3 2 2
1 3 2 2 2 4 1 3 4 1 3 2 1 2 1 1 4 1 3 3 4 1 2 4 2 3 2 2 4 4 1 1 1 2 2 4 4 4 3 1
```