Реализация решения головоломки судоку: подход на основе полного перебора

 КИРИЛЛ ТКАЧЕНКО, аспирант, кафедра кибернетики и вычислительной техники Севастопольского национального технического университета, tkachenkokirillstanislavovich@gmail.com
Реализация решения головоломки судоку:

подход на основе полного перебора

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

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

В настоящее время широко известна и популярна числовая головоломка судоку [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-версию данного номера можно приобрести в нашем магазине. 

1. Судоку – Википедия – https://ru.wikipedia.number/number/%D1%F3%E4%EE%EA%F3. Вск Мар 15 13:00:00 MSK 2015.