백준 2239 스도쿠

예전에 텀프로젝트로 풀었던 문제,, 이제 보니까 금세 풀 수 있었다.

스도쿠 문제는 대표적인 백트래킹 문제이다.

스도쿠의 핵심은 한 row에, 한 col에, 한 square(box)에서 그 숫자를 넣어도 괜찮은가에 대해서 체크해야 한다는 점이다.

따라서, boolean 함수 3가지, rowCheck, colCheck, boxCheck를 이용해준다.

이 때 중요한 점은 백트래킹 시, 만족하지 않을 경우, 다시 0으로 채워줘야 한다는 점이다.

원래는 모든 칸, n = 81이 되면 마치도록 했었는다. 그런데, 굳이 그렇게 모든 칸을 보기보다, 입력 시 0인 칸들의 좌표를 저장해두고, 그 좌표만 확인하는 방식으로 변경하였다.

사실 스도쿠 문제를 해결하는 것보다 골치 아팠던 점은, 출력 초과가 계속 떴다는 점이다.

그 이유를 살펴보니,

입력이 다음과 같은 경우,

000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000

여러 가지 출력이 나올 수 있는데, 그 출력이 하나에 그치지 않았다는 점이다.
그래서, exit(0);으로 강제종료를 시켜주어야만 한다.

#include <iostream>
#include <vector>
using namespace std;

struct coor{
  int x;
  int y;
};

vector<coor> emptyCoor;
int arr[10][10];
int flag[9][9];
void input(){
  for(int i = 0; i < 9; i++){
    for(int j = 0; j < 9; j++){
      char c;
      cin >> c;
      c = c - 48;
      arr[i][j] = int(c);
      if(arr[i][j] == 0) emptyCoor.push_back({i, j});
    }
  }
}

bool rowCheck(int row, int num){
  for(int i = 0; i < 9; i++){
    if(arr[row][i] == num) return false;
  }
  return true;
}

bool colCheck(int col, int num){
  for(int i = 0; i < 9; i++){
    if(arr[i][col] == num) return false;
  }
  return true;
}

bool boxCheck(int row, int col, int num){
  int x = row / 3 * 3;
  int y = col / 3 * 3;
  for(int i = x; i < x + 3; i++){
    for(int j = y; j < y + 3; j++){
      if(arr[i][j] == num) return false;
    }
  }
  return true;
}

void print_(){
  for(int i = 0; i < 9; i++){
    for(int j = 0; j < 9; j++){
      cout << arr[i][j];
    }
    cout << "\n";
  }
  return;
}

void sudoku(int n){
  if(n==emptyCoor.size()) {
    print_();
    exit(0);
  }
  int x = emptyCoor[n].x;
  int y = emptyCoor[n].y;
  
  for(int num = 1; num <= 9; num++){
    if(rowCheck(x, num) && colCheck(y, num) && boxCheck(x, y, num)){
      arr[x][y] = num;
      sudoku(n+1);
      arr[x][y] = 0;
    }
  }
}

int main(void){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  input();
  sudoku(0);
  return 0;
}