/* Author - Ajay Somani */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<iterator>
#include<map>
#include<vector>
#include<list>
#include<set>
#include<queue>
#include<cassert>
#include<deque>
#include<stack>
#include<bitset>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<ctime>
using namespace std;
#define Debug 0
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define FOR(i,a,b) for(int i=(int)(a) ; i < (int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define SZ size()
#define PB push_back
#define PF push_front
#define V(x) vector< x >
typedef V(int) VI;
typedef V(VI) VII;
typedef V(string) VS;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> PI;
#define INF 100000000
/***
* number of nodes in the dancing link for 16x16 sudoku = 16*16*16*4 + 16*16*4 + 1 = 17409
* The number of selected rows = 256
* Number of column headers = 1024
***/
#define nodes 3241
#define maxSelected 81
#define nHeaders 325
char a[16][20];
class dancingLink{
/* Algorithm assumes that the root node is 0 and all column headers are [1,1024] */
public:
/* Data objects */
int l[nodes],r[nodes],u[nodes],d[nodes],C[nodes],size[nHeaders],o[maxSelected],initialChoice,h;
-
/* this part is problem specific and to be implemented by the user */
dancingLink(); /* initialization of the dancing links :D */
void print(int k); /* output function .... specific to the problem */
int row(int x); /* returns the row of a particular node */
int choice(int col,int i); /* It gives the index of ith 1 in column col */
/* this part remains the same irrespective of the problem */
void cover(int x){ /* A function to cover a particular column c */
l[r[x]] = l[x];
r[l[x]] = r[x];
int i = x,j;
while((i = d[i]) != x){
j = i;
while((j = r[j]) != i){
size[C[j]]--;
d[u[j]] = d[j];
u[d[j]] = u[j];
}
}
}
void uncover(int x){/* A function to uncover a partucular column c */
int i=x,j;
while((i = u[i]) != x){
j = i;
while((j = l[j]) != i){
size[C[j]]++;
u[d[j]] = j;
d[u[j]] = j;
}
}
r[l[x]] = x;
l[r[x]] = x;
}
bool search(int k){/* a function which finds the solution using backtracking with algorithm 'X' */
if(r[h] == h){
print(k);return true;
}
int c,s=INF,cur = h,j;
while((cur = r[cur]) != h){
if(size[cur] < s) s = size[c = cur];
}
cover(cur = c);
while((cur = d[cur]) != c){
o[k] = row(j = cur);
while((j = r[j]) != cur){
cover(C[j]);
}
if(search(k+1)){
return true;
}
while((j = l[j]) != cur){
uncover(C[j]);
}
}
uncover(c);
return false;
}
};
dancingLink::dancingLink():h(0),initialChoice(0){
REP(i,nHeaders){
r[i] = (i+1)%nHeaders;
l[i] = (i+nHeaders-1)%nHeaders;
size[i] = 9;
}
FOR(i,nHeaders,nodes){
r[i] = ((i-nHeaders)/4)*4 + ((i-nHeaders)%4+1)%4 + nHeaders;
l[i] = ((i-nHeaders)/4)*4 + ((i-nHeaders)%4+3)%4 + nHeaders;
}
int temp[10];
FOR(i,1,nHeaders){
temp[0] = i;
REP(j,9){ temp[j+1] = choice(i-1,j);C[temp[j+1]] = i;}
REP(j,10){ d[temp[j]] = temp[(j+1)%10];u[temp[j]] = temp[(j+9)%10];}
}
/*REP(i,9) puts(a[i]);putchar(10);*/
REP(i,9) REP(j,9) if(a[i][j] != '.'){
int cur = (i*81+j*9+(a[i][j]-'1')),z;
o[initialChoice++] = cur;
z = (cur = cur * 4 + nHeaders);
while((z = r[z]) != cur){
cover(C[z]);
}
cover(C[z]);
}
}
int dancingLink::choice(int col,int no){
if(col < 81){
return (col*9+no)*4 + nHeaders;
}
else if(col < 162){
col -= 81;
return ((col/9)*81+no*9+col%9)*4+1+nHeaders;
}
else if(col < 243){
col -= 162;
return (no*81+(col/9)*9+col%9)*4+2+nHeaders;
}
else {
col -= 243;
return ((((col/9)/3)*3+(no/3))*81 + (((col/9)%3)*3+no%3)*9 + col%9)*4+3+nHeaders;
}
}
void dancingLink::print(int k){
REP(i,k) a[o[i]/81][(o[i]/9)%9]='1'+o[i]%9;
}
int dancingLink::row(int x){
return (x-nHeaders)/4;
}
int main(){
int N;scanf("%d",&N);while(N--){
char temp[100];scanf("%s",temp);
REP(i,81) a[i/9][i%9] = temp[i];
dancingLink r;
r.search(r.initialChoice);
}
return 0;
}
-