Програмная реализация нахождения решения головоломки «Судоку» в 1С

 КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат., ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Программная реализация
нахождения решения головоломки «Судоку» в 1С

Рассматривается программная система для нахождения решения головоломки «Судоку» средствами языка программирования 1С. Разработанный модуль управляемого приложения выполняет поиск решения рекурсивным способом. Укрепим знания разработчика по типовым структурам данных и управляющим конструкциям

Наилучшие результаты в области творчества почти получаются, когда «автор… не был связан маркетинговыми и рекламными обязательствами… Ему ничего и никому не надо было доказывать. Он был волен использовать то, что ему нравилось…» [1].

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

Одной их таких головоломок является широко известная «Судоку». Эта головоломка имеет богатое прошлое, пользуется чрезвычайной популярностью, выходят тематические газеты и журналы, поддерживаются и развиваются онлайн-ресурсы, ей посвященные. Решение варианта головоломки любой сложности человеком может в некоторых случаях потребовать «опорных» решений или, говоря другими словами, подсказок. Их обеспечивают специально разработанные для получения этого программные системы.

Распространенные программы для решения этой головоломки либо поставляются с закрытым исходным кодом, либо их исходные коды слишком трудоемки для того, чтобы сходу понять происходящие в процессе решения действия.

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

Вследствие того, что на предприятиях и в организациях востребована среда 1С, стоит вести разработку именно на этой платформе, доступной для многих специалистов в ИТ-области, программистов и непрограммистов. Существуют программные реализации и на других языках программирования [2].

Целью настоящей публикации является иллюстративная разработка достаточно простой программы на языке 1С для попытки получения решения головоломки «Судоку».

Программа и подпрограмма инициализации

Так же как и во многих других подобных случаях, вся программа целиком помещается в модуль управляемого приложения заведомо пустой конфигурации. Описание ее целесообразно осуществлять путем комментированного приведения строк полученного исходного текста, поскольку этот способ часто применяется в современной обучающей литературе для специалистов.

Объявляются используемые несколькими подпрограммами модуля переменные и константы:

Перем N, КодСимволаНоль, Судоку, СчЗамен, ИсхДанные;

В константе N будет хранится длина стороны поля, равная 9, в КодСимволаНоль – код нуля. В переменной Судоку – все поле для головоломки, СчЗамен – количество произведенных замен, ИсхДанные – входные данные дляфункционирования.

Процедура ИнициализацияКонстант() инициализирует константы:

Процедура ИнициализацияКонстант()

    N = 9;

    КодСимволаНоль = КодСимвола("0");

КонецПроцедуры

В N присваивается 9, в КодСимволаНоль – код нуля.

Процедура ИнициализацияПеременных() инициализирует переменные:

Процедура ИнициализацияПеременных()

    Судоку = Новый Массив(N, N);

    ИсхДанные = Новый Массив();

    ИсхДанные.Добавить("000006201");

    ИсхДанные.Добавить("070510060");

    ИсхДанные.Добавить("006080059");

    ИсхДанные.Добавить("120000000");

    ИсхДанные.Добавить("080940500");

    ИсхДанные.Добавить("590000000");

    ИсхДанные.Добавить("001050073");

    ИсхДанные.Добавить("030460080");

    ИсхДанные.Добавить("000003604");

    СчЗамен = 0;

КонецПроцедуры

В Судоку помещается пустой массив 9 на 9, ИсхДанные – 9 строк по 9 символов входных данных (упрощенное хранение малого количества входных данных), СчЗамен – 0.

Подпрограммы получения исходных данных и вывода поля

Для вывода поля на экран служит процедура ПечатьСудоку():

Процедура ПечатьСудоку()

    Перем Рез, ТекСтрок, ТекСтолб;

    Рез = "+---+---+---+"

"";

    Для ТекСтрок = 0 По N - 1 Цикл

        Для ТекСтолб = 0 По N - 1 Цикл

            Если ТекСтолб % 3 = 0 Тогда

                Рез = Рез + "|";

            КонецЕсли;

            Рез = Рез + Символ(Судоку[ТекСтрок][ТекСтолб] + КодСимволаНоль);

        КонецЦикла;

        Рез = Рез + "|"

"";

        Если ТекСтрок % 3 = 2 Тогда

            Рез = Рез + "+---+---+---+"

"";

        КонецЕсли;

    КонецЦикла;

    Рез = Рез + ""

"";

    Сообщить(Рез);

КонецПроцедуры

Эта процедура выводит содержимое поля головоломки. Используются три переменные: Рез, ТекСтрок, ТекСтолб.

В переменной Рез находится результат, текстовая строка, разбитая на отдельные строки терминаторами. Здесь и далее переменная ТекСтрок содержит номер рассматриваемой в настоящее время строки, а ТекСтолб – соответственно столбца.

Построчно, а затем постолбцово рассматриваются данные ячеек игрового поля. Содержимое ячейки поля преобразуется в десятичную цифру, когда к ней добавляется код нуля, а затем полученная величина преобразуется в символ по коду. Вконце каждой строки добавляется вертикальная черта с терминатором. Если номер столбца делится на 3 без остатка, то добавляется вертикальная черта. Если номер строки делится на 3 с остатком 2, то есть после каждой третьей строки, торезультат конкатенируется с «+---+---+---+» и терминатором.

Преобразование входных данных во внутреннее представление производится процедурой СтрокиВСудоку():

Процедура СтрокиВСудоку()

    Перем ТекСтрок, ТекСтолб;

    Для ТекСтрок = 0 По N - 1 Цикл

        Для ТекСтолб = 0 По N - 1 Цикл

            Судоку[ТекСтрок][ТекСтолб] = КодСимвола(ИсхДанные[ТекСтрок], ТекСтолб + 1) - КодСимволаНоль;

        КонецЦикла;

    КонецЦикла;

КонецПроцедуры

В рамках этой процедуры решается другая несложная задача – ввод из исходных данных начального состояния поля. Используются две переменные: ТекСтрок, ТекСтолб, с определенным ранее функциональным назначением.

По строкам и по столбцам клетке поля присваивается цифра, которая должна там содержаться: для этого от кода символа в исходных данных отнимается код нуля.

Подпрограмма поиска решения

Поиск решения осуществляется в рекурсивной функции Решить():

Функция Решить()

...

    Возврат Ложь;

КонецФункции

Эта функция возвращает ложь, если решение не было найдено.

Объявляются переменные:

    Перем ЦифраВСудоку;

    Перем НСтроки, НСтолбца;

    Перем НетНулей;

    Перем ТекСтрок, ТекСтолб, ТекЦифра;

    Перем НачСтрок, НачСтолб, КонСтрок, КонСтолб;

В одномерном массиве ЦифраВСудоку хранится вектор флажков, отмечающих встречу с цифры на поле, чтобы избежать ее повторного использования.

В индексных переменных НСтроки и НСтолбца находится номер найденного нуля.

Во флажке НетНулей отмечается факт его ненахождения.

Номер текущих рассматриваемых строки и столбца располагаются в ТекСтрок и ТекСтолб соответственно, а десятичной цифры – в ТекЦифра.

Граничные индексы заполнения поля для строк – НачСтрок и КонСтрок, столбцов – НачСтолб и КонСтолб.

Присваивается начальное значение:

    ЦифраВСудоку = Новый Массив(10);

    НСтроки = 0;

    НСтолбца = 0;

    НетНулей = Истина;

Новый массив в ЦифраВСудоку, начальные нули – в НСтроки, НСтолбца, отсутствие нулей на поле НетНулей – Истина.

Ищется первый сверху и слева нуль:

    ТекСтрок = 0;

    Пока НетНулей И (ТекСтрок < N) Цикл

        ТекСтолб = 0;

        Пока НетНулей И (ТекСтолб < N) Цикл

        Если Судоку[ТекСтрок][ТекСтолб] = 0 Тогда

                НетНулей = Ложь;

                НСтроки = ТекСтрок;

                НСтолбца = ТекСтолб;

            КонецЕсли;

            ТекСтолб = ТекСтолб + 1;

        КонецЦикла;

        ТекСтрок = ТекСтрок + 1;

    КонецЦикла;

Поиск выполняется типовым алгоритмом для двумерного массива с ограничениями на первый найденный элемент. Перед внешним циклом с предусловием счетчику ТекСтрок присваивается 0. Предусловием является одновременная истинность: отсутствие нулей на поле и выхода за границу поля по строкам. Выполняется тело цикла, в конце происходит увеличение счетчика ТекСтрок. В теле цикла для внутреннего цикла с предусловием счетчику ТекСтолб присваивается 0. Предусловием внутреннего цикла является одновременная истинность: отсутствие нулей на поле и выхода за границу поля по столбцам. Выполняется тело внутреннего цикла, в конце происходит увеличение счетчика ТекСтолб. В теле внутреннего цикла проверяется условие равенства ячейки поля нулю. При его выполнении фиксируются столбец и строка найденной ячейки и факт наличия нулей.

    Если НетНулей Тогда

        Возврат Истина;

    КонецЕсли;

В случае ненахождения нулевого элемента головоломка считается успешно решенной.

Считается, что ни одна из цифр не повторяется:

    Для ТекЦифра = 0 По 9 Цикл

        ЦифраВСудоку[ТекЦифра] = Ложь;

    КонецЦикла;

Границы для заполнения цифрами соответствуют квадрату 3 на 3, в котором находится найденный нулевой элемент:

    НачСтрок = Цел(НСтроки / 3) * 3;

    НачСтолб = Цел(НСтолбца / 3) * 3;

    КонСтрок = НачСтрок + 3;

    КонСтолб = НачСтолб + 3;

Начальные границы всегда кратны трем. Для этого выполняется целочисленное деление соответствующей строки и столбца на 3 с последующим умножением на 3. Конечные границы больше начальных на 3.

Все имеющиеся в «кресте» для этого элемента цифры отмечаются как присутствующие:

    Для ТекСтрок = 0 По N - 1 Цикл

        ЦифраВСудоку[Судоку[НСтроки][ТекСтрок]] = Истина;

        ЦифраВСудоку[Судоку[ТекСтрок][НСтолбца]] = Истина;

    КонецЦикла;

В цикле со счетчиком для всех ячеек, у которых номер строки соответствует номеру строки нулевой ячейки или номер столбца – столбцу нулевой ячейки.

А также все имеющиеся в квадрате этого элемента цифры отмечаются как присутствующие:

    Для ТекСтрок = НачСтрок По КонСтрок - 1 Цикл

        Для ТекСтолб = НачСтолб По КонСтолб - 1 Цикл

            ЦифраВСудоку[Судоку[ТекСтрок][ТекСтолб]] = Истина;

        КонецЦикла;

    КонецЦикла;

То есть для всех ячеек, строки которых имеют номера НачСтрок, …, КонСтрок – 1 и столбцы – номера НачСтолб, …, КонСтолб – 1, содержащиеся в этих ячейках цифры отмечаются как присутствующие.

Для каждой возможной десятичной цифры:

    Для ТекЦифра = 1 По 9 Цикл

        Если Не ЦифраВСудоку[ТекЦифра] Тогда

            СчЗамен = СчЗамен + 1;

            Судоку[НСтроки][НСтолбца] = ТекЦифра;

            Если Решить() Тогда

                Возврат Истина;

            КонецЕсли;

            Судоку[НСтроки][НСтолбца] = 0;

        КонецЕсли;

    КонецЦикла;

Если она не использована, то увеличивается счетчик изменений поля, затем эта цифра присваивается нулевому элементу. В случае успешного рекурсивного запуска решения возвращается Истина. Иначе элементу возвращается нулевое значение, и процесс повторяется.

Подпрограмма запуска

Головная процедура Главная() выполняет запуск :

Процедура Главная()

    ИнициализацияКонстант();

    ИнициализацияПеременных();

    СтрокиВСудоку();

    ПечатьСудоку();

    Сообщить("");

    Решить();

    ПечатьСудоку();

    Сообщить("");

    Сообщить("Число замен: " + СчЗамен);

    Сообщить("");

КонецПроцедуры

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

Точка входа достаточно проста: Главная();.

Полный исходный код и результаты работы на сайте журнала http://samag.ru.

Рисунок 1. Результаты работы программы

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

1. Вторников А. Философский камень программирования: язык С. // «Системный администратор», № 1-2, 2017 г. – С. 75-79. URL: http://samag.ru/archive/article/3366.
2. Ткаченко К. Реализация решения головоломки судоку: подход на основе полного перебора. // «Системный администратор», № 5, 2015 г. – С. 85–87. URL: http://samag.ru/archive/article/2954.

Комментарии могут оставлять только зарегистрированные пользователи