백준 2580 스도쿠 / python

문제 : 2580

풀이 point

빈칸을 선택한 뒤 10개의 숫자 중 하나를 선택해서 가로, 세로, 3x3 범위에 같은 숫자가 있는지 파악한다. 없다면 숫자를 확정짓고 다음 가지로 넘어간다.

풀이 방법

3x3은 다음과 같은 수식으로 확인할 수 있다.

    for i in range(3):
        for j in range(3):
            if n == grid[x//3 * 3 + i][y//3 * 3 + j]

먼저 빈칸의 개수를 구한 뒤 백트래킹을 진행한다. 만약 백트래킹 깊이가 빈칸의 개수만큼 깊어졌다면 답이 구해진 것이므로 출력하고 종료한다.
백트래킹을 활용하여 경우의 수를 확인하고 답을 구할 수 있다.

코드

#백준 2580, 스도쿠

import sys
input = sys.stdin.readline

def back(depth):
   if depth == len(zero):
       for num in grid:
           print(*num)
       exit()

   x, y = zero[depth]

   for i in range(1, 10):
       if rowCheck(x, i) and colCheck(y, i) and threeBy(x, y, i):
           grid[x][y] = i
           back(depth+1)
           grid[x][y] = 0

def rowCheck(x, n):
   return n not in grid[x]

def colCheck(y, n):
   for i in range(9):
       if n == grid[i][y]:
           return False
   return True

def threeBy(x, y, n):
   for i in range(3):
       for j in range(3):
           if n == grid[x//3 * 3 + i][y//3 * 3 + j]:
               return False
   return True

grid = [list(map(int, input().rstrip().split())) for _ in range(9)]
zero = []

for i in range(9):
   for j in range(9):
       if grid[i][j] == 0:
           zero.append([i, j])

back(0)