[🥇4 / 백준 2239 / 파이썬] 스도쿠

 

2239번: 스도쿠

 

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

예제 입력  103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107

예제 출력  143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127

 

풀이

 

[🥇4 / 백준 2580 / 파이썬] 스도쿠

 

위 문제와 완전히 동일한 문제이다.

단, 입출력 형식이 바뀌었고 조건만 하나 추가되었다.

백트래킹을 연습할 겸 새로 풀어보았다.

 

조건은 사전식으로 앞서는 것을 출력하라는 것인데, 무조건 백트래킹으로 완성되는 첫 번째 스도쿠 판을 출력하라는 것 같다.

어차피 백트래킹으로 문제를 해결할 것이니 딱히 상관쓰지 않아도 된다.

 

0의 좌표들을 추출하고 백트래킹을 하며 해당 자리에 들어갈 수 있는 후보 숫자들을 추린다.

그리고 그 후보 숫자들을 순서대로 대입하며 재귀를 한다.

 

만약, 재귀 깊이가 0의 개수보다 깊어진다면 문제가 풀렸다는 얘기이니 스도쿠 판을 출력하고 코드를 종료한다.

 

import sys
input = sys.stdin.readline

sudoku = [list(map(int,list(input().rstrip()))) for _ in range(9)]
zeros = [(i,j) for i in range(9) for j in range(9) if not sudoku[i][j]]
cand = [i for i in range(1,10)]

def bt(n):
    if n == len(zeros):
        for i in sudoku:
            print(*i,sep="")
        sys.exit()
        
    x,y = zeros[n]
    a,b = x//3,y//3
    cand2 = cand[:]
    
    # 박스 칸
    for i in range(3*a,(a+1)*3):
        for j in range(3*b,(b+1)*3):
            if sudoku[i][j] in cand2:
                cand2.remove(sudoku[i][j])
    
    # 가로 세로
    for i in range(9):
        if sudoku[x][i] in cand2:
            cand2.remove(sudoku[x][i])
        if sudoku[i][y] in cand2:
            cand2.remove(sudoku[i][y])
    
    for i in cand2:
        sudoku[x][y] = i
        bt(n+1)
    sudoku[x][y] = 0

if __name__ == '__main__':
    bt(0)