어떤 문제인가?

$9\times 9$ 스도쿠 푸는 프로그램을 만드는 문제.

적용 가능한 최적화

1. 빈 칸 기록
   보드만 가지고 빈 칸을 찾으려고 들면, $O(N)$이라 추가적인 시간이 더 걸린다.

2. 조건에 맞지 않으면 즉시 손절
   처음에 사용 가능한 숫자를 걸러낸 다음, 그 숫자들에 포함되어있는지 그 여부를 봤는데, 어차피 참•거짓 여부만 가를 것이라면 그럴 필요도 없었다. 조건에 맞지 않으면 즉시 손절해 조금의 시간이라도 아끼자.

내 풀이

#include <stdio.h>

int B[10][10]={{0}},X[82]={0},Y[82]={0},k=0;
char e=0;

int c(int x, int y, int n) {
    int i=0,j=0;
    for(;i<9;i++)
        if(B[i][y]==n) return 1;
    for(;j<9;j++)
        if(B[x][j]==n) return 1;
    for(i=x/3*3;i<x/3*3+3;i++) {
        for(j=y/3*3;j<y/3*3+3;j++)
            if(B[i][j]==n) return 1;
    }
    return 0;
}

void d(int l) {
    int i;
    if(l==k || e) {
        e=1;
        return;
    }
    
    for(i=1;i<=9;i++) {
        if(!c(X[l],Y[l],i)) {
            B[X[l]][Y[l]]=i;
            d(l+1);
            if(!e) B[X[l]][Y[l]]=0;
        }
    }
}

int main() {
    int i,j;
    for(i=0;i<9;i++) {
        for(j=0;j<9;j++) {
            scanf("%d",&B[i][j]);
            if(!B[i][j]) {
                X[k]=i;
                Y[k++]=j;
            }
        }
    }
    d(0);
    for(i=0;i<9;i++) {
        for(j=0;j<9;j++)
            printf("%d ",B[i][j]);
        printf("\n");
    }
}

다른 분들의 풀이

#include <stdio.h>
int row[9][10], col[9][10], box[9][10], a[9][9], chk;
int dfs(int now){
  if (now==81){
    for (int i=0; i<9; i++){
      for (int j=0; j<9; j++){
        printf("%d ", a[i][j]);
      }
      printf("\n");
    }
    return 1;
  }
  int x=now/9, y=now%9;
  if (a[x][y]==0){
    for (int i=1; i<10; i++){
      if (!row[x][i] && !col[y][i] && !box[(x/3)*3+y/3][i]){
        row[x][i]=col[y][i]=box[(x/3)*3+y/3][i]=1;
        a[x][y]=i;
        if (dfs(now+1)) return 1;
        row[x][i]=col[y][i]=box[(x/3)*3+y/3][i]=0;
        a[x][y]=0;
      }
    }
  }
  else return dfs(now+1);
  return 0;
}
int main(){
  for (int i=0; i<9; i++){
    for (int j=0; j<9; j++){
      scanf("%d", &a[i][j]);
      row[i][a[i][j]]=col[j][a[i][j]]=box[(i/3)*3+j/3][a[i][j]]=1;
    }
  }
  dfs(0);
}

gaelim님 소스
-> https://www.acmicpc.net/source/7157063

2-1. 배열에 다 담아놓고 필요한 때 쓰자.
공간을 많이 잡아먹겠지만 열, 행 그리고 특정 $3\times 3$칸 안에 있는 숫자들을 전부 집어넣은 후 비교 시 $O(1)$의 실행시간을 보장한다.

쓰다보니 내 실행시간이 좀 긴 편에 속했다. 200ms인데 다른 분들의 실행시간은 40ms까지 짧았던 분들도 있었다. 어디에서 차이가 난 걸까? 시간이 날 때 천천히 생각해봐야겠다.

※ 구글링해서 이 문제 풀이들을 일부 봤는데, exit(0)을 쓰는 경우가 많았다. 나 같은 경우에는 그 함수가 좀 뜬금없이 자리 잡고 들어오는 느낌이 들어 변수 e로 대체했다.