빈칸 목록을 미리 만들어놓고 앞에서부터 하나씩 채우는 백트래킹이다. 뼈대는 이렇다.
def sudoku(n, board):
if n == zeroNum:
for i in board:
print(*i)
return
r, c = zero[n]
...
board[r][c] = i
sudoku(n + 1, board)
board[r][c] = 0
넣고, 내려가고, 돌아오면 0으로 되돌린다. 되돌리는 마지막 줄이 백트래킹의 전부다.
빈칸을 zero 리스트로 뽑아둔 게 편했다. 다음 빈칸을 찾으려고 판을 다시 훑지 않아도 되고, n 하나로 어디까지 왔는지가 정해진다.
조건 세 개를 각각 확인하기
처음에는 1부터 9까지 넣어보면서 매번 세 방향을 확인했다.
for i in range(1, 10):
con1 = not i in [j[c] for j in board]
con2 = not i in board[r]
con3 = not i in sum([j[c-c%3:][:3] for j in board[r-r%3:][:3]], [])
if con1 and con2 and con3:
board[r][c] = i
sudoku(n + 1, board)
board[r][c] = 0
c - c % 3 이 3x3 상자의 왼쪽 끝이다. c 가 4면 4 % 3 = 1이라 3이 되고, 거기서 세 칸을 잘라 그 상자의 열 범위가 된다. 행도 같은 식이다.
문제는 이 세 줄이 후보 하나마다 다시 돈다. 빈칸 하나를 채우려고 세로줄과 가로줄과 상자를 아홉 번씩 다시 만든다.
후보를 한 번에 구하기
칸이 정해지면 세로줄, 가로줄, 상자는 하나로 정해진다. 후보를 하나씩 물어볼 게 아니라 못 쓰는 숫자를 한 번에 모으면 된다.
li = set([i for i in range(1, 10)])
li1 = set([j[c] for j in board])
li2 = set(board[r])
li3 = set(sum([j[c-c%3:][:3] for j in board[r-r%3:][:3]], []))
for i in li - (li1 | li2 | li3):
board[r][c] = i
sudoku(n + 1, board)
board[r][c] = 0
세 집합을 합치고 1~9에서 뺀다. 남은 게 그대로 후보라 if 가 사라진다. 반복문이 후보 개수만큼만 돈다.
세로줄과 가로줄과 상자를 만드는 일이 빈칸당 세 번으로 줄었다. 앞의 것은 스물일곱 번이었다.
li1 에 0이 섞여 들어가는데 빼는 쪽이라 상관없다. 1~9에 0이 없으므로 결과가 달라지지 않는다.
시간은 안 재졌다
두 셀 모두 time.time() 으로 재도록 해뒀는데, 이 판은 빈칸이 39개라 어느 쪽이든 순식간에 끝난다. 숫자로는 차이가 안 나왔다.
빈칸이 많고 후보가 넓은 판이라야 갈릴 텐데 그런 입력으로는 안 돌려봤다.
판이 틀려 있던 것
맨 앞의 탐색용 셀에 적어둔 판은 같은 열에 8이 두 번, 1이 두 번 들어가 있었다. 그대로는 답이 없는 판이다.
실제로 푸는 두 셀에서는 고쳐져 있다. 옮겨 적다 틀린 것을 돌려보고 나서 잡은 것으로 보인다.