3099573_tle.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int m[108], bc[512], mp[81][3];
char r[81], *init;

void recur()
{
	int i, t, v;
	int bv = 99, bvv = -1, bi = -1;

	for(i = 0; i < 81; i++)
	{
		if(r[i]==0)
		{
			v = 511 - (m[i] | m[mp[i][0]] | m[mp[i][1]] | m[mp[i][2]]);
			t = bc[v];
			if(t < bv)
			{
				if(t == 0)
				{
					return ;
				}
				bv  = t;
				bi = i;
				bvv = v;
				if(t==1)
				{
					break;
				}
			}
		}
	}
	if(bv==99)
	{
		puts(r);
		return ;
	}
	for(i = 0; i < 9; i++)
	{
		if(0 != (bvv & (1<<i)))
		{
			r[bi] = '1'+i;
			m[mp[bi][0]] |= 1 << i;
			m[mp[bi][1]] |= 1 << i;
			m[mp[bi][2]] |= 1 << i;
			recur();
			m[mp[bi][0]] &= ~(1 << i);
			m[mp[bi][1]] &= ~(1 << i);
			m[mp[bi][2]] &= ~(1 << i);
			r[bi] = '\0';
		}
	}
}

void solve(char initv[])
{
	int i;

	init = initv;
	for(i = 0; i < 81; i++)
	{
		if(init[i] > '0')
		{
			m[i] = 511 - (1<<(init[i] - '1'));
		}
		else
		{
			m[i] = 0;
		}
	}
	memset(r,'\0',sizeof(r));
	recur();
}

int main()
{
	int i;
	char sudoku[82];

	memset(bc,0,sizeof(bc));
	for(i = 1; i < 512; i++)
	{
		bc[i] = 1 + bc[i & (1-i)];
	}
	for(i = 0; i < 81; i++)
	{
		mp[i][0] = 81+i%9;
		mp[i][1] = 90+i/9;
		mp[i][2] = 99+i/3%3*3+i/27;
	}
	while(scanf("%s",sudoku)==1)
	{
		if(sudoku[0]=='e')
		{
			break;
		}
		solve(sudoku);
	}
	return 0;
}