2239. 스도쿠

멍진이·2021년 6월 16일
0

백준 문제풀기

목록 보기
13/36

문제 링크

2239. 스도쿠

문제 코드


def is_promising(blank,num):

    x,y = blank

    if num in sudoku[x]: #가로 검사
        return False

    for i in range(9): #세로 검사
        if num == sudoku[i][y]:
            return False

    square_x = x//3
    square_y = y//3

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

    return True

def print_sudoku():
    print("==========")
    for i in range(9):
        print(sudoku[i])


def back_tracking(idx):

    global is_solved

    if is_solved == True:
        return

    if idx >= len(blank_list):
        is_solved = True
        return

    blank = blank_list[idx]

    for i in range(1,10):
        if is_promising(blank,i):
            sudoku[blank[0]][blank[1]] = i
            #print_sudoku()
            back_tracking(idx+1)
            if is_solved == True:
                return
            sudoku[blank[0]][blank[1]] = 0




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

is_solved = False
back_tracking(0)

for i in range(9):
    result = ""
    for j in range(9):
        result += str(sudoku[i][j])

    print(result)

문제 풀이

  • 스도쿠를 입력하면서 blank들을 찾아서 list에 보관
  • backtracking은 blank_list 순서대로
  • promising 한 값들을 넣어가면서 sudoku를 채움
  • 숫자가 작은 순서대로 넣기때문에, 첫번째 나오는 스도쿠가 반드시 가장 작은 스도쿠임
  • 따라서 blank를 다채우게 되면 더 이상 스도쿠를 찾을 필요가 없음
  • isSolved를 True로 바꿔주고 스도쿠 찾는과정을 그만두도록 함
  • 찾은 스도쿠를 출력해주면 종료
profile
개발하는 멍멍이

0개의 댓글