 |
|
|
|
Реализация решения головоломки судоку: подход на основе полного перебора
подход на основе полного перебора Головоломки и игры – логические задачи – удобны для обучения нахождению связей и структур, используемых при таких построениях. В статье приводятся анализ, алгоритм и итоговые программы для решения головоломки судоку. Программирование – сложный процесс, при котором написание программ на отличающихся между собой языках программирования высокого уровня возможно после получения навыков построения алгоритмов. В настоящее время широко известна и популярна числовая головоломка судоку [1]. В соответствии с правилами, игровое поле судоку состоит из 81 одной клетки в форме квадрата со стороной 9 клеток. В свою очередь, игровое поле состоит из 9 малых полей в форме квадрата со стороной 3 клетки и содержащих 9 клеток. В игровых клетках могут встречаться только целые положительные числа 1, 2… 9, при этом клетки, их содержащие, считаются занятыми. При отсутствии числа в клетке она считается свободной. Начальным заполнением игрового поля является некоторая совокупность заполненных клеток, называемая подсказкой. Решением головоломки считается такое заполнение всех свободных в начале клеток указанными выше числами, при котором игровое поле становится латинским квадратом, и малые поля содержат каждое число от 1 до 9 только один раз. (Латинским квадратом n-го порядка является квадратная матрица n-го порядка, заполненная n элементами некоторого множества так, чтобы элементы этого множества встречались только один раз в каждой строке и каждом столбце.) При длительном и многократном процессе решения головоломок судоку может возникать такая ситуация, когда для какой-либо головоломки по какой-либо причине не может быть получено необходимое заполнение. Это может быть связано как с ошибками решающего головоломку, так и с рядом неоднозначностей решения, к которым могут привести неполные илинеудачные подсказки или процесс решения. Одним из подходов является использование для решения таких головоломок программ и программных систем. Представленный алгоритм выполняет решение головоломки судоку методом полного перебора. Реализуется на языках программирования высокого уровня Си, Pascal, Java. Среда разработки для Си – Code::Blocks IDE, Pascal – Vim и транслятор FreePascal (режим совместимости с TP7: -Mtp), Java – Eclipse. Следует учесть, что по ряду причин людьми используются одни методы решения головоломки, а программами – совершенно другие. Человек скорее всего будет использовать интуитивные творческие подходы, которые основаны на его способности находить и выявлять разнообразные взаимосвязанные структуры в игровом поле. При этом попытка ихалгоритмизировать, вполне возможно, будет достаточно трудоемкой. Одним из наиболее простых для алгоритмизации и последующего написания программы, но при этом ресурсоемких (по потребляемой оперативной памяти и процессорному времени результирующего решения) подходов является использование полного перебора, который можно улучшить различными вариациями эвристик, ветвей и границ и прочего. Анализ задачи Имеется игровое поле 9 на 9 клеток, которое после решения должно стать латинским квадратом. Поэтому при выполнении решения необходимо обеспечивать корректный контроль того факта, что в каждой строке и каждом столбце числа от 1 до 9 не повторяются. Далее в каждом из малых квадратов могут встречаться числа от 1 до 9 только один раз. Поэтому на каждом из этапов компьютерного решения задачи необходимо для каждой клетки завести таблицу, в которой будут присутствовать числа, которыми можно заполнить рассматриваемую игровую клетку. Статью целиком читайте в журнале «Системный администратор», №5 за 2015 г. на страницах 85-87. PDF-версию данного номера можно приобрести в нашем магазине.
|
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
