문제 링크
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
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로 바꿔주고 스도쿠 찾는과정을 그만두도록 함
- 찾은 스도쿠를 출력해주면 종료