[Python]백트래킹 백준 2580

   문제

   https://www.acmicpc.net/problem/2580

나에게는 매우 친숙한 퍼즐이다.

중학교 시절 신문에 나오던 스도쿠 문제를 풀던 기억이 난다. 

풀이방식은 앞에 문제들과 비슷할거같다.

import sys
 
 
sdk = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sdk[i][j] == 0]
 
 
def sudoku(index):
    # 한 바퀴에서 모든 경우를 다 보았으면 출력
    if index == len(zeros):#더이상 넣을곳이 없어지면
        for row in sdk:
            print(*row)
        sys.exit(0)#하나이상 있을시 하나만 출력
 
    x = zeros[index][0]#넣을곳의 x좌표
    y = zeros[index][1]#넣을곳의 y좌표
    dx = (x // 3) * 3
    dy = (y // 3) * 3
 
    # 사용할 수 있는 숫자 9개 0은 못쓰기때문에 처음부터 false로 둔다.
    num_list = [0] + [1 for _ in range(9)]
    ##가로세로 박스를 검사해 넣을수 있는숫자만 true로 남긴다.
    for j in range(9):
        # 가로 검사
        if (sdk[x][j]):#가로의 숫자 체크 불가능한 숫자 모두 num list에서 false로 만들어줌
            num_list[sdk[x][j]] = 0
            # 세로 검사
        if (sdk[j][y]):#세로의 숫자 체크
            num_list[sdk[j][y]] = 0
 
        # 3*3 box 검사
    for i in range(dx, dx + 3):
        for j in range(dy, dy + 3):
            check_num = sdk[i][j]
            if (check_num):
                num_list[check_num] = 0
 
        # 현재 가능한 수(후보숫자)만 가져옴
        # 가능한 수를 가져왔으면, 이전에 다뤄왔던 백트래킹을 사용하면 됨
    candidate_list = []
    for i in range(len(num_list)):
        if num_list[i]==1:
            candidate_list.append(i)
 
    # 후보숫자 하나씩 넣어봄
    for num in candidate_list:
        sdk[x][y] = num
        sudoku(index + 1)#다음 칸
        sdk[x][y] = 0
 
sudoku(0)

백트래킹은 많은 문제에 사용될거 같다.

어렸을때 손으로 풀어 보았던 문제를 컴퓨터로 풀어보니 색다른 경험이었다.

네모네모로직과 같은 문제들도 컴퓨터로 풀수있다면 풀어봐야겠다.