Решение судоку с помощью эвристических методов

Август 8, 2022

Главная
Информатика
Решение судоку с помощью эвристических методов

Содержание

2. Постановка задачи Необходимо разработать приложение для решения судоку, которое будет использовать эвристические методы. Основные требования: нахождение
3. Терминология Поле – все поле судоку размером 9х9. Ячейка – клетка, являющаяся частью поля. Строка –
4. Терминология Элемент – группа из 9 ячеек, в которых содержатся различные значения (строка, столбец или блок).
5. Принцип единственной цифры прогноза
6. Принцип единственности цифры в прогнозах элемента
7. Принцип двух ячеек с одинаковым прогнозом
8. Сравнение сложности алгоритмов
9. Ввод условия
10. Некорректный ввод
11. Успешно решенное судоку
12. Некорректное условие
13. Множественные решения
14. Результаты работы Разработано приложение для решения судоку, использующее эвристические методы. Приложение может: решать судоку различных уровней
15. Перспективы развития Пока не реализованные методы: принцип трех ячеек с сопоставимым прогнозом; принцип скрытых пар; принцип
17. Скачать презентацию

Слайд 2

Постановка задачи
Необходимо разработать приложение для решения судоку, которое будет использовать эвристические

методы.
Основные требования:
нахождение правильного решения наиболее эффективными способами;
определение единственности решения для данного условия задачи.

Слайд 3

Терминология
Поле – все поле судоку размером 9х9.
Ячейка – клетка, являющаяся частью

поля.
Строка – горизонтальный ряд длиной в 9 ячеек.
Столбец – вертикальный ряд длиной в 9 ячеек.
Блок – регион размером 3х3, не содержащий одинаковых цифр.

Слайд 4

Терминология
Элемент – группа из 9 ячеек, в которых содержатся различные значения

(строка, столбец или блок).
Прогноз – список возможных значений для конкретной ячейки.
Длина прогноза – количество возможных значений для конкретной ячейки. Для заполненной ячейки длина прогноза равна 1, для пустой – больше 1.

Слайд 5

Принцип единственной цифры прогноза

Слайд 6

Принцип единственности цифры в прогнозах элемента

Слайд 7

Принцип двух ячеек с одинаковым прогнозом

Слайд 8

Сравнение сложности алгоритмов

Слайд 9

Ввод условия

Слайд 10

Некорректный ввод

Слайд 11

Успешно решенное судоку

Слайд 12

Некорректное условие

Слайд 13

Множественные решения

Слайд 14

Результаты работы
Разработано приложение для решения судоку, использующее эвристические методы.
Приложение может:
решать судоку

различных уровней сложности наиболее эффективными методами;
определять, что найденное решение – единственное, или выдавать сообщение об обратном.

Слайд 15

Перспективы развития
Пока не реализованные методы:
принцип трех ячеек с сопоставимым прогнозом;
принцип скрытых

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