BOJ 2580 스도쿠

이 문제는 유명한 퍼즐인 스도쿠를 구현하면 된다.

스도쿠가 풀리는 입력만 주어지기 때문에 퍼즐을 완성하는 알고리즘만 잘 구현한다면 꽤 쉽게 풀 수 있다.

 

실제 스도쿠 퍼즐을 사람이 풀기 위해선 다양한 전략, 기법이 필요하지만 컴퓨터가 풀기 위해선 가능한 숫자들을 다 try & error 하는 식으로 해도 빠르게 풀 수 있기 때문에, 백트래킹 + 주먹구구식 대입으로 구현하면 될 것 같다.

 

문제는 효율적인 백트랙킹을 위해 데이터를 어떤식으로 저장해야 하는가이다.

 

각 빈칸에 1~9 의 숫자가 들어갈 수 있는지 확인을 위해, row(열), col(행), box(정사각형) bool 타입 배열에 이미 들어간 숫자를 저장하였고, 각 빈칸에 들어갈 수 있는 모든 숫자 후보들을 다 저장하기 위해 2차원 벡터를 이용하였다.

vector< vector< pair< pair<int,int> ,int> > > v;

안쪽 pair<int,int>      : y,x 좌표

바깥쪽 pair의 second : 가능한 숫자 후보

 

이렇게하면 안쪽 벡터는 같은 빈 칸의 가능한 모든 숫자 후보를 모두  저장할 수 있다.

데이터만 잘 저장해놓으면 재귀함수를 이용해 쉽게 백트래킹을 구현하여 풀 수 있다.

 

 

 

소스코드

#include<stdio.h>
#include<vector>
using namespace std;

int board[10][10];
bool cols[10][10], rows[10][10], box[10][10];
vector< vector< pair< pair<int,int> ,int> > > v;

bool chk(int y,int x, int num){
    if(rows[y][num] || cols[x][num] || box[3*(y/3) + (x/3)][num]){
        return false;
    }
    return true;
}

bool solve(int p){
    if(p == v.size()){
        return true;
    }

    for(int i=0; i<v[p].size(); i++){
        int y = v[p][i].first.first, x = v[p][i].first.second, num = v[p][i].second;
        if(chk(y,x,num)){
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = true;
            board[y][x] = num;
            
            if(solve(p+1)){
                return true;
            }
            
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = false;
            board[y][x] = 0;
        }
    }
    return false;
}
int main(){
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            scanf("%d", &board[i][j]);
            if(board[i][j] != 0){
                rows[i][board[i][j]] = cols[j][board[i][j]] = box[3*(i/3) + (j/3)][board[i][j]] = true;
            }
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            if(board[i][j] == 0){
                vector< pair< pair<int,int>, int> > tmp;
                for(int num=1; num<=9; num++){
                    if(chk(i,j, num)){
                        tmp.push_back(make_pair( make_pair(i,j), num));
                    }
                }
                v.push_back(tmp);
            }
        }
    }

    solve(0);

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

    return 0;
}