스도쿠는 컴퓨터에게 풀게 할 수도 있어요. 가장 간단한 방법은 빈칸에 숫자를 차례로 넣어 보고, 막히면 한 칸 되돌아가 다시 해 보는 거예요. 이 방법을 백트래킹(되돌아가기)이라고 해요.
백트래킹의 아이디어
- 왼쪽 위부터 차례로 빈칸을 찾는다.
- 그 칸에 1부터 9까지 차례로 넣어 본다. 같은 행·열·박스에 같은 숫자가 있으면 그 숫자는 건너뛴다.
- 넣을 수 있는 숫자가 있으면 넣고 다음 빈칸으로 간다.
- 어떤 숫자도 넣을 수 없는 칸에 오면, 한 칸 앞으로 돌아가 다음 숫자를 시도한다.
- 빈칸이 없어지면 완성.
사람이 풀 때는 찍는 것을 피하지만, 컴퓨터는 틀리면 곧바로 되돌아갈 수 있어서 닥치는 대로 해 봐도 금방 답에 도착해요.
파이썬으로 쓰면
판은 81개의 숫자를 왼쪽 위에서 오른쪽으로, 위에서 아래로 늘어놓은 리스트로 나타내요(0은 빈칸). i번째 칸은 i÷9의 몫이 행, 나머지가 열이에요.
def can_place(grid, r, c, d):
# 같은 행·열·박스에 d가 없으면 놓을 수 있다
for k in range(9):
if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
return False
br, bc = r // 3 * 3, c // 3 * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if grid[rr * 9 + cc] == d:
return False
return True
def solve(grid):
# 빈칸을 찾아 1~9를 차례로 시도한다. 막히면 되돌아간다
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
if solve(grid):
return True
grid[i] = 0
return False
return True
puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9])) 실행하면 다음처럼 답이 표시돼요. 문제는 앱 NumberPlace의 ★1 문제예요.
3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8 해가 몇 개인지 세기
문제를 만들 때는 해가 하나뿐인지 확인하고 싶어져요(해가 하나가 되는 이유). 위 프로그램을 조금 바꿔서, 해를 찾아도 멈추지 않고 계속 세면 해의 개수를 알 수 있어요. 두 개가 발견된 시점에서 “하나가 아니다”를 알 수 있으니, 거기서 중단해요.
def count_solutions(grid, limit=2):
# 해를 limit개 찾으면 멈춘다(2개가 나오면 "하나가 아니다"를 알 수 있다)
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
found = 0
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
found += count_solutions(grid, limit - found)
grid[i] = 0
if found >= limit:
break
return found
return 1
grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid)) 위의 ★1 문제에서는 1이, 해가 두 개인 문제에서는 2가 표시돼요.
빠르게 만드는 요령
왼쪽 위부터 차례로 시도하는 대신, 넣을 수 있는 숫자가 가장 적은 칸부터 시도하면 훨씬 빨라져요. 후보가 하나뿐인 칸부터 채워 가면 거의 되돌아가지 않아도 되니까요. 앱 NumberPlace에서 해의 개수를 확인할 때도 이 순서로 시도해요.
사람과 같은 기법으로 푸는 방법
백트래킹은 빠르고 확실하지만, “왜 거기에 그 숫자가 들어가는지”는 알려 주지 않아요. 앱 NumberPlace의 힌트와 문제의 난이도 판정에는 또 다른 방법을 써요.
- 빈칸마다 들어갈 수 있는 숫자(후보)를 가지고 있는다.
- 쉬운 기법부터 차례로, 쓸 수 있는 것을 찾는다.
- 한 수 나아가면, 다시 가장 쉬운 기법부터 찾는다.
기법은 “여기에만 들어간다”, “이 숫자만 들어간다”에서 시작해 후보 한정, 페어, X-Wing, XY-Wing, 소드피시까지 15종류를 쉬운 순서로 늘어놓았어요(스도쿠 푸는 법). 사람이 푸는 것과 같은 순서로 나아가기 때문에 어떤 기법이 필요했는지 알 수 있고, 그걸로 ★를 정하거나 힌트로 이유를 보여 줄 수 있어요.
