Решение СУДОКУ на платформе "1С:Предприятие 8"
Несколько "странная" статья для этого сайта родилась во время "коротания" свободного вечернего времени в отпуске. Предвидя возможные незанятые ни чем паузы отдыха - лежание на пляже, вечер перед сном, опытный отпускник запасается сборниками кроссвордов и прочей "развлекательно - познавательной лабудой". Так вот, отгадывая очередную табличку судоковской головоломки, подумалось: "а ведь значительно интереснее сочинить программку для разгадывания, чем тупо "вручную" разгадывать..." Для реализации пришлось воспользоваться "текущим рабочим инструментом" - платформой "1С:Предприятие 8.2"
Конфигурация для решения СУДОКУ разработана на релизе платформы 8.2.18.102 в режиме управляемого приложения.
В представленной выгрузке есть несколько примеров с их решениями.
Описание конфигурации
Документ "Игра" - предназначен для ввода в программу исходной таблицы судоку. Табличная часть документа должна содержать девять строк (по числу строк в "кроссворде"). В каждой строке таблицы кроме номера содержится девять реквизитов К1...К9 соответствующих девяти столбцам таблицы судоку.
Реквизиты Комментарий и Сложность - носят чисто справочный характер и на поведение документа не влияют...
При проведении документа заполняется вспомогательный регистр сведений "Исходное поле" и регистр сведений "Поле результат". Это результат "спонтанного" создания программы и никакой надобности в этих регистрах нет :)). В процессе раздумываний над алгоритмом решения и его реализацией пришел к выводу, что эти регистры - ни к чему, но удалять было жаль :).
Документ "Решение" - собственно и реализует решение задачи... Внешне документ - точная копия документа "Игра". Отличается он лишь наличием кнопки "Решить". По этой кнопке, собственно, и запускается решение задачки. В процессе работы алгоритма решения задачи используется регистр сведений "Временное поле". При проведении документа идет заполнение регистра сведений "Поле результат" - но это нигде потом не используется - совсем не нужно, но удалять так же было жаль... ;)
Как это работает
Сначала терпеливо вносим в документ "Игра" таблицу "кроссворда" Судоку. Сохраняем документ (можно и провести...:)
Затем на основании документа "Игра" вводим новый документ "Решение". Он должен заполниться "один-в-один".
Сохраняем документ (хотя на данном этапе это совсем необязательно).
Для решения нажимаем кнопку "Решение" и смотрим как идет процесс в поле сообщений.
Если решение закончилось успешно, то увидим заполненную табличную часть документа.
Если алгоритм с задачей не справился - в поле сообщений увидим "тупиковую" надпись, а в таблице конечный результат...
Результат можно сохранить, записав документ.
Используемый Алгоритм
При разгадывании "загадки" используются два алгоритма:
Первый - для каждой пустой клетки определяются допустимые значения. Проверка ведется по трем признакам - уникальность в строке, в колонке и матрице 3 на 3. Если такое значение единственное, то оно записывается в табличную часть документа "Решение"
Когда возможности первого алгоритма исчерпаны, запускается второй...
Второй - для каждой пустой клетки определяется список допустимых значений. Проверка ведется все по тем же трем признакам. После заполнения списков возможных значений клеток, определяется значение в строке, столбце или матрице, которое встречается только в одном списке в строке, столбце или матрице... (если не понятно, то можно посмотреть программный код в форме документа "Решение")
Пока в результате работы алгоритмов продолжается заполнение таблицы, циклически запускаем их снова... Как только заполнение прекратилось, цикл прерывается...
Проблемы...
В отпуске было несколько книжек с кроссвордами - все "судоки" из них успешно решались программой. Но в третьей книге встретились такие таблицы, что программа не смогла их решить до конца (пример в документе номер 11 от 03.09.2013). Действительно, кто-то так замудрил задачку, что кроме перебора, вариантов для решения - не остается! Но такой алгоритм неинтересен (на мой взгляд) для программиста...