import std.stdio;
import std.string;
import std.cstream;


struct Game
{
	char[81] value;
	ushort[81] mask;
	int count;

	int working;
	int guess;
	ushort guessMask;

}

//bool[81] changed;

class Block:Error{this(char[]c){super(c);}}

int main()
{
	Game current;
	Game[81] stack;
	int at;
	int iter;

	void Report(int z)
	{
		static char[] value = ".123456789";
debug		writef(
"
depth      = %d
found      = %d
iterations = %d
working    = %d
guess      = %d\n\n",
at, current.count, iter, current.working, current.guess);
		for(int y = 0; y < 9; y++)
		{
			for(int x = 0; x < 9; x++)
			{
				writef("%d  ",// value[
				current.value[y*9+x]);//]);
				if(2 == x%3) writef("  ");
			}
			writef("\n");
			if(2 == y%3) writef("\n");
		}

		debug for(int y = 0; y < 9; y++)
		{
			for(int x = 0; x < 9; x++)
			{
				int i = 0;
				ushort t = current.mask[y*9+x];
				for(int z=0; z<9; z++)
				{
					writef((t & 0x0100) ? "." : "!");
					i+=(t & 0x0100) ? 0 : 1;
					t<<=1;
				}

				writef("%d  ",i);
				if(2 == x%3) writef("  ");
			}
			writef("\n");
			if(2 == y%3) writef("\n");

		}
	};

	
//	int loop = 0; restart: loop++;

	at=0;
	current.count=0;
	current.working = -1;
	for(int i = 0; i<81; i++)
	{
		current.value[i] = 0;
		current.mask[i] = 0x0;
	}

	static byte[81] seeds = [
		0, 0, 0,  0, 0, 7,  4, 0, 2,
		7, 0, 0,  6, 0, 0,  0, 5, 8,
		0, 0, 5,  0, 8, 2,  0, 0, 0,

		0, 0, 8,  4, 0, 0,  0, 0, 7,
		3, 0, 0,  0, 0, 0,  0, 0, 4,
		0, 0, 0,  0, 0, 1,  9, 0, 0,

		0, 0, 0,  7, 3, 0,  6, 0, 0,
		9, 7, 0,  0, 0, 5,  0, 0, 3,
		1, 0, 3,  8, 0, 0,  0, 0, 0
		];

	foreach(int i, c;seeds)
		setValue(current, i, c);

//	Report(0);	writef(\n\n);

	bool delta;
	int v;

	do
	{
		do
		{
			delta = false;
			for(int c=0; c<80; c++)
			{
				switch(current.mask[c])
				{
					case 0x01ff:
						goto backUp;

					default:
					case 0xffff:
						continue;

					case 0x00ff:	v = 9; break;
					case 0x017f:	v = 8; break;
					case 0x01bf:	v = 7; break;
					case 0x01df:	v = 6; break;
					case 0x01ef:	v = 5; break;
					case 0x01f7:	v = 4; break;
					case 0x01fb:	v = 3; break;
					case 0x01fd:	v = 2; break;
					case 0x01fe:	v = 1; break;
				}
				setValue(current, c, v);
				delta = true;
			}
		}while (delta)

		while(false)	// skip this block unless we get here by goto
		{
			backUp:
			assert(0 < at);
			at--;
			current = stack[at];
			current.mask[current.working] ^= current.guessMask;
			debug writef("<<<<< backup %d\n", at);
		}

		with(current)
		{
				// find a unknown cell
			while(working == -1 || 0 != value[working])
			{
				working++;
				guess = 1;
				guessMask = 0x01;
			}

				// find an avalable value
			while(0 != (mask[working] & guessMask))
			{
				guess++;
				guessMask<<=1;
				if(9 < guess) goto backUp;
			}
		}

		// store off state
		stack[at] = current;
		at++;

		debug writef("cell=%d guess=%d\n", current.working, current.guess);
		//make move
		setValue(current, current.working, current.guess);

		
		iter++;

	}while(current.count < 81)

//	if(loop<1000) goto restart;
	Report(0);
	return 0;
}

byte[20][81] depends;
static this()
{
	int at;
	for(int set = 0; set<81; set++)
	{
		at=0;
		for(int to = 0; to<81; to++)
		{
			if(set == to) continue;
			if(	set/9 == to/9 ||
				set%9 == to%9 || 
				(
					(set/3)%3 == (to/3)%3 &&
					set/27 == to/27
				)
			)
				depends[set][at++] = to;
		}
		assert(at == 20);
	}
}


bool setValue(inout Game where, int what, int to)
{
	if(0 == to || 9 < to) return false;
	bool ret = false;
	short mask = 0x0001 << (to-1);

//	if(where.value[what] || where.mask[what] & mask) throw new Error(__FILE__":" ~ itoa!(__LINE__)~" error\n");

	where.value[what] = to;
	where.mask[what] = 0xffff;
	where.count++;

	foreach(c;depends[what])
		where.mask[c] |= mask;

	return ret;
}











template decimalDigit(int n){const char[] decimalDigit = "0123456789"[n..n+1];} 
template itoa(long n){
	static if (n < 0)		const char[] itoa = "-" ~ itoa!(-n);  
	else static if (n < 10)		const char[] itoa = decimalDigit!(n); 
	else				const char[] itoa = itoa!(n/10L) ~ decimalDigit!(n%10L); }