Как генерируется судоку: алгоритм и код на Python

Даниил Фенелонов 18 мая 2026 г. 4 минуты чтения

Содержание

Всем привет! 👋 Последнее время подсел на судоку. Стало интересно, как работает генерация новых задачек, так что давайте разберемся по шагам, как генерируется полная сетка, почему нельзя просто убрать случайные числа, и как контролируется сложность.

Почему нельзя просто расставить числа случайно

Происходит это в два этапа. Сначала мы генерируем финальный ответ. Очевидно, рандомно расставить числа не получится, потому что с огромной вероятностью будет конфликт либо в строчке, либо в столбце, либо в квадрате 3x3.

Далее мы должны удалять значения из ячеек, пока не получим готовое нерешенное судоку, но важно помнить, что решение должно быть единственным.

Поэтому генерация состоит из двух отдельных шагов, и оба нетривиальные.

Шаг 1: генерация полной валидной сетки

Используется backtracking (поиск с возвратом). Идём по клеткам слева направо, сверху вниз. В каждую пытаемся поставить число. Если число не конфликтует со строкой, столбцом и квадратом 3×3, двигаемся дальше. Если допустимых чисел нет, откатываемся на шаг назад и пробуем другое число.

Чтобы каждый запуск давал новую сетку, порядок перебора чисел (1-9) рандомизируется. Вместо «попробуй 1, потом 2, потом 3…» алгоритм делает «попробуй 7, потом 2, потом 9…» в рандомном порядке.

Пример на сетке 4×4

Чтобы не рисовать сетку 9×9, покажем на упрощённом варианте: судоку 4×4, числа от 1 до 4, квадраты 2×2.

Пошаговый backtracking на сетке 4×4: алгоритм заполняет клетки, упирается в тупик на позиции где ни одно число не подходит, откатывается и находит другой путь

Алгоритм заполняет первые 5 клеток без проблем. На шестой не может поставить ни одно число (все конфликтуют). Откатывается на пятую, меняет число, и продолжает. Это может повторяться многократно, но для сетки 9×9 полная генерация занимает миллисекунды.

Масштаб пространства

Количество валидных полных сеток 9×9 — примерно $6.67 \times 10^{21}$ . Звучит как огромное число, но это ничтожная доля от всех возможных расстановок ( $9^{81} \approx 2 \times 10^{77}$ ). Одна валидная сетка на $10^{55}$ случайных. Вот почему случайная расстановка не работает.

Шаг 2: удаление чисел с проверкой единственности

У нас есть полная валидная сетка. Теперь нужно превратить её в головоломку: убрать часть чисел так, чтобы осталось ровно одно решение.

Алгоритм:

Берём список всех 81 клетки в случайном порядке.
Убираем число из первой клетки.
Запускаем солвер и считаем количество решений.
Если решение единственное, оставляем клетку пустой и переходим к следующей.
Если решений больше одного, возвращаем число на место и переходим к следующей клетке.
Повторяем, пока не пройдём все 81 клетку (или пока не достигнем нужного количества пустых клеток).

Почему это дорого

На каждом шаге мы фактически решаем судоку заново. И не просто решаем, а проверяем, нет ли второго решения. Для этого солвер должен найти первое решение, а потом попытаться найти второе. Если второе нашлось, число нельзя убирать.

80 клеток × решение судоку на каждом шаге = генерация в разы дороже, чем однократное решение. Вот почему генерация — задача сложнее решения.

Оптимизация: симметричное удаление

Многие генераторы убирают числа парами: клетка и её «зеркало» относительно центра (например, [1,2] и [9,8]). Это даёт визуальную симметрию, которую можно заметить в газетных судоку. Бонус: количество проверок сокращается вдвое.

Как контролируется сложность

Распространённое заблуждение: чем больше чисел убрано, тем сложнее судоку. Это не совсем так. Головоломка с 25 оставшимися числами может быть проще, чем головоломка с 30.

Сложность определяется техниками, которые нужны для решения.

Лёгкое (Easy). Решается только методом naked single: в клетке остаётся единственный возможный вариант. Смотришь на строку, столбец, квадрат, исключаешь, остаётся одно число. Повторяешь.

Среднее (Medium). Требует hidden singles: в строке (или столбце, или квадрате) есть число, которое может стоять только в одной клетке, хотя у самой клетки несколько кандидатов.

Сложное (Hard). Naked pairs, hidden pairs, pointing pairs. Нужно анализировать группы клеток, а не одиночные.

Экстремальное (Expert). X-wing, swordfish, цепочки. Техники, требующие поиска паттернов через всю сетку.

Как генератор выбирает сложность

После создания головоломки генератор запускает человекоподобный солвер, который решает судоку теми же техниками, что и человек (не backtracking, а логические правила). Солвер фиксирует, какие техники понадобились. Если хватило naked singles, головоломка помечается как Easy. Если понадобился X-wing, это Expert.

Если нужна головоломка определённой сложности, генератор повторяет процесс, пока не получит подходящую. Или использует направленное удаление: для Easy убирает числа, которые создают naked singles. Для Hard целенаправленно оставляет конфигурации, требующие продвинутых техник.

Python-демо: минимальный генератор

Вот рабочий генератор судоку в 60 строк. Генерирует полную сетку, убирает числа с проверкой единственности. Можете поиграться у себя локально:

import random
 
def is_valid(grid, row, col, num):
    # Проверка строки, столбца и квадрата 3×3
    if num in grid[row]:
        return False
    if num in [grid[r][col] for r in range(9)]:
        return False
    r0, c0 = 3 * (row // 3), 3 * (col // 3)
    for r in range(r0, r0 + 3):
        for c in range(c0, c0 + 3):
            if grid[r][c] == num:
                return False
    return True
 
def fill_grid(grid):
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                nums = list(range(1, 10))
                random.shuffle(nums)  # Рандомизация
                for num in nums:
                    if is_valid(grid, row, col, num):
                        grid[row][col] = num
                        if fill_grid(grid):
                            return True
                        grid[row][col] = 0
                return False
    return True
 
def count_solutions(grid, limit=2):
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                count = 0
                for num in range(1, 10):
                    if is_valid(grid, row, col, num):
                        grid[row][col] = num
                        count += count_solutions(grid, limit - count)
                        grid[row][col] = 0
                        if count >= limit:
                            return count
                return count
    return 1
 
def generate_sudoku(n_remove=45):
    # полная сетка
    grid = [[0]*9 for _ in range(9)]
    fill_grid(grid)
 
    # убираем числа
    cells = [(r, c) for r in range(9) for c in range(9)]
    random.shuffle(cells)
    removed = 0
 
    for row, col in cells:
        if removed >= n_remove:
            break
        backup = grid[row][col]
        grid[row][col] = 0
        if count_solutions([r[:] for r in grid]) == 1:
            removed += 1
        else:
            grid[row][col] = backup  # Откат!
 
    return grid
 
puzzle = generate_sudoku(n_remove=45)
for row in puzzle:
    print(' '.join(str(x) if x != 0 else '.' for x in row))

Результат одного запуска:

. 3 . | . 7 . | . 1 .
6 . . | 1 . 3 | . . 8
. . 9 | . . . | 3 . .
------+-------+------
3 . . | . 2 . | . . 4
. . 7 | . . . | 2 . .
8 . . | . 1 . | . . 7
------+-------+------
. . 3 | . . . | 8 . .
4 . . | 3 . 7 | . . 1
. 8 . | . 6 . | . 5 .

Каждый запуск даёт новую головоломку. 45 чисел убрано, решение единственное, гарантированно.

Итого

Генерация судоку — три вложенные задачи:

Создать валидную полную сетку. Backtracking с рандомизацией. Пространство валидных сеток — $6.67 \times 10^{21}$ , но это капля в море всех расстановок.

Убрать числа, сохранив единственность решения. На каждом шаге решаем судоку заново, чтобы убедиться, что второго решения нет. Генерация дороже решения.

Контролировать сложность. Не количество убранных чисел, а необходимые техники решения. Человекоподобный солвер классифицирует результат.

Поделиться в Telegram