(2580) 스도쿠

https://www.acmicpc.net/problem/2580

단계별로 풀어보기

20단계(백트래킹) 6번째

 

 

 

백트래킹 연습용으로 만들어진 문제라 별다른 최적화 없이 기본에 충실하게 첫 칸부터 탐색하며 빈칸에 1부터 9까지 집어넣는 코드를 짜면 된다.

중간에 가지치기를 잘못해서 두 번 틀렸다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int cnt= 0;
  vector v(9, vector<short> (9));
  
  for(int i=0;i<9;i++){
    for(int j=0;j<9;j++){
      cin >> v[i][j];
      cnt+= (!v[i][j]);
    }
  }
  
  auto check= [&](int r, int c, int n){
    for(int i=0;i<9;i++){
      if(v[r][i]==n || v[i][c]==n)  return false;
    }
    for(int x=r/3*3,i=x;i<x+3;i++){
      for(int y=c/3*3,j=y;j<y+3;j++){
        if(v[i][j]==n)  return false;
      }
    }
    
    return true;
  };
  
  auto func= [&](auto self, int depth, int idx) -> void {
    if(depth==cnt){
      for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
          cout << v[i][j] << " ";
        }
        cout << "\n";
      }
      
      exit(0);
    }
    
    for(int i=idx;i<81;i++){
      if(v[i/9][i%9])  continue;
      
      for(int k=1;k<=9;k++){
        if(!check(i/9, i%9, k))  continue;
        
        v[i/9][i%9]= k;
        self(self, depth+1, i+1);
        v[i/9][i%9]= 0;
      }
      
      return;
    }
  };
  
  func(func, 0, 0);
  
  return 0;
}