[C언어] Sudoku Validator (부루트포스 탐색 알고리즘)

문제

Sudoku Validator

사용자로부터 9x9 크기의 스도쿠 판을 입력받아 아래의 규칙에 어긋난 부분이 없는지 확인하여 올바르게 채워진 경우 true, 규칙에 어긋난 부분이 있는 경우 false를 출력하세요.

• 각 행은 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 각 열에도 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 3x3의 크기로 나누어진 9개의 내부 구획 내에서도 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 각 숫자는 쉼표(,)로 구분합니다.
• 비어있는 칸은 마침표(.)로 나타냅니다.

입력으로 주어지는 스도쿠 판은 일부만 채워져 있을 수 있습니다. (비어있는 칸을 추론하여 채우기 위한 충분한 숫자가 채워져 있지 않을 수 있습니다.) 

입출력 예시

(입력 #1)

5,3,.,.,7,.,.,.,.
6,.,.,1,9,5,.,.,.
.,9,8,.,.,.,.,6,.
8,.,.,.,6,.,.,.,3
4,.,.,8,.,3,.,.,1
7,.,.,.,2,.,.,.,6
.,6,.,.,.,.,2,8,.
.,.,.,4,1,9,.,.,5
.,.,.,.,8,.,.,7,9

(출력 #1)

true

 

(입력 #2)

5,3,.,.,7,.,.,.,.
6,.,.,1,9,5,.,.,.
.,9,8,.,.,.,.,6,.
8,.,.,.,6,.,.,.,3
4,.,.,8,.,3,.,.,1
7,.,.,.,2,.,.,.,6
.,6,.,.,.,.,2,8,.
.,.,.,4,1,9,.,.,5
.,.,.,.,8,.,.,7,3

(출력 #2)

false

 

어떻게 해결해야 할까?

스도쿠의 규칙에 따라 가로로 9개, 세로로 9개의 요소를 전부 확인하면서 중복이 있는지 확인하고

9칸씩 확인하고 그 안에 중복이 있는지 확인하면 될 것이다.

만약 중복이 생긴다면 즉시 함수를 종료시키는 방법을 사용하자.

 

코드를 살펴보자

전체 코드는 아래와 같다.

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

int check(int stx,int sty,char ssudocu[][9])
{
	int check[10]={0,0,0,0,0,0,0,0,0,0};
	for(int i=stx; i<stx+3; i++){
		for(int j=sty; j<sty+3; j++)
		{
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')])
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}
	return 1;
}
int main(int argc, char *argv[]) {
	char ssudocu[9][9];
	for(int i=0; i<9; i++) // 스도쿠 입력 sssss
		for(int j=0; j<9; j++)
		{
			scanf("%c",&ssudocu[i][j]);
			getchar();
		}
	//////////////////////////////////////
	for(int i=0; i<9; i++)
	{
		int check[10]={0,0,0,0,0,0,0,0,0,0};
		for(int j=0; j<9; j++)
		{	
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')]==1)
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}
	///////////////////////////////////////////////////////
	for(int j=0; j<9; j++)
	{
		int check[10]={0,0,0,0,0,0,0,0,0,0};
		for(int i=0; i<9; i++)
		{
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')]==1)
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}
	////////////////////////////////////////////////////////
	for(int i=0; i<9; i+=3)
	{
		for(int j=0; j<9; j+=3)
		{
			if(check(i,j,ssudocu))
				continue;
			else
			{
				return 0;
			}
		}
	}
	printf("true\n");
	return 0;
}

일단 먼저 9칸(3X3)씩 확인하는 함수를 선언해주자.

int check(int stx,int sty,char ssudocu[][9])
{
	int check[10]={0,0,0,0,0,0,0,0,0,0};
	for(int i=stx; i<stx+3; i++){
		for(int j=sty; j<sty+3; j++)
		{
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')])
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}
	return 1;
}

check를 10칸으로 설정한 이유는 index를 계속 -1해주지 않기 위해서이다.

그리고 .을 봤을 때는 그냥 넘어가주었다.

그리고 check를 이미 방문하였다면 false를 출력하고 종료한다.

 

int main(int argc, char *argv[]) {
	char ssudocu[9][9];
	for(int i=0; i<9; i++) // 스도쿠 입력 sssss
		for(int j=0; j<9; j++)
		{
			scanf("%c",&ssudocu[i][j]);
			getchar();
		}
	//////////////////////////////////////

이 부분은 스도쿠 (9X9)만큼의 구간의 값을 받는 부분이고 ','와 개행을 무시하기 위해 getchar로 버퍼를 비워주었다.

 

	for(int i=0; i<9; i++)
	{
		int check[10]={0,0,0,0,0,0,0,0,0,0};
		for(int j=0; j<9; j++)
		{	
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')]==1)
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}
	///////////////////////////////////////////////////////
	for(int j=0; j<9; j++)
	{
		int check[10]={0,0,0,0,0,0,0,0,0,0};
		for(int i=0; i<9; i++)
		{
			if(ssudocu[i][j] == '.')
				continue;
			else
			{
				if(check[(int)(ssudocu[i][j]-'0')]==1)
				{
					printf("false\n");
					return 0;
				}
				else
					check[(int)(ssudocu[i][j]-'0')] = 1;
			}
		}
	}

여긴 그냥 코드를 보면 알 수 있듯, 세로 방향 가로 방향으로 탐색하고 중복이 있다면 false를 출력하고 종료하는 코드이다.

 

	////////////////////////////////////////////////////////
	for(int i=0; i<9; i+=3)
	{
		for(int j=0; j<9; j+=3)
		{
			if(check(i,j,ssudocu))
				continue;
			else
			{
				return 0;
			}
		}
	}
	printf("true\n");
	return 0;
}

여긴 위에 선언해준 함수를 사용해서 (3X3)부분을 탐색하는 부분이다. 만약 0이 return되었다면 즉시 코드를 종료한다.

만약 이 모든 검사를 통과했다면 true를 출력하고 코드를 종료한다.

 

이 코드는 효율적이지는 않지만 모든 경우를 확실하게 확인할 수 있고 구현이 쉽다.

 

좀 더 효율적으로 하려면 비트마스킹을 이용해서 행, 열, 3x3배열을 한번에 확인하는 방법이 있다.

for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        if (ssudocu[i][j] == '.') continue;

        int num = ssudocu[i][j] - '0';
        int mask = 1 << num;

        if (row[i] & mask || col[j] & mask || block[(i / 3) * 3 + (j / 3)] & mask) {
            printf("false\n");
            return 0;
        }

        row[i] |= mask;
        col[j] |= mask;
        block[(i / 3) * 3 + (j / 3)] |= mask;
    }
}

대충 이런식으로 하면 된다.

 

• row[i], col[j], block[(i / 3) * 3 + (j / 3)]는 각각 현재 위치의 행, 열, 블록에서 숫자를 체크하는 배열이다.
• 숫자가 나타나면 비트 마스크를 사용해 row[i], col[j], block에 기록하고, 같은 숫자가 있으면 중복이므로 false를 출력하고 종료한다.