Головоломка Судоку

Судоку — это популярная головоломка на поле 9×9, где нужно заполнить клетки цифрами от 1 до 9. Условия:

• каждая строка содержит все числа от 1 до 9 без повторов;
• каждая колонка также содержит все числа от 1 до 9 без повторов;
• каждая область 3×3 содержит все числа от 1 до 9 без повторов.

Часть клеток заполнена заранее и служит подсказками. Необходимо заполнить все пустые клетки так, чтобы правила соблюдались.

Решение задачи

1. Выбор модели

Для решения задачи судоку идеально подходит модель ограничений (Constraint Satisfaction Problem, CSP). В рамках этой модели мы:

• Определяем переменные (ячейки судоку, которые нужно заполнить).
• Определяем домены (множество допустимых значений для каждой переменной, в нашем случае это цифры от 1 до 9).
• Определяем ограничения (правила судоку, которые связывают эти переменные: все значения в строке, столбце и блоке 3x3 должны быть уникальными).

Модель ограничений из библиотеки O₂ как раз предназначена для описания и решения таких задач. Ее механизм не перебирает варианты "в лоб", а использует умные алгоритмы для отсечения заведомо неверных путей поиска, что делает решение очень эффективным.

2. Создание модели

Создадим экземпляр модели, в котором будут регистрироваться переменные и ограничения. Это «контейнер», через который мы описываем задачу и затем вызываем метод решения.

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

3. Ввод данных

Определяем размерность судоку (9×9) и размер блока (3×3). В массив Подсказки заносим исходные данные, где 0 означает пустую клетку.

// Вводим начальные данные
РазмерПоля  = 9;
РазмерБлока = 3;

// Вводим значения подсказок (0 означает пустую ячейку)
Подсказки = Новый Массив(РазмерПоля);

Подсказки[0] = О2.Утилиты().МассивЧиселИзСтроки("5,3,0, 0,7,0, 0,0,0");
Подсказки[1] = О2.Утилиты().МассивЧиселИзСтроки("6,0,0, 1,9,5, 0,0,0");
Подсказки[2] = О2.Утилиты().МассивЧиселИзСтроки("0,9,8, 0,0,0, 0,6,0");

Подсказки[3] = О2.Утилиты().МассивЧиселИзСтроки("8,0,0, 0,6,0, 0,0,3");
Подсказки[4] = О2.Утилиты().МассивЧиселИзСтроки("4,0,0, 8,0,3, 0,0,1");
Подсказки[5] = О2.Утилиты().МассивЧиселИзСтроки("7,0,0, 0,2,0, 0,0,6");

Подсказки[6] = О2.Утилиты().МассивЧиселИзСтроки("0,6,0, 0,0,0, 2,8,0");
Подсказки[7] = О2.Утилиты().МассивЧиселИзСтроки("0,0,0, 4,1,9, 0,0,5");
Подсказки[8] = О2.Утилиты().МассивЧиселИзСтроки("0,0,0, 0,8,0, 0,7,9");

4. Регистрация переменных

Создадим переменные модели. Ключевой момент: для ячеек с подсказкой мы создаем константу, а для пустых ячеек — переменную, которая может принимать значения от 1 до 9.

// Создаем двумерный массив для хранения переменных модели, соответствующих ячейкам судоку
ЗначенияЯчеек = Новый Массив(РазмерПоля, РазмерПоля);

// Обходим все ячейки поля
Для Строка = 0 По РазмерПоля - 1 Цикл
    Для Колонка = 0 По РазмерПоля - 1 Цикл
        // Смотрим, есть ли в ячейке подсказка
        ЗначениеПодсказки = Подсказки[Строка][Колонка];
        
        Если ЗначениеПодсказки = 0 Тогда
            // Если подсказки нет, создаем переменную с диапазоном допустимых значений 1-9
            ЗначениеЯчейки = Модель.ПеременнаяДиапазона(1, РазмерПоля);
        Иначе
            // Если подсказка есть, создаем константу (фиксированное значение)
            ЗначениеЯчейки = Модель.Константа(ЗначениеПодсказки);
        КонецЕсли;
        
        // Сохраняем созданную переменную или константу в массив
        ЗначенияЯчеек[Строка][Колонка] = ЗначениеЯчейки;
    КонецЦикла;
КонецЦикла;

5. Описание ограничений

Это самый важный этап, на котором мы формализуем правила судоку на языке модели.

Установим ограничение на уникальность в строках:

// Для каждой строки добавляем ограничение: все элементы должны быть разными
Для Строка = 0 По РазмерПоля - 1 Цикл
    Модель.Ограничения().ВсеРазличные(ЗначенияЯчеек[Строка]);
КонецЦикла;

Установим ограничение на уникальность в столбцах. Поскольку наш массив ЗначенияЯчеек организован по строкам, для работы со столбцами мы сначала собирем все переменные одного столбца во временный массив.

// Для каждого столбца...
Для Колонка = 0 По РазмерПоля - 1 Цикл
    // ...создаем массив, содержащий все переменные этого столбца
    КолонкаПеременных = Новый Массив(РазмерПоля);
    Для Строка = 0 По РазмерПоля - 1 Цикл
        КолонкаПеременных[Строка] = ЗначенияЯчеек[Строка][Колонка];
    КонецЦикла;
    // ...и добавляем для этого массива ограничение на уникальность
    Модель.Ограничения().ВсеРазличные(КолонкаПеременных);
КонецЦикла;

Установим ограничение на уникальность в блоках 3x3. Алгоритм чуть сложнее. Мы проходим по всем девяти блокам, для каждого блока собираем все 9 переменных в массив и накладываем ограничение.

// Создаем массив для сбора переменных блока
БлокПеременных = Новый Массив(РазмерБлока * РазмерБлока);

// Цикл по вертикальным блокам (0,1,2)
Для БлокСтрока = 0 По РазмерБлока - 1 Цикл
    // Цикл по горизонтальным блокам (0,1,2)
    Для БлокКолонка = 0 По РазмерБлока - 1 Цикл
        Индекс = 0; // Индекс для заполнения массива БлокПеременных
        
        // Внутренние циклы по ячейкам внутри одного блока 3x3
        Для Строка = БлокСтрока * РазмерБлока По (БлокСтрока + 1) * РазмерБлока - 1 Цикл
            Для Колонка = БлокКолонка * РазмерБлока По (БлокКолонка + 1) * РазмерБлока - 1 Цикл
                // Собираем переменные ячеек блока в массив
                БлокПеременных[Индекс] = ЗначенияЯчеек[Строка][Колонка];
                Индекс = Индекс + 1;
            КонецЦикла;
        КонецЦикла;
        
        // Добавляем ограничение на уникальность для текущего блока
        Модель.Ограничения().ВсеРазличные(БлокПеременных);
    КонецЦикла;
КонецЦикла;

6. Решение модели

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

// Выполняем поиск решения
Решение = Модель.Решить();

В данный задаче отсутсвует целевая функция — мы ищем любое допустимое решение. Модель ограничений без целевой функции — это задача выполнимости (satisfaction). Решатель вернёт либо допустимую конфигурацию, либо сообщит, что решений нет.

7. Вывод результатов

На последнем этапе мы проверяем, было ли найдено решение, и если да, то выводим его в удобочитаемом виде.

// Проверяем статус решения
Если Решение.РешениеНайдено() Тогда
    // Если решение найдено, формируем красивый вывод
    Сообщение = "Решение судоку:" + Символы.ПС + Символы.ПС;
    
    Для Строка = 0 По РазмерПоля - 1 Цикл
        Для Колонка = 0 По РазмерПоля - 1 Цикл
            // Получаем значение переменной из найденного решения
            ЗначениеЯчейки = Решение.ЗначениеПеременной(ЗначенияЯчеек[Строка][Колонка]);
            // Добавляем его в текстовую строку
            Сообщение = Сообщение + Строка(ЗначениеЯчейки);
        КонецЦикла;
        // Переходим на новую строку после вывода каждой строки поля
        Сообщение = Сообщение + Символы.ПС;
    КонецЦикла;
    
    // Показываем результат пользователю
    Сообщить(Сообщение);
Иначе
    // Если решение не найдено (например, головоломка составлена неверно)
    Сообщить("Решение не найдено.");
КонецЕсли;

Полный код решения задачи

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

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Вводим начальные данные
РазмерПоля  = 9;
РазмерБлока = 3;

// Вводим значения подсказок (0 означает пустую ячейку)
Подсказки = Новый Массив(РазмерПоля);

Подсказки[0] = О2.Утилиты().МассивЧиселИзСтроки("5,3,0, 0,7,0, 0,0,0");
Подсказки[1] = О2.Утилиты().МассивЧиселИзСтроки("6,0,0, 1,9,5, 0,0,0");
Подсказки[2] = О2.Утилиты().МассивЧиселИзСтроки("0,9,8, 0,0,0, 0,6,0");

Подсказки[3] = О2.Утилиты().МассивЧиселИзСтроки("8,0,0, 0,6,0, 0,0,3");
Подсказки[4] = О2.Утилиты().МассивЧиселИзСтроки("4,0,0, 8,0,3, 0,0,1");
Подсказки[5] = О2.Утилиты().МассивЧиселИзСтроки("7,0,0, 0,2,0, 0,0,6");

Подсказки[6] = О2.Утилиты().МассивЧиселИзСтроки("0,6,0, 0,0,0, 2,8,0");
Подсказки[7] = О2.Утилиты().МассивЧиселИзСтроки("0,0,0, 4,1,9, 0,0,5");
Подсказки[8] = О2.Утилиты().МассивЧиселИзСтроки("0,0,0, 0,8,0, 0,7,9");

// Создаем двумерный массив для хранения переменных модели, соответствующих ячейкам судоку
ЗначенияЯчеек = Новый Массив(РазмерПоля, РазмерПоля);

// Обходим все ячейки поля
Для Строка = 0 По РазмерПоля - 1 Цикл
    Для Колонка = 0 По РазмерПоля - 1 Цикл
        // Смотрим, есть ли в ячейке подсказка
        ЗначениеПодсказки = Подсказки[Строка][Колонка];
        
        Если ЗначениеПодсказки = 0 Тогда
            // Если подсказки нет, создаем переменную с диапазоном допустимых значений 1-9
            ЗначениеЯчейки = Модель.ПеременнаяДиапазона(1, РазмерПоля);
        Иначе
            // Если подсказка есть, создаем константу (фиксированное значение)
            ЗначениеЯчейки = Модель.Константа(ЗначениеПодсказки);
        КонецЕсли;
        
        // Сохраняем созданную переменную или константу в массив
        ЗначенияЯчеек[Строка][Колонка] = ЗначениеЯчейки;
    КонецЦикла;
КонецЦикла;

// Для каждой строки добавляем ограничение: все элементы должны быть разными
Для Строка = 0 По РазмерПоля - 1 Цикл
    Модель.Ограничения().ВсеРазличные(ЗначенияЯчеек[Строка]);
КонецЦикла;

// Для каждого столбца...
Для Колонка = 0 По РазмерПоля - 1 Цикл
    // ...создаем массив, содержащий все переменные этого столбца
    КолонкаПеременных = Новый Массив(РазмерПоля);
    Для Строка = 0 По РазмерПоля - 1 Цикл
        КолонкаПеременных[Строка] = ЗначенияЯчеек[Строка][Колонка];
    КонецЦикла;
    // ...и добавляем для этого массива ограничение на уникальность
    Модель.Ограничения().ВсеРазличные(КолонкаПеременных);
КонецЦикла;

// Создаем массив для сбора переменных блока
БлокПеременных = Новый Массив(РазмерБлока * РазмерБлока);

// Цикл по вертикальным блокам (0,1,2)
Для БлокСтрока = 0 По РазмерБлока - 1 Цикл
    // Цикл по горизонтальным блокам (0,1,2)
    Для БлокКолонка = 0 По РазмерБлока - 1 Цикл
        Индекс = 0; // Индекс для заполнения массива БлокПеременных
        
        // Внутренние циклы по ячейкам внутри одного блока 3x3
        Для Строка = БлокСтрока * РазмерБлока По (БлокСтрока + 1) * РазмерБлока - 1 Цикл
            Для Колонка = БлокКолонка * РазмерБлока По (БлокКолонка + 1) * РазмерБлока - 1 Цикл
                // Собираем переменные ячеек блока в массив
                БлокПеременных[Индекс] = ЗначенияЯчеек[Строка][Колонка];
                Индекс = Индекс + 1;
            КонецЦикла;
        КонецЦикла;
        
        // Добавляем ограничение на уникальность для текущего блока
        Модель.Ограничения().ВсеРазличные(БлокПеременных);
    КонецЦикла;
КонецЦикла;

// Выполняем поиск решения
Решение = Модель.Решить();

// Проверяем статус решения
Если Решение.РешениеНайдено() Тогда
    // Если решение найдено, формируем красивый вывод
    Сообщение = "Решение судоку:" + Символы.ПС + Символы.ПС;
    
    Для Строка = 0 По РазмерПоля - 1 Цикл
        Для Колонка = 0 По РазмерПоля - 1 Цикл
            // Получаем значение переменной из найденного решения
            ЗначениеЯчейки = Решение.ЗначениеПеременной(ЗначенияЯчеек[Строка][Колонка]);
            // Добавляем его в текстовую строку
            Сообщение = Сообщение + Строка(ЗначениеЯчейки);
        КонецЦикла;
        // Переходим на новую строку после вывода каждой строки поля
        Сообщение = Сообщение + Символы.ПС;
    КонецЦикла;
    
    // Показываем результат пользователю
    Сообщить(Сообщение);
Иначе
    // Если решение не найдено (например, головоломка составлена неверно)
    Сообщить("Решение не найдено.");
КонецЕсли;

  Скачать пример