soduke.cpp

采用搜索策略求解数独问题

#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define SUB( r, c ) (r/3*3+c/3)

short g[9][9], row[9], col[9], sub[9];
bool  ok;

int cnt_one( int n )
{
	int cnt;
	for( cnt=0; n; n&=(n-1), cnt++ );
	
	return cnt;
}

void Solve( short fixed )
{
	short i, j, r, c, avail, min=9;
	short t, cnt;

	if( fixed==81 )
	{
		ok = 1;
		return;
	}

	for( i=0; i<9; i++ ) // Select Optimal
	{
		for( j=0; j<9; j++ )
		{
			if( g[i][j]==0 )
			{
				t = row[i]&col[j]&sub[SUB(i,j)];
				if( t==0 ) return;
				cnt = cnt_one( t );
				if( cnt<min )
				{
					min = cnt;
					r = i;
					c = j;
					avail = t;					
				}
			}
		}
	}

	for( i=1; i<=9; i++ )
	{
		if( avail&(1<<i) )
		{
			t = 1<<i;

			g[r][c] = i;		
			row[r]&=~t, col[c]&=~t, sub[SUB(r,c)]&=~t;
			Solve( fixed+1 );
			if( ok ) return;
			row[r]|=t, col[c]|=t, sub[SUB(r,c)]|=t;
			g[r][c] = 0;
		}
	}
}

int main()
{
	short fixed, i, r, c, t;
	char  str[82] = ".2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.";
	clock_t st,ed;

	while( scanf("%s", str)&&str[0]!='e' )
	{
		st = clock();
		ok =0, fixed = 0;

		for( i=0; i<9; i++ )
			row[i] = col[i] = sub[i] = 0x3fe;
		
		for( i=0; i<81; i++ )
		{
			r = i/9, c = i%9;
			if( str[i] == '.' )
				g[r][c] = 0;
			else
			{
				fixed++;
				g[r][c] = str[i]-'0';
				t = 1<<g[r][c];
				row[r]&=~t, col[c]&=~t, sub[SUB(r,c)]&=~t;
			}			
		}

		Solve( fixed );
		for( r=0; r<9; r++ )
	/*	{*/
			for( c=0; c<9; c++ )
				printf("%d", g[r][c]);
			printf("\n");
	/*	}*/
		ed = clock();
	/*	printf("%d\n", (int)(ed-st));*/
		
	}

	return 0;
}