[백준 2239번] 스도쿠 (Python3)

import sys
input = sys.stdin.readline

sudoku = []
for i in range(9):
  sudoku.append(list(map(int,list(input().strip()))))

def check(y,x,n):
  for i in range(9):
    if sudoku[y][i] == n or sudoku[i][x] == n:
      return False
  for i in range(3):
    for j in range(3):
      if sudoku[y-y%3+i][x-x%3+j] == n:
        return False
  return True

finish = False  
def solsudoku(y,x):
  global finish
  if finish:
    return
  if x==9:
    solsudoku(y+1,0)
    return
  if y==9:
    finish=True
    return
  if sudoku[y][x] != 0:
    solsudoku(y,x+1)
    return
  for i in range(1,10):
    if check(y,x,i):
      sudoku[y][x] = i
      solsudoku(y,x+1)
      if not finish:
        sudoku[y][x] = 0

solsudoku(0,0)

for i in sudoku:
  print("".join(map(str,i)))

전형적인 백트래킹 문제이다.

check함수를 이용해서 가로, 세로, 작은사각형 내에 같은 숫자가 있는지 확인하고 없으면 해당 숫자로 바꾼뒤 재귀호출하는 방식이다.

 

이 문제도 파이썬이 파이썬해서 pypy3로 제출하였다.

 

 

오늘의 교훈) 파이썬은 구리다