#include "stdafx.h"
#include "TableDef.h"
#include "time.h"
#include "windows.h"

#define IndexEnd 41
#define PUSHSINGLE(i) {posStack[SCnt] = i; valueStack[SCnt++] = G[PIdx].area[mult162[i]];}

LARGE_INTEGER Frequency;
LARGE_INTEGER StartTime;
LARGE_INTEGER EndTime;
double SpendTime;

struct GameBoard {
	int area[4374];
	int left[27];
	int SCnt;
	int cntGuessed;
} G[IndexEnd];

int posStack[27];
int valueStack[27];
int SCnt;
int PIdx;
int flagAnswer;
char str[83];

inline bool initArea()
{
	int i, j;
	int value;
	int squareNo;
	int list[81];
	int temp;
	int pList0, pList1, pList2;
	int listStack0[9], listStack1[9], listStack2[9];
	int p0, p1, p2;
	int temp2;
	SCnt = 0;
	for(i=0; i<81; i++)
	{
		list[i] = 511;
	}
	// board to list[81]
	for(i=0; i<81; i++)
	{
		if((value=str[i]-'1') == -1) // str[i] is '0'
		{
			continue;
		}
		squareNo = squareNoTbl[i];
		temp = mult9[value] + squareNo;
		temp2 = ~areaTrans[i];
		for(j=squareNo; j<81; j+=9)
		{
			list[j] = list[j] & temp2;
		}
		list[temp] = areaTrans[i];
		if(mod3[squareNo] == 0)
		{
			list[temp+1] &= areaRow[i];
			list[temp+2] &= areaRow[i];
		}
		else if(mod3[squareNo] == 1)
		{
			list[temp-1] &= areaRow[i];
			list[temp+1] &= areaRow[i];
		}
		else
		{
			list[temp-2] &= areaRow[i];
			list[temp-1] &= areaRow[i];
		}
		if(squareNo < 3)
		{
			list[temp+3] &= areaColumn[i];
			list[temp+6] &= areaColumn[i];
		}
		else if(squareNo < 6)
		{
			list[temp-3] &= areaColumn[i];
			list[temp+3] &= areaColumn[i];
		}
		else
		{
			list[temp-6] &= areaColumn[i];
			list[temp-3] &= areaColumn[i];
		}
	}
	// legal check
	for(i=0; i<81; i++)
	{
		if((value=str[i]-'1') != -1 && list[mult9[value]+squareNoTbl[i]] != areaTrans[i])
		{
			return false;
		}
	}
	for(i=0; i<81; i+=3)
	{
		// compress list[81] to pList0, pList1, pList2
		pList0 = pList1 = pList2 = 0;
		while((temp=lastOneTbl[list[i]]) != 9)
		{
			listStack0[pList0++] = temp;
			list[i] = list[i] & ~(1<<temp);
		}
		while((temp=lastOneTbl[list[i+1]]) != 9)
		{
			listStack1[pList1++] = temp;
			list[i+1] = list[i+1] & ~(1<<temp);
		}
		while((temp=lastOneTbl[list[i+2]]) != 9)
		{
			listStack2[pList2++] = temp;
			list[i+2] = list[i+2] & ~(1<<temp);
		}
		// set G[0].area and G[0].left
		G[0].left[divide3[i]] = 0;
		for(p0=0; p0<pList0; p0++)
		{
			for(p1=0; p1<pList1; p1++)
			{
				temp2 = mult81[listStack0[p0]]+mult9[listStack1[p1]];
				for(p2=0; p2<pList2; p2++)
				{
					if((temp=create[temp2+listStack2[p2]]) != 162)
					{
						G[0].area[mult162[divide3[i]]+G[0].left[divide3[i]]++] = temp;
					}
				}
			}
		}
	}
	for(i=0; i<27; i++)
	{
		if((temp=G[0].left[i]) == 0)
		{
			return false;
		}
		else if(temp == 1)
		{
			PUSHSINGLE(i);
		}
	}
	return true;
}

inline bool update(int i)
{
	int m, n;
	int thisArea, thatIndex;
	// self check
	thisArea = mult162[G[PIdx].area[mult162[i]]];
	for(m=trim3[i]-3; m<trim3[i]; m++)
	{
		if(m == i)
		{
			continue;
		}
		for(n=0; n<G[PIdx].left[m]; n++)
		{
			thatIndex = mult162[m] + n;
			if(self[thisArea+G[PIdx].area[thatIndex]])
			{
				G[PIdx].area[thatIndex] = G[PIdx].area[mult162[m]+--G[PIdx].left[m]];
				if(G[PIdx].left[m] == 0)
				{
					return false;
				}
				else if(G[PIdx].left[m] == 1)
				{
					PUSHSINGLE(m);
				}
				n--;
			}
		}
	}
	// other check
	for(m=mod3[i]; m<27; m+=3)
	{
		if(m == i)
		{
			continue;
		}
		for(n=0; n<G[PIdx].left[m]; n++)
		{
			thatIndex = mult162[m] + n;
			if(other[thisArea+G[PIdx].area[thatIndex]])
			{
				G[PIdx].area[thatIndex] = G[PIdx].area[mult162[m]+--G[PIdx].left[m]];
				if(G[PIdx].left[m] == 0)
				{
					return false;
				}
				else if(G[PIdx].left[m] == 1)
				{
					PUSHSINGLE(m);
				}
				n--;
			}
		}
	}
	return true;
}

void getAnswer()
{
	int i;
	int temp;
	int least;
	int multLeast;
	int leastArea[IndexEnd];
	flagAnswer = 0;
	if(initArea() == false)
	{
		return;
	}
	PIdx = 0;
	G[0].SCnt = 0;
	G[0].cntGuessed = 0;
next:
	for(i=G[PIdx].SCnt; i<SCnt; i++)
	{
		if(!update(posStack[i]))
		{
again:		if(--PIdx == -1)
			{
				return;
			}
			else if(G[PIdx].left[leastArea[PIdx]] == 0)
			{
				goto again;
			}
			// swap cntGuessed, 0
			least = leastArea[PIdx];
			multLeast = mult162[least];
			temp = G[PIdx].area[multLeast];
			G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed];
			G[PIdx].area[multLeast+G[PIdx].cntGuessed] = temp;
			SCnt = G[PIdx+1].SCnt;
			PUSHSINGLE(least);
			G[PIdx].left[least]--;
			G[PIdx+1] = G[PIdx];
			G[PIdx].cntGuessed++;
			G[PIdx+1].cntGuessed = 0;
			G[PIdx+1].SCnt = SCnt-1;
			PIdx++;
			G[PIdx].left[leastArea[PIdx-1]] = 1;
			goto next;
		}
	}
	if(i == 27)
	{
		if(flagAnswer == 0)
		{
			flagAnswer = 1;
			goto again;
		}
		else
		{
			flagAnswer = 2;
			return;
		}
	}
	least = 163;
	for(i=0; i<27; i++)
	{
		if(G[PIdx].left[i] < least && G[PIdx].left[i] != 1)
		{
			least = G[PIdx].left[i];
			leastArea[PIdx] = i;
			if(least == 2)
			{
				break;
			}
		}
	}
	// swap cntGuessed, 0
	least = leastArea[PIdx];
	multLeast = mult162[least];
	temp = G[PIdx].area[multLeast];
	G[PIdx].area[multLeast] = G[PIdx].area[multLeast+G[PIdx].cntGuessed];
	G[PIdx].area[multLeast+G[PIdx].cntGuessed] = temp;
	PUSHSINGLE(least);
	G[PIdx].left[least]--;
	G[PIdx+1] = G[PIdx];
	G[PIdx].cntGuessed++;
	G[PIdx+1].SCnt = SCnt-1;
	PIdx++;
	G[PIdx].left[leastArea[PIdx-1]] = 1;
	goto next;
}

int main(int argc, char* argv[])
{
	QueryPerformanceFrequency(&Frequency);
	while(fgets(str, 83, stdin))
	{
		QueryPerformanceCounter(&StartTime);
		getAnswer();
		QueryPerformanceCounter(&EndTime);
		SpendTime = (double)(EndTime.QuadPart-StartTime.QuadPart)*1000/(double)Frequency.QuadPart;
		printf("%f ms       ", SpendTime);
		printf("Result: %d\n", flagAnswer);
	}
	return 0;
}
