[백준] 2580: 스도쿠 - 백트래킹

다른 코드 참조: O, 푼 횟수: 7

풀이과정

빈칸을 돌며 빈칸에 1~9중 가능한 숫자들을 하나씩 대입해 보며 빈칸을 채우는 식으로 진행하면 된다.

 

1. 빈칸을 계속 돌며 가능한 숫자를 대입해 봐야 하므로 빈칸 위치를 저장해야 한다.

따라서, 빈칸의 위치를 저장하는 리스트 blank를 만들고 그 리스트를 돌아보게 하면 된다.

 

2. 가능한 수들은

(1). 해당 행에서 1~9 숫자 중 존재하지 않는 수

(2). 해당 열에서 1~9 숫자 중 존재하지 않는 수

(3). 해당 3*3칸에서 1~9 숫자 중 존재하지 않는 수

를 기준으로 판별하면 된다.

 

3. 다음칸도 마찬가지로 blank의 끝에 도달할때까지 계속한다.

 

4. blank의 끝에 도달했다면 출력한다.

 

 

코드

import sys

table = [[] for i in range(9)]

for i in range(9):
    table[i] = list(map(int, sys.stdin.readline().split()))


blank = []
for i in range(9):
    for ii in range(9):
        if table[i][ii] == 0:
            blank.append([i, ii])
            


def isAble(row, col, n):					#n이 가능한 수인지 판별
    for i in range(0, 9):
        if table[row][i] == n:
            return False
        if table[i][col] == n:
            return False
        if table[(row//3)*3+i//3][(col//3)*3+i%3] == n:
            return False
    return True


def sudoku(x):
    if x == len(blank): 
        for i in range(9):
             print(*table[i])
        exit(0)
    else:
        i = blank[x][0]
        ii = blank[x][1]
        for iii in range(1, 10):			#1~9
            if isAble(i, ii, iii):			#해당 수가 가능한 수인지 판별
                table[i][ii] = iii			#대입	
                sudoku(x+1)				#다음 빈칸
                table[i][ii] = 0			#만약 모든 빈칸을 채울 수 없다면 0으로 초기화

sudoku(0)