[C/C++][백트래킹] 백준 2239번: 스도쿠

문제: https://www.acmicpc.net/problem/2239

스도쿠를 푸는 알고리즘을 작성하는 문제이다.

주어진 조건은

1. 여러개의 답이 있으면 그 중 사전식으로 앞서는 것을 출력한다.

1. 풀리지 않는 스도쿠는 없다. ( 문제에 예외가 작성되지 않았으므로 )

스도쿠 빈칸을 채우기 위해서는 스도쿠 규칙을 따라야 하는데

1. 가로줄에 같은 숫자가 있으면 안된다.

1. 세로줄에 같은 숫자가 있으면 안된다.

1. 같은 섹션에 같은 숫자가 있으면 안된다.

3번 규칙이 구현하기 살짝 어려웠는데 정수 나눗셈으로 소숫점 아랫부분을 버리면서 해결했다.

bool isAvailable(int x, int y, int k){
  for(int i=0;i<9;i++){
    if(puzzle[x][i] == k) return false;
    if(puzzle[i][y] == k) return false;
  }
  for(int i=x/3*3; i<x/3*3+3; i++){
    for(int j=y/3*3; j<y/3*3+3; j++){
      if(puzzle[i][j] == k) return false;
    }
  }
  return true;
}

이후 백트래킹으로 다음 빈칸을 찾아 나가면 되는데 dfs에서 목표에 도달했는지 검증할 때 return을 사용하면 안된다.

return을 하게되면 그 시점의 dfs재귀 호출 스택만 빠져나오기 때문에 dfs호출이 끝나고 빈칸을 다시 열어두는 기능을 수행해버린다. 따라서 exit(0)으로 재귀호출을 끊어야한다.

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

int puzzle[9][9];
vector<pair<int, int>> space;

bool isAvailable(int x, int y, int k){
  for(int i=0;i<9;i++){
    if(puzzle[x][i] == k) return false;
    if(puzzle[i][y] == k) return false;
  }
  for(int i=x/3*3; i<x/3*3+3; i++){
    for(int j=y/3*3; j<y/3*3+3; j++){
      if(puzzle[i][j] == k) return false;
    }
  }
  return true;
}

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

void dfs(int space_index){
  if (space_index == space.size()) {
    print_puzzle();
    exit(0);
  }
  //cout<<"----------------\n";
  //print_puzzle();
  int x = space[space_index].first;
  int y = space[space_index].second;
  for(int i=1;i<=9;i++){
    if(isAvailable(x, y, i)){
      puzzle[x][y] = i;
      dfs(space_index+1);
      puzzle[x][y] = 0;
    }
  }
}

int main(){
  cout.tie(NULL);
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  //
  for(int i=0;i<9;i++){
    string a;
    cin >> a;
    for(int j=0;j<9;j++){
      puzzle[i][j] = a[j] - '0';
      if(puzzle[i][j] == 0) space.push_back({i, j});
    }
  }
  dfs(0);
  print_puzzle();
}