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

  Опросы
1001 и 1 книга  
12.02.2021г.
Просмотров: 11847
Комментарии: 22
Коротко о корпусе. Как выбрать системный блок под конкретные задачи

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

11.02.2021г.
Просмотров: 13182
Комментарии: 13
Василий Севостьянов: «Как безболезненно перейти с одного продукта на другой»

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

20.12.2019г.
Просмотров: 20000
Комментарии: 3
Dr.Web: всё под контролем

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

04.12.2019г.
Просмотров: 16718
Комментарии: 13
Особенности сертификаций по этичному хакингу

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

28.05.2019г.
Просмотров: 17424
Комментарии: 8
Анализ вредоносных программ

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

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

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

Архив номеров / 2015 / Выпуск №5 (150) / Реализация решения головоломки судоку: подход на основе полного перебора

Рубрика: Карьера/Образование /  Пятая пара   | Дополнительные материалы

Кирилл Ткаченко КИРИЛЛ ТКАЧЕНКО, аспирант, кафедра кибернетики и вычислительной техники Севастопольского национального технического университета, 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.

 


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

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

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

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

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