BAEKJOON 2580
문제
스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
나의 처음 코드
n-queen에서 0.5단계 높은 문제인 것 같다. 백트래킹 기술을 적용하는 과정은 똑같지만, 스도쿠의 규칙상 같은 행, 같은 열, 3x3안에 있는 숫자들을 다 확인해줘야 한다.
첫번 째, 0인 리스트들을 따로 담을 수 있는 리스트 안에 넣어준다. (이 안에 들어있는 것들만 재귀로 돌리기 위해서)
두번 째, 같은 행,열 혹은 3x3안에 존재하지 않는 숫자들을 찾아서 리스트 안에 넣어준다.
세번 째, 재귀를 돌면서 재귀의 깊이가 0인 리스트들만 모여있는 크기와 같아질 때 까지 돌려준다.
위의 세 가지만 지키면 이 문제는 끝이 난다. 다른 것은 없지만, 두번 째에 언급한 부분만 효율적으로 잘 찾아주면 된다.
import sys #pypy3에서는 exit가 안 먹히기 때문에 sys.exit()를 위함
sdoku_map = [[] * 9] * 9
for i in range(9):
sdoku_map[i] = list(map(int, input().split()))
#0을 좌표를 찾는 부분
find_zero = [(i, j) for i in range(0,9) for j in range(0,9) if sdoku_map[i][j] == 0]
def find_number(depth):
#깊이가 0의 좌표 리스트의 크기와 같다면 종료
if depth == len(find_zero):
for i in sdoku_map:
print(*i)
sys.exit(0)
row, col = find_zero[depth] #0인 리스트의 좌표
num_list = [True] * 10 #어느 숫자가 available한지 확인하기 위함
num_list[0] = False
#가로 세로
for j in range(0, 9):
if sdoku_map[j][col] != 0:
num_list[sdoku_map[j][col]] = False
if sdoku_map[row][j] != 0:
num_list[sdoku_map[row][j]] = False
#3*3
for m in range((row // 3) * 3, (row // 3) * 3 + 3):
for n in range((col // 3) * 3, (col // 3) * 3 + 3):
if sdoku_map[m][n] != 0:
num_list[sdoku_map[m][n]] = False
#되는 숫자들만 모여 있는 리스트 중에서 True 인 것들. 즉, 0안에 들어갈 수 있는 숫자들의 집합
candidate_list = [idx for idx, state in enumerate(num_list) if state == True]
#백트래킹 재귀 부분
for i in candidate_list:
sdoku_map[row][col] = i
find_number(depth + 1)
sdoku_map[row][col] = 0
find_number(0)
결과는 맞았습니다. 단, pypy3에서만 통과되고 python3에서는 시간초과가 난다. 돌릴 때마다, 가능한 숫자를 찾고 리스트를 만드는데 시간을 많이 걸리는 것 같다. 그리고 이번에는 for문으로 list를 안 만들고, 보시다싶이 한줄로 리스트를 만들었다. 깔끔하고 보기 더 쉬운 것같다. 앞으로도 저렇게 만들어야겠다.