Судоку можно поручить и компьютеру. Проще всего подставлять цифры в пустые клетки по очереди, а в тупике вернуться на шаг назад и начать заново. Такой метод называют перебором с возвратом (backtracking).
Идея перебора с возвратом
- Идём с левого верхнего угла и ищем пустую клетку.
- Пробуем ставить в неё цифры от 1 до 9 по порядку. Если такая цифра уже есть в той же строке, столбце или блоке, пропускаем её.
- Если какую-то цифру поставить можно, ставим и переходим к следующей пустой клетке.
- Если в клетку не подходит ни одна цифра, возвращаемся к предыдущей клетке и пробуем следующую цифру.
- Когда пустых клеток не осталось, судоку решено.
Человек старается не гадать, а компьютер может сразу вернуться после ошибки, поэтому он находит ответ быстро, даже перебирая всё подряд.
Как это выглядит на Python
Доска — это список из 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])) Если запустить программу, на экране появится решение. Задача здесь — ★1 из приложения NumberPlace.
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 решений (если их два, решение не единственное)
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 и для оценки сложности задачи используется другой способ.
- Для каждой пустой клетки хранится список цифр, которые в неё подходят (кандидаты).
- Начиная с простых приёмов, ищем тот, который можно применить.
- Сделав один ход, снова ищем с самого простого приёма.
Приёмов 15, и они идут от простых к сложным: от «эта цифра подходит только сюда» и «сюда подходит только эта цифра» до запертых кандидатов, пар, X-Wing, XY-Wing и Swordfish (как решать судоку). Раз порядок такой же, как у человека, видно, какой приём понадобился. По этому определяют ★ и объясняют причину в подсказке.
