[C++] 백준 4574번 스도미노쿠

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다.

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.
스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 주어진다. U는 도미노에 쓰여 있는 한 숫자이고, LU는 길이가 2인 문자열로 U의 위치를 나타낸다. V와 LV는 도미노에 쓰여 있는 다른 숫자를 나타낸다. 도미노의 위치는 문제에 나와있는 그림을 참고한다. 입력으로 주어지는 도미노의 각 숫자 위치는 항상 인접해 있다.

N개의 도미노의 정보가 주어진 다음 줄에는 채워져 있는 숫자의 위치가 1부터 9까지 차례대로 주어진다. 위치는 도미노의 위치를 나타낸 방법과 같은 방법으로 주어진다.

모든 도미노와 숫자가 겹치는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 퍼즐에 대해서, 스도쿠를 푼 결과를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

풀이

백준 스도쿠문제를 해결했다면 어렵지 않게 풀 수 있는 문제이다. 기존과 달라진 점이 한번에 1칸을 채우는 대신 2칸짜리 블록을 가로 또는 세로로 놓아야 한다는 것밖에 없다.
숫자 한개를 해당 위치에 놓을 수 있는지 열, 행, 3x3박스를 검사하는 함수를 만들어두고 3가지 경우를 모두 충족할때만 숫자를 놓을 수 있다. 우리는 2칸짜리 블럭을 놓아야하므로 가로, 세로로 놓을 수 있고 둘의 숫자 위치가 뒤바뀐 경우도 가능하다.
위에서부터 빈칸을 찾고 해당위치에 가능한 경우의 블록을 모두 놓는 함수를 재귀적으로 반복하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n;
int board[9][9];
int used[10][10];
bool fin = false;

bool checkRow(int r, int num){
  for (int i=0; i<9; i++){
    if (board[r][i] == num) 
      return false;
  }
  return true;
}

bool checkCol(int c, int num){
  for (int i=0; i<9; i++){
    if (board[i][c] == num) 
      return false;
  }
  return true;
}

bool checkBox(int r, int c, int num){
  int x = r/3*3;
  int y = c/3*3;
  for (int i=0; i<3; i++)
    for (int j=0; j<3; j++){
      if (board[x+i][y+j] == num) 
        return false;
    }
  return true;
}

bool check(int r, int c, int num){
  return checkBox(r,c,num) && checkCol(c,num) && checkRow(r,num);
}

void solve(){
  if (fin) return;

  int x=-1,y;
  for (int i=0; i<9; i++){
    for (int j=0; j<9; j++){
      if (!board[i][j]){
        x = i;
        y = j;
        break;
      }
      if (x != -1) break;
    }
    if (x != -1) break;
  }

  if (x == -1) {
    fin = true;
    for (int i=0; i<9; i++){
      for (int j=0; j<9; j++)
        cout << board[i][j];
      cout << endl;
    }
    return;
  }

  for (int i=1; i<=8; i++)
    for (int j=i+1; j<=9; j++){ 
      if (!used[i][j]){
        used[i][j] = 1;
        used[j][i] = 1;
        // 가로
        if (y+1 < 9 && !board[x][y+1]){
          if (check(x,y,i) && check(x,y+1,j)){
            board[x][y] = i;
            board[x][y+1] = j;
            solve();
            board[x][y] = 0;
            board[x][y+1] = 0;
          }
          if (check(x,y,j) && check(x,y+1,i)){
            board[x][y] = j;
            board[x][y+1] = i;
            solve();
            board[x][y] = 0;
            board[x][y+1] = 0;
          } 
        }
        // 세로
        if (x+1 < 9 && !board[x+1][y]){
          if (check(x,y,i) && check(x+1,y,j)){
            board[x][y] = i;
            board[x+1][y] = j;
            solve();
            board[x][y] = 0;
            board[x+1][y] = 0;
          }
          if (check(x,y,j) && check(x+1,y,i)){
            board[x][y] = j;
            board[x+1][y] = i;
            solve();
            board[x][y] = 0;
            board[x+1][y] = 0;
          } 
        }
        used[i][j] = 0;
        used[j][i] = 0;
      }
    }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  int test = 1;
  while(1){
    cin >> n;
    if (n == 0) break;

    for (int i=0; i<n; i++){
      int num[2];
      for (int j=0; j<2; j++){
        string str;
        cin >> num[j];
        cin >> str;

        int x = str[0]-'A';
        int y = str[1]-'1';

        board[x][y] = num[j];
      }
      used[num[0]][num[1]] = 1;
      used[num[1]][num[0]] = 1;
    }

    for (int j=1; j<=9; j++){
      string str;
      cin >> str;
      int x = str[0]-'A';
      int y = str[1]-'1';

      board[x][y] = j;
    }
    

    cout << "Puzzle " << test << endl;
    solve();

    test++;
    fin = false;
    memset(board, 0, sizeof(board));
    memset(used, 0, sizeof(used));
  }
}