[백준 2580] 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

---

접근

기본적으로 완전탐색이 필요했다. 0인 곳을 찾아서 1~9까지의 숫자 중 넣을 수 있는 수를 넣어보는 것이다. 

여기서 중복을 제거할 수 있는 것이 무엇이 있는지 생각해봤다. 0인 곳을 찾아 숫자를 채워넣고 다음 0을 찾을 때 또 2중 for문을 사용한다. => 미리 0인 곳을 찾아서 저장해둔다.

 

이제 0인 곳을 찾았을 때 넣을 수 있는 수를 어떻게 판별할지 생각해야한다.

해당 칸의 행과 열을 체크하는 것은 쉬웠다. 하지만 해당 칸을 탐색하는 방법이 떠오르지 않았고 다른 사람들의 풀이를 참고하였다. 

해당 좌표를 3으로 나눈 몫을 인덱스로 활용할 수 있었다.

이제 넣을 수 있는 숫자들을 리스트로 반환하여 DFS를 진행한다.

 

구현

- DFS를 통해 탐색을 진행한다.

- 지금까지 채운 0의 개수가 총 0의 개수와 같을 때 출력하고 종료한다.

- 그렇지않다면 채워야할 0의 좌표를 꺼내고 is_possible 함수로 좌표를 전달하여 넣을 수 있는 숫자를 받는다.

- 후보가 되는 숫자들을 하나씩 해당 좌표에 넣고 다음으로 넘어간다.

def dfs(zero_count):
    if zero_count == len(zeros):
        for y in range(9):
            for x in range(9):
                print(sdoku_map[y][x], end=' ')
            print()
        exit(0)

    (y, x) = zeros[zero_count]
    numbers = is_possible(y, x)

    for number in numbers:
        sdoku_map[y][x] = number
        dfs(zero_count+1)
        sdoku_map[y][x] = 0

- 아래의 함수는 해당 좌표에 넣을 수 있는 후보 숫자들을 출력하는 함수이다.

- numbers에 1부터 9까지의 수를 저장한다.

- 먼저 행과 열을 탐색하여 존재하는 수를 numbers 리스트에서 지운다.

- 이후 해당 3x3 칸에 수가 존재하는지 판단하고 있다면 지운다.

- 이렇게해서 최종적인 후보 숫자들을 반환한다.

def is_possible(y, x):
    numbers = [n+1 for n in range(9)]

    for k in range(9):
        if sdoku_map[y][k] in numbers:
            numbers.remove(sdoku_map[y][k])
        if sdoku_map[k][x] in numbers:
            numbers.remove(sdoku_map[k][x])

    y //= 3
    x //= 3
    for i in range(y*3, (y+1)*3):
        for j in range(x*3, (x+1)*3):
            if sdoku_map[i][j] in numbers:
                numbers.remove(sdoku_map[i][j])

    return numbers

---

전체 코드

import sys
input = sys.stdin.readline
def is_possible(y, x):
    numbers = [n+1 for n in range(9)]

    for k in range(9):
        if sdoku_map[y][k] in numbers:
            numbers.remove(sdoku_map[y][k])
        if sdoku_map[k][x] in numbers:
            numbers.remove(sdoku_map[k][x])

    y //= 3
    x //= 3
    for i in range(y*3, (y+1)*3):
        for j in range(x*3, (x+1)*3):
            if sdoku_map[i][j] in numbers:
                numbers.remove(sdoku_map[i][j])

    return numbers
def dfs(zero_count):
    if zero_count == len(zeros):
        for y in range(9):
            for x in range(9):
                print(sdoku_map[y][x], end=' ')
            print()
        exit(0)

    (y, x) = zeros[zero_count]
    numbers = is_possible(y, x)

    for number in numbers:
        sdoku_map[y][x] = number
        dfs(zero_count+1)
        sdoku_map[y][x] = 0


sdoku_map = [list(map(int, input().split())) for _ in range(9)]
zeros = []
for i in range(9):
    for j in range(9):
        if sdoku_map[i][j] == 0:
            zeros.append((i, j))

dfs(0)