Судоку можно поручить и компьютеру. Проще всего подставлять цифры в пустые клетки по очереди, а в тупике вернуться на шаг назад и начать заново. Такой метод называют перебором с возвратом (backtracking).

Идея перебора с возвратом

  1. Идём с левого верхнего угла и ищем пустую клетку.
  2. Пробуем ставить в неё цифры от 1 до 9 по порядку. Если такая цифра уже есть в той же строке, столбце или блоке, пропускаем её.
  3. Если какую-то цифру поставить можно, ставим и переходим к следующей пустой клетке.
  4. Если в клетку не подходит ни одна цифра, возвращаемся к предыдущей клетке и пробуем следующую цифру.
  5. Когда пустых клеток не осталось, судоку решено.

Человек старается не гадать, а компьютер может сразу вернуться после ошибки, поэтому он находит ответ быстро, даже перебирая всё подряд.

Как это выглядит на 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 и для оценки сложности задачи используется другой способ.

  1. Для каждой пустой клетки хранится список цифр, которые в неё подходят (кандидаты).
  2. Начиная с простых приёмов, ищем тот, который можно применить.
  3. Сделав один ход, снова ищем с самого простого приёма.

Приёмов 15, и они идут от простых к сложным: от «эта цифра подходит только сюда» и «сюда подходит только эта цифра» до запертых кандидатов, пар, X-Wing, XY-Wing и Swordfish (как решать судоку). Раз порядок такой же, как у человека, видно, какой приём понадобился. По этому определяют ★ и объясняют причину в подсказке.