[BOJ/백준][Gold4] 2239 : 스도쿠 (C++)

www.acmicpc.net/problem/2239

2239번: 스도쿠

 

 

[난이도] Gold4

[유형] 백트래킹

 

[풀이]

81개중 빈칸에 대해 1~9의 숫자를 넣어보면서 조건에 맞는지 체크해간다.

#include <cstdio>
using namespace std;
int map[9][9],ok;
bool check(int y,int x,int k){
    for(int i=0;i<9;i++) {
        if(map[y][i]==k || map[i][x]==k) return 0;
    }
    int yy = (y/3)*3, xx=(x/3)*3;
    for(int i=yy;i<yy+3;i++)
        for(int j=xx;j<xx+3;j++) if(map[i][j]==k) return 0;
    
    return 1;
}
void sol(int y,int x){
    if(ok) return;
    if(y==9) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) printf("%d",map[i][j]);
            puts("");
        }
        ok = 1;
        return;
    }
    if(map[y][x]){
        if(x==8) sol(y+1,0);
        else sol(y,x+1);
    }else{
        for(int i=1;i<10;i++){
            if(check(y,x,i)){
                map[y][x] = i;
                if(x==8) sol(y+1,0);
                else sol(y,x+1);
                map[y][x] = 0;
            }
        }
    }
}
int main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++) scanf("%1d",&map[i][j]);
    sol(0,0);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2239.cpp