[백준] 2580번: 스도쿠

문제

백준 - 2580번: 스도쿠

분석

스도쿠 문제와 같이, 비어있는 칸을 채워넣는 문제이다.

9X9 칸이므로 복잡한 생각없이 백트래킹으로 경우를 따져보면 된다.
먼저 빈 칸의 위치를 저장해두고, 그 빈 칸의 위치를 모두 채워넣는 경우가 되면 모든 규칙에 맞게 채워진 것이기 때문에 즉시 출력하고 프로그램을 종료한다.

1~9까지 빈 칸에 넣어보면서 가로, 세로, 3X3칸 규칙에 맞는지 확인해보면서 진행한다.
규칙에 맞으면 그 칸에 해당 값을 넣고 다음 빈 칸을 채우러 재귀호출한다. 그 작업이 끝나면 현재 칸을 다시 0으로 채워 모든 경우를 따진다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

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

def isPossible(x, y, num):
    for row in range(9):
        if board[row][y] == num:
            return False
    for col in range(9):
        if board[x][col] == num:
            return False
    for i in range(3):
        for j in range(3):
            if board[x//3*3+i][y//3*3+j] == num:
                return False
    return True
    
def solve(i):
    if i == len(pos):
        for idx in range(9):
            print(*board[idx])
        exit(0)
    x, y = pos[i]
    for num in range(1, 10):
        if isPossible(x, y, num):
            board[x][y] = num
            solve(i + 1)
            board[x][y] = 0
            
pos = [] # blank position
for i in range(9):
    for j in range(9):
        if not board[i][j]:
            pos.append((i, j))
solve(0)

*pypy로 제출해야 통과된다

끝으로..

문제에 상황에 따라서 단순하게도 생각하는 연습이 필요한 것 같다.