#include <stdio.h>

#define SIZE 20

int sq[SIZE][SIZE];
int allowed[SIZE][SIZE];
int row[SIZE];
int col[SIZE];
int n;
int allvec;

int nrbitset(int x)
{
	int r = 0;
	for (int i = 0; i < n; i++)
		if ((1 << i) & x)
			r++;
	return r;
}

void set(int i, int j, int k)
{
	if (sq[i][j] != 0)
	{
		printf("%d %d %d %d\n", i, j, sq[i][j], k);
		exit(1);
	}
	sq[i][j] = k+1;
	row[i] &= ~(1 << k);
	col[j] &= ~(1 << k);
}
void iset(int i, int j, int k)
{	set(i-1,j-1,k-1);
}
void reset(int i, int j)
{
	int k = sq[i][j]-1;
	sq[i][j] = 0;
	row[i] |= (1 << k);
	col[j] |= (1 << k);
}
int possiblemoves()
{
	int p = 0;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (sq[i][j] == 0)
			{
				int v = nrbitset(row[i] & col[j] & allowed[i][j]);
				if (v == 0)
					return 0;
				p += v; // v*v - (v < 2 ? 0 : v-2);
			}
			
	return p;
}

int count = 0;

bool solve(int depth)
{
	//printf("%*.*s%d\n", depth, depth, "", possiblemoves());
	struct
	{	int pm;
		int i;
		int j;
		int k;
	} sols;

	sols.pm = 0;
	
	int v;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (sq[i][j] == 0 && nrbitset(v = row[i] & col[j] & allowed[i][j]) == 1)
			{
				for (int k = 0; k < n; k++)
					if ((1 << k) & v)
					{
						set(i,j,k);
						if (solve(depth+1))
							return true;
						reset(i,j);
						
						return false;
					}
			}
	
	int o = 0;	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (sq[i][j] == 0)
			{
				o++;
				int x = row[i] & col[j] & allowed[i][j];
				for (int k = 0; k < n; k++)
					if ((1 << k) & x)
					{
						set(i,j,k);
						int pm = possiblemoves();
						reset(i,j);
	
						if (pm > sols.pm)
						{					
							sols.pm = pm;
							sols.i = i;
							sols.j = j;
							sols.k = k;
						}
					}
			}

	//printf("nrsols = %d\n", o);	
	if (o == 0)
	{
#if 0	
		for (int j = n-1; j >= 0; j--)
		{
			for (int i = 0; i < n; i++)
				printf("%3d", sq[i][j]);
			printf("\n");
		}
#else
		for (int j = n-1; j >= 0; j--)
		{
			for (int i = 0; i < n; i++)
				printf("%1d", sq[i][j]);
		}
		printf("\n");
#endif
		if (count++ > 100000)
			return true;
		//return true;
	}

	if (sols.pm > 0)
	{
		set(sols.i, sols.j, sols.k);
		if (solve(depth+1))
			return true;
		reset(sols.i, sols.j);
		allowed[sols.i][sols.j] &= ~(1 << sols.k);
		if (solve(depth+1))
			return true;
		allowed[sols.i][sols.j] |= (1 << sols.k);
	}
	
	return false;
}

int main(int argc, char *argv[])
{
	n = 9;
	allvec = (2 << n) - 1;
	for (int i = 0; i < n; i++)
	{
		row[i] = allvec;
		col[i] = allvec;
		for (int j = 0; j < n; j++)
		{
			sq[i][j] = 0;
			allowed[i][j] = allvec;
		}
	}
	
	iset(1,1,1);
	iset(2,3,1);
	iset(4,3,4);
	iset(4,5,1);
	iset(4,8,5);
	iset(6,4,2);
	iset(6,7,6);
	iset(7,6,2);
	iset(8,3,3);
	solve(9);
			
	return 0;
}