[BOJ-2580]스도쿠

모든 경우의 수를 확인하기위해 백트래킹을 하는 문제이다. 

옳은 경우를 확인하면서 DFS 를 하면서 옳지 않은 경우를 걸러내면 된다.

스도쿠에서 옳은 수를 넣는 조건은

행에 모두 1,2,....,8,9

열에 모두 1,2,....,8,9

9x9 안에 3x3 이 9개 있으면 그 내부에 있는 수 또한 1,2...,8,9 가 존재해야한다. 

#include<cstdio>
#define MAX 10
 
int map[MAX][MAX] = {0,};
int ROW[MAX] = {0,};
int COL[MAX] = {0,};
int SIDE[MAX] = {0,};
bool res = false;
 
void printBoard(){
    for(int i = 1 ; i < MAX ; i++){
        for(int j = 1 ; j < MAX ; j++){
            printf("%d", map[i][j]);
            if(j != 9) printf(" ");
        }
        if(i<9) printf("\n");
    }
}
void boolInit(){
    for(int i = 1 ; i < MAX ; i++){
        ROW[i] = COL[i] = SIDE[i] = 0;
    }
}
 
bool sideCondition(int r, int c){
    int idx = 0;
    for(int i = 3*((r-1)/3)+1 ; i < 3*((r-1)/3+1)+1 ; i++){
        for(int j = 3*((c-1)/3)+1 ; j < 3*((c-1)/3+1)+1 ; j++){
            SIDE[map[i][j]] += map[i][j];
            if(SIDE[map[i][j]] > map[i][j])    return false;
        }
    }
    return true;
}
bool rowCondition(int r, int c){
    for(int i = 1 ; i < MAX ; i++){
        ROW[map[r][i]] += map[r][i];
        if(ROW[map[r][i]] > map[r][i]) return false;
    }
    
    return true;
}
bool columnCondition(int r, int c){
    for(int i = 1 ; i < MAX ; i++){
        COL[map[i][c]] += map[i][c];
        if(COL[map[i][c]] > map[i][c]) return false;
    
    }
    return true;
}
bool board(int r, int c){
    boolInit();
    if(!rowCondition(r,c))    return false;
    if(!columnCondition(r,c))return false;
    if(!sideCondition(r,c))    return false;
    return true;
}
 
void back(int row, int col, int n){
    if(n==81 || res){
        res = true;
        return ;
    }
    for( int value = 1 ; value < MAX ; value++){
        if(map[row][col] == 0){
            map[row][col] = value;
            if(board(row,col)){ 
                if(col<9) back(row,col+1,n+1);
                else if(col==9) back(row+1,1,n+1);
                if(!res) map[row][col] = 0;    
            }else{ 
                map[row][col] = 0;
            }                
        }else{
            if(col<9) back(row,col+1,n+1);
            else if(col==9) back(row+1,1,n+1);
            return ;
        }
        if(res) return ;
    }
}
 
 
int main(){
    for(int i = 1 ; i < MAX ; i++)
        for(int j = 1 ; j < MAX ; j++) scanf("%d",&map[i][j]);        
    
    back(1,1,0);
    printBoard();
    return 0;
}
 

#include<cstdio>
#include<vector>
int imap[10][10];
int row[10];
int col[10];
int sid[10];
void print_map() {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            printf("%d ", imap[r][c]);
        }
        puts("");
    }
}
// false ; 값이 옳지않음.
// true ; 값이 옳음.
bool row_condition(int r) {
    for (int c = 0; c < 10; c++) row[c] = 0;
    for (int c = 0; c < 10; c++) {
        row[imap[r][c]]++;
        if (row[imap[r][c]] > 1 && imap[r][c] != 0) return false;
    }
    return true;
}
bool col_condition(int c) {
    for (int r = 0; r < 10; r++) col[r] = 0;
    for (int r = 0; r < 10; r++) {
        col[imap[r][c]]++;
        if (col[imap[r][c]] > 1 && imap[r][c] != 0) return false;
    }
    return true;
}
bool sid_condition(int r, int c) {
    int row = r / 3;
    int col = c / 3;
    for (int i = 0; i < 10; i++) sid[i] = 0;
    for (int r = 3 * row; r < 3 * (row + 1); r++) {
        for (int c = 3 * col; c < 3 * (col + 1); c++) {
            sid[imap[r][c]]++;
            if (sid[imap[r][c]] > 1 && imap[r][c] != 0) return false;
        }
    }
    return true;
}
bool tot_condition(int r, int c) {
    if (!row_condition(r)) return false;
    if (!col_condition(c)) return false;
    if (!sid_condition(r, c)) return false;
    return true;
}
bool finish = false;
void dfs(int r, int c) {
    if (r == 9) {
        finish = true;
        return;
    }
    
    if (!finish) {
        for (int v = 1; v < 10; v++) {
            if (imap[r][c] == 0) {
                imap[r][c] = v;
                if (tot_condition(r, c)) {
                    if (c + 1 == 9) dfs(r + 1, 0);
                    else dfs(r, c + 1);
                }
                if(!finish)    imap[r][c] = 0;    
            }
            else {
                if (c + 1 == 9) dfs(r + 1, 0);
                else dfs(r, c + 1);
                break;
            }
 
        }
    }
}
 
int main() {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) scanf("%d", &imap[r][c]);
    dfs(0, 0);
    print_map();
    return 0;
}