Програмная реализация нахождения решения головоломки «Судоку» в 1С::Журнал СА 11.2017
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Подписка
Архив номеров
Где купить
Наука и технологии
Авторам
Рекламодателям
Контакты
   

  Опросы
  Статьи

День сисадмина  

Учите матчасть! Или как стать системным администратором

Лето – время не только отпусков, но и хорошая возможность определиться с профессией

 Читать далее...

День сисадмина  

Живой айтишник – это всегда движение. Остановка смерти подобна

Наши авторы рассказывают о своем опыте и дают советы начинающим системным администраторам.

 Читать далее...

Виртуализация  

Рынок решений для виртуализации

По данным «Обзора российского рынка инфраструктурного ПО и перспектив его развития», сделанного

 Читать далее...

Книжная полка  

Как стать креативным и востребованным

Издательский дом «Питер» предлагает новинки компьютерной литературы, а также книги по бизнесу

 Читать далее...

Книжная полка  

От создания сайтов до разработки и реализации API

В издательстве «БХВ» недавно вышли книги, которые будут интересны системным администраторам, создателям

 Читать далее...

Разбор полетов  

Ошибок опыт трудный

Как часто мы легко повторяем, что не надо бояться совершать ошибки, мол,

 Читать далее...

Принципы проектирования  

Dependency Inversion Principle. Принцип инверсии зависимостей в разработке

Мы подошли к последнему принципу проектирования приложений из серии SOLID – Dependency

 Читать далее...

Рынок труда  

Вакансия: Администратор 1С

Администратор 1С – это специалист, который необходим любой организации, где установлены программы

 Читать далее...

Книжная полка  

Книги для профессионалов, студентов и пользователей

Книги издательства «БХВ» вышли книги для тех, кто хочет овладеть самыми востребованными

 Читать далее...

Принципы проектирования  

Interface Segregation Principle. Принцип разделения интерфейсов в проектировании приложений

Эта статья из серии «SOLID» посвящена четвертому принципу проектирования приложений – Interface

 Читать далее...

1001 и 1 книга  
19.03.2018г.
Просмотров: 10720
Комментарии: 0
Потоковая обработка данных

 Читать далее...

19.03.2018г.
Просмотров: 8970
Комментарии: 0
Релевантный поиск с использованием Elasticsearch и Solr

 Читать далее...

19.03.2018г.
Просмотров: 9006
Комментарии: 0
Конкурентное программирование на SCALA

 Читать далее...

19.03.2018г.
Просмотров: 5683
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

 Читать далее...

12.03.2018г.
Просмотров: 6375
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

 Читать далее...

12.03.2018г.
Просмотров: 3678
Комментарии: 0
Глубокое обучение с точки зрения практика

 Читать далее...

12.03.2018г.
Просмотров: 2682
Комментарии: 0
Изучаем pandas

 Читать далее...

12.03.2018г.
Просмотров: 3479
Комментарии: 0
Программирование на языке Rust (Цветное издание)

 Читать далее...

19.12.2017г.
Просмотров: 3473
Комментарии: 0
Глубокое обучение

 Читать далее...

19.12.2017г.
Просмотров: 5966
Комментарии: 0
Анализ социальных медиа на Python

 Читать далее...

Друзья сайта  

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

Архив номеров / 2017 / Выпуск №11 (180) / Програмная реализация нахождения решения головоломки «Судоку» в 1С

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

Комментарии отсутствуют

Добавить комментарий

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

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru