[PyPy] boj no. 2239 : 스도쿠

Problem

https://www.acmicpc.net/problem/2239

Idea

전형적인 백트래킹 문제.

숫자가 채워지지 않은 칸을 찾아 리스트화한 뒤 백트래킹을 통해 각 칸에 들어갈 숫자들을 구했다. 기본적인 스도쿠의 풀이 방식인 같은 행과 열과 네모 섹터에 포함되는 숫자들을 탐색 대상에서 제외하여 유망하지 않은 번호들을 제거했다.

답이 여러 개 있다면 사전식으로 앞서는 것을 출력하므로 빈칸 리스트의 순서가 퍼즐의 행을 기준으로 이루어져야 한다.

Code

import sys

input = sys.stdin.readline

tile = [list(map(int, input().rstrip())) for _ in range(9)]
blank = [(i, j) for i in range(9) for j in range(9) if tile[i][j] == 0]

def blank_check(cy, cx, tgt):
    
    for i in range(9):
        if tile[i][cx] == tgt or tile[cy][i] == tgt:
            return False
        
    ty, tx = cy // 3 * 3, cx // 3 * 3    
    for i in range(ty, ty+3):
        for j in range(tx, tx+3):
            if tile[i][j] == tgt:
                return False
            
    return True
         

def bt(seq):
    if seq == len(blank):
        for line in tile:
            print(*line, sep='')
        
        sys.exit()
    
    for i in range(1, 10):
        if blank_check(blank[seq][0], blank[seq][1], i):
            tile[blank[seq][0]][blank[seq][1]] = i
            bt(seq+1)
            tile[blank[seq][0]][blank[seq][1]] = 0
       
bt(0)

Comment