[BaekJoon] 백준 2239번 : 스도쿠

2239번 : 스도쿠

손으로만 풀어보던 스도쿠를 프로그래밍으로 푸는건 처음이라 재미있었다.

재미는 있었지만 내가 풀던 방법을 코드로 옮기자니 정말 어려웠다..

풀이 방법은 빈 칸마다 올 수 있는 모든 수를 가져온다.

그리고 DFS 를 통해 가능한 모든 경우를 따져보면 된다.

빈 칸이 다 안채워졌는데 가능 한 수가 없다면 그 경우는 만들 수 없는 경우니까 다시 되돌아가 작업한다.

---

def candidating_nums(i, j):
    nums = {num: True for num in range(10)}

    for k in range(9):
        nums[sudoku[i][k]] = False
        nums[sudoku[k][j]] = False

    for x in range((i // 3) * 3, (i // 3) * 3 + 3):
        for y in range((j // 3) * 3, (j // 3) * 3 + 3):
            nums[sudoku[x][y]] = False

    return nums


def DFS(count, loop, zero_pos):
    global sudoku

    if count == loop:
        for row in sudoku:
            print(''.join(map(str, row)))
        exit(0)

    i, j = zero_pos[count]
    candidate = candidating_nums(i, j)

    for num in candidate:
        if candidate[num]:
            sudoku[i][j] = num
            DFS(count + 1, loop, zero_pos)
            sudoku[i][j] = 0


def solution():
    zero_pos = []

    for i in range(9):
        for j in range(9):
            if sudoku[i][j] == 0:
                zero_pos.append([i, j])

    loop = len(zero_pos)
    DFS(0, loop, zero_pos)


if __name__ == "__main__":
    sudoku = [list(map(int, input())) for _ in range(9)]

    solution()