2580. 스도쿠

문제 링크

2580. 스도쿠

코드

def print_sudoku():
    for len_su in sudoku:
        tmp_str = ""
        for i in len_su:
            tmp_str += str(i) + " "
        print(tmp_str)

def is_promising(row,col,num):

    #가로 가능한 숫자 리스트
    for j in range(9):
        if sudoku[row][j] == num :
            return False
    #세로 가능한 숫자 리스트
    for j in range(9):
        if sudoku[j][col] == num:
            return False

    #정사각형 숫자 리스트
    square_row = (row)//3
    square_col = (col)//3

    for i in range(square_row*3, square_row*3+3):
        for j in range(square_col*3,square_col*3+3):
            if sudoku[i][j] == num:
                return False

    return True

def back_tracking_sudoku(blank_idx):

    global sudoku
    global idx
    global blank_list
    global isSolved

    if isSolved:
        return

    if blank_idx == len(blank_list):
        print_sudoku()
        isSolved = True
        return

    blank = blank_list[blank_idx]

    row = blank[0]
    col = blank[1]

    if sudoku[row][col] ==0: # 숫자가0일때
        for i in range(1,10):
            if is_promising(row,col,i):
                sudoku[row][col] = i
                back_tracking_sudoku(blank_idx+1)
                sudoku[row][col] = 0



idx = 0
sudoku = [[0 for col in range(9)]for row in range(9)]

isSolved = False
blank_list =[]

for i in range(9):
    num_list = list(map(int, input().split()))
    for j in range(9):
        sudoku[i][j] = num_list[j]
        if num_list[j] == 0:
            blank_list.append([i,j])

back_tracking_sudoku(0)

문제 풀이

• 스도쿠를 입력받을 때 blank도 같이 입력 받는다.

• back tracking 할때 blank list에서 하나씩 뽑아서 하도록 한다.
  - blank list를 따로 안하고, row와 col을 돌아가는 방식으로 했더니 꼬임

• back tracking 할때는 값을 넣고, 호출하고, 다시 그부분을 0으로 만들어 주는것을 기억한다.

• back tracking 할때는 blank_idx를 인자로 돌린다.

• blank idx가 전체 blank list의 길이와 같아지면 전부 다 찾은것으로 간주한다.
  - backtracking 호출할때 +1 해서 돌리므로, 분기문을 빠져나갈때는 len(blank_idx)와 동일해야한다.
  

• 여러개의 답이 나올수 있는 스페셜 저지이므로 한번 답을 찾으면 다른 답은 출력 못하도록 isSolved로 관리한다.