태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Notice

2011.08.12 13:54 Solutions/Mr.K's Solution
ㅋㅋㅋ

너무 정석대로 풀었나
뭔가 빨리 돌리는 방법이 있을텐뎈ㅋ


#include 
using namespace std;

void zeroset( int ary[][9] );
int numfind( int ary[][9], int bry[][9], int wtf );

int find[10]; // 숫자 k(k번째 원소)를 몇개나 찾았는가에 해당하는 배열

int main()
{
	char str[90];
	int a[9][9]; // 풀어야되는 스도쿠
	int b[9][9]; // 메모지
	int i, j;
	int temp;

	while(1)
	{
		gets(str);

		if( strcmp( str, "end" ) == 0 )
		{
			break;
		}

		for( i = 0; i <= 9; i++ )
		{
			find[i] = 0;
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				if( str[i*9+j] == '.' )
				{
					a[i][j] = 0;
				}
				else
				{
					a[i][j] = str[i*9+j] - '0';
					find[a[i][j]]++;
					find[0]++;
				}
			}
		}

		while( find[0] < 81 )
		{
			// 스도쿠 연산
			for( i = 1; i <= 9; i++ )
			{
				zeroset( b );
				for( j = 0; j < 2; j++ )
				{
					if( find[i] < 9 )
					{
						temp = numfind( a, b, i );
					}
					if( temp == 0 )
					{
						// 찾는 숫자가 없거나 숫자 대입을 하지 않았으면 함수를 2번 돌릴 필요가 없음
						j++;
					}
				}
			}
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				printf( "%d", a[i][j] );
			}
		}
		printf("\n");
	}

	return 0;
}

void zeroset( int ary[][9] )
{
	int i, j;

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			ary[i][j] = 0;
		}
	}
}

int numfind( int ary[][9], int bry[][9], int wtf ) // wtf : isn't what the fu*k, want to find
{
	int i, j, k, m;
	int esc = 1;
	int count;
	int tempr, tempc;

	// wtf 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] == wtf )
			{
				bry[i][j] = 2;
				esc = 0;
			}
		}
	}

	// wtf가 현재 스도쿠에 없음
	if( esc == 1 )
	{
		return 0;
	}

	// wtf가 위치할 수 없는 범위 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( bry[i][j] == 2 )
			{
				for( k = 0; k < 9; k++ )
				{
					bry[i][k] = 1;
					bry[k][j] = 1;
				}
				for( k = (i/3)*3; k < (i/3)*3+3; k++ )
				{
					for( m = (j/3)*3; m < (j/3)*3+3; m++ )
					{
						bry[k][m] = 1;
					}
				}

				bry[i][j] = 2;
			}
		}
	}

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] != 0 && bry[i][j] == 0 )
			{
				bry[i][j] = 1;
			}
		}
	}

	// wtf가 유일하게 들어갈 수 있으면 대입
	for( i = 0; i < 3; i++ )
	{
		for( j = 0; j < 3; j++ )
		{
			count = 0;
			for( k = i*3; k < (i+1)*3; k++ )
			{
				for( m = j*3; m < (j+1)*3; m++ )
				{
					if( bry[k][m] == 0 )
					{
						tempr = k;
						tempc = m;
						count++;
					}
				}
			}

			if( count == 1 )
			{
				ary[tempr][tempc] = wtf;
				find[wtf]++;
				find[0]++;
				esc = 1;
			}
		}
	}

	return esc;
}
 
posted by Milkskin