[백준] 4056번: 스-스-스도쿠

스스로 푼 문제: O
걸린 시간: 52분

문제

골드4 - 4056번: 스-스-스도쿠

풀이

가로줄 조건으로 각 0에 들어갈 숫자 후보를 파악해서 백트래킹으로 모든 경우의 수를 탐색한다.

코드

import collections

def check_answer(board):
  # 가로줄 조건 확인
  for r in range(9):
    if sum(board[r]) != 45:
      return False
  
  # 세로줄 조건 확인
  for c in range(9):
    total = 0
    for i in range(9):
      total += board[i][c]
    if total != 45:
      return False
  
  for a in range(0, 9, 3):
    for b in range(0, 9, 3):
      total = 0
      total += sum(board[a][b:b+3])
      total += sum(board[a+1][b:b+3])
      total += sum(board[a+2][b:b+3])
      if total != 45:
        return False
  
  for r in range(9):
    print(*board[r], sep='')
  return True

def back_tracking(idx, board):
  global flag
  # 종료 조건
  if idx == 5:
    if flag or check_answer(board): # 정답인 경우
      flag = True
    return

  for num in graph[zeros[idx]]:
    i, j = divmod(zeros[idx], 9)
    board[i][j] = num
    back_tracking(idx+1, board)
    board[i][j] = 0


n = int(input())

for t in range(n):
  board = [list(map(int, list(input()))) for _ in range(9)]
  graph = collections.defaultdict(list)
  flag = False
  zeros = []

  # 0의 위치 찾기 & 0에 들어갈 숫자 후보 파악
  check = [i for i in range(1, 10)]
  for i in range(9):
    for j in range(9):
      if board[i][j] == 0:
        num = i*9+j
        zeros.append(num)
        graph[num] = list(set(check) - set(board[i]))

  back_tracking(0, board)

  if not flag:
    print("Could not complete this grid.")
  
  if t != n-1:
    print('')