스도쿠

처음 시도해본건 거의 3주 전이었다. 그날도 몇 시간 동안 스트레스를 받다가 결국 풀지 못했었는데, 오늘도 거의 3시간 동안 고민을 했다.

처음에는 가로, 세로, 사각형 구역에서 빈칸이 한개인 좌표의 값들을 스도쿠 내에 0이 없어질 때 까지 채워나갔다.

이런 방식으로 풀면 시간 복잡도도 문제이지만, 가로, 세로, 사각형에 모두 빈칸이 2개씩 존재할 경우에 빈칸이 한개인 좌표를 찾지 못해 영원히 while문을 돌게 된다.

1 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
4 6 9 2 0 8 1 0 5

스도쿠의 일부를 가져왔다. 여기서 0이 존재하는 칸을 살펴보자. 가로로 탐색해도 0이 한개인 칸이 없고, 세로, 사각형으로 탐색해도 그렇다. 이렇게 될 경우 빈칸에 가능한 값들 중 한가지 값을 임의로 넣고 다음단계로 진행해야 하는데 위의 방식대로 풀어나간다면 오류가 날 수 밖에 없다.

그래서 빈칸에 들어갈 수 있는 값들 중 한 가지를 계속 넣어보며 탐색해 나가는 DFS방식을 사용해야 한다.

문제에서 ‘스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.’라고 했음으로 DFS방식으로 탐색하다가 빈칸을 모두 채우면 그때 스도쿠를 출력하고 종료하면 된다.(혼자 생각해낸 것은 아니고, 결국 다른 분의 풀이를 읽고 알게되었다…)

문제의 힌트를 얻기 위해 들어오신 분들은 여기까지 읽고 다시 한번 풀어보면 좋을 것 같다.

위의 방식을 코드로 구현하기 위해 DFS를 위한 함수와 빈 칸에 들어갈 수 있는 수의 목록을 받아오는 함수를 만들었다. 각각 dfs, possible 이다.

possible(x,y)

• 해당 빈칸의 좌표를 입력으로 받는다.
• 먼저 1~9로 이루어진 ‘numlist’리스트를 생성한다.
• 가로, 세로 그리고 상자를 탐색하며 이들 내에 존재하는 수를 ‘numlist’에서 제거해 나간다.
• 빈 칸에 들어갈 수 있는 수들로 이루어진 리스트를 반환한다.

dfs(x)

• x를 입력받아 ‘zero’에 저장된 빈칸을 차례로 선택하게 된다.
• 만약 x가 빈칸의 개수와 동일하다면 빈칸이 모두 채워졌다는 뜻임으로 스도쿠를 출력하고, 시스템을 종료한다.
• ‘possible’ 함수로 부터 가능한 숫자들을 받아와 DFS를 진행한다.
• 숫자들을 빈칸에 집어넣고, dfs(x+1)을 실행시켜 다음 빈칸을 탐색한다.
• 이때, 집어넣은 숫자가 틀린 숫자일 수도 있음으로 해당 dfs가 종료되면 다시 빈칸으로 만들어 다음 노드가 실행될 수 있도록 한다.

CODE

import sys

def possible(x,y):
    #1-9까지의 숫자중 어떤 숫자가 비어있는지 확인
    numlist=list(range(1,10))
    #1-9로 이루어진 리스트 numlist를 생성하고,
    #가로, 세로, 상자내에 존재하는 숫자들을 제거해 나간다.
    for i in range(9):
        #가로
        if numbs[x][i] in numlist: numlist.remove(numbs[x][i])
        #세로
        #여기서 elif로 쓰는 실수를 해서 1시간 동안 고민했었는데 반드시 if 문을 써주어야한다!
        if numbs[i][y] in numlist: numlist.remove(numbs[i][y])
    #상자
    a=(x//3)*3
    b=(y//3)*3
    for i in range(3):
        for j in range(3):
            if numbs[a+i][b+j] in numlist:
                numlist.remove(numbs[a+i][b+j])

    return numlist  #빈칸에 들어갈 수 있는 숫자들 return

# 정답이 여러개라면 아무거나 출력해도 상관 없음으로
# 0인 칸에 들어갈 수 있는 수들에 대해서 dfs진행
def dfs(x):
    if x==len(zero):
        for i in numbs:
            print(*i)
        sys.exit() # 스도쿠가 출력되었으면 시스템 종료!

    a=zero[x][0]
    b=zero[x][1]
    N=possible(a,b)

    for n in N:
        numbs[a][b]=n
        dfs(x+1)
        numbs[a][b]=0
    return

numbs=list(list(map(int,sys.stdin.readline().split())) for _ in range(9))
# 0인 칸들의 좌표들을 zero에 추가
zero=[]
for i in range(9):
    for j in range(9):
        if numbs[i][j]==0: zero.append([i,j])

dfs(0)

[다시 풀어보기]