c언어 2239번 스도쿠 (백준)

#include <stdio.h>
#include <stdlib.h>

int a[82] = {0, };


void find(int x)
{
    if(x==81) {
        for(int i = 0; i<81; i++) {
        printf("%d ", a[i]);
        if((i+1) % 9 == 0) printf("\n");
    }
    exit(0);
    
    }
    
    
    if(a[x] == 0) {
        for(int i = 1; i<=9; i++)
        {
            int count = 0;
            a[x] = i;
            for(int j = (x/9)*9; j<(x/9)*9+9; j++) //가로
            {
                if(x != j && a[j] == a[x]) break;
                count++;
            }
            for(int j = x%9; j<81 && count>=9; j=j+9) //세로
            {
                if(x != j && a[j] == a[x]) break;
                count++;
            }
            
            
            int tmp = x/27; //가로 압축 
            int tmp_1 = (x%9)/3; //세로 압축 
            //9개의 3*3 영역이 만들어짐
            //각 영역의 시작점 0, 3, 6...
            int start = 0;
            start = (tmp_1 * 3) + (tmp * 27);
            int t = 1;
            while(t<=9 && count>=18)
            {
                    if(x != start) {
                        if(a[start] == a[x]) break;
                    }
                    count++;
                    start++;
                    if(t%3==0) start = (start-3)+9;
                    t++;
                    
            }
            
            if(count == 27) find(x+1);
            
            a[x] = 0;
            count = 0;
            start = 0;
            t = 1;
        } 
        
    } else if(a[x] != 0) find(x+1);
}

int main(void)
{
	char s[10] = {};
	int k = 0;
	
    for(int i = 0; i<9; i++) {
    	scanf("%s", s); //문자열로 입력을 받은 다음 
    	for(int j=0; j<9; j++) {
    		a[k++] =  s[j]-48; //정수로 바꾼뒤, int형 배열에 집어넣음 
		}
	}
   
    find(0); //백트래킹 
    
    return 0;
}

 

풀이 : 백트래킹

1. 문자열로 입력을 받은 것을 따로 만들어둔 int형 배열에 정수로 바꾼다음 집어 넣습니다.

1-1) int 형 배열은 저는 1차원배열로 만들었습니다.

 

2. 백트래킹

2-1)  81개이므로 int형배열의 모든 요소, 즉 0번 부터 80번까지 확인을 한 다음 81번째 함수가 호출 되면, 완성된 스토쿠를 출력합니다.

2-2) 모든 요소를 검사할 때, 0이 아닌 것은 다음 함수를 호출하면 됩니다.

2-3) 0일 경우 사전순이이게 1~9까지 대입을 해보면서, 가로로 비교, 세로로비교, 3*3 정사각형 내에서의 비교를 거친 후

모두다 만족하는 1~9 중에서의 숫자를 찾으면, 다음 함수를 호출합니다.

2-4) 스도쿠를 만드는 과정에서 뒤로 돌아올 수 있는 상황이 있기에, 이를 대비하여 함수호출을 하는 코드 다음에는 넣은 값을 0으로 다시 초기화 해주어야 합니다. 그렇지 않으면, 이전과정으로 돌아가더라도, 원래는 0이었던 곳이 9로 바뀌어 있게 됩니다.

2-5) 물론 2-4)의 문제는, 단지 count, start, t 처럼 for문을 돌릴 때마다 같이 0으로 초기화 해주고 새로운 숫자를 넣는 형식으로 구현하면 걱정할 필요가 없습니다.

 

https://h202.tistory.com/29

c언어 2580번 스토쿠 (백준)

이 문제는 위 문제와 같다고 볼 수 있습니다. 더욱 자세한 설명이 있습니다.

 

https://www.acmicpc.net/problem/2239

2239번: 스도쿠