Программа для решения СУДОКУ, выдающая все возможные варианты решения
Для тех, кто не знаком с Судоку читать дальше не имеет смысла.
Для тех, кто увлекается Судоку, но не интересуется программированием, целесообразно скачать программу
и использовать ее по прямому назначению.
А для программистов, может быть, будет интересно проанализировать алгоритм решения…
Это не студенческое задание.
Так, из спортивного интереса, я когда-то написал программку для решения этой японской головоломки на VBA (Excel).
Целью было - просто проверять, имеется ли решение для данного варианта конкретной Судоку.
Поэтому и решал методом простого перебора с проверкой истинности условий по всем 18 линиям и 9 квадратикам.
Конечно, не рационально и долго.
Почти целую минуту…
Хотя для человека это недостижимый результат…
Кого интересует код на VBA (Excel) – скачать xls-файл…
Этим же файлом могут воспользоваться те, у кого не установлена .NET Framework 4. Только макросы включать не забывайте.
От жалости к компьютеру (его не рациональному труду) и зародилась мысль,
решить задачу не методом сплошного перебора, а логично…
Т.е. присваивать одно из альтернативных значений клетке только в том случае,
если по методу исключений уже невозможно определить значение ни для одной из ячеек.
Павел Жигулин – студент и талантливый программист, взялся за реализацию такой
программы на своем любимом языке C# (Visual Studio 2010, необходима .NET Framework 4).
Предметную область мы обсуждали и разрабатывали вместе.
На мой взгляд, задача оказалась менее заковыристой, чем казалась на первый взгляд
(но не знаю, как Павел на это дело смотрит).
Минимум классов предметной области:
- Доступность
- Клетка
- Регион
- ход
в конкретный момент решения (на определенном ходе) обладают определенной доступностью – набором цифр, которые еще не использовались в этом регионе.
А ход представляет собой объект, который в начальный период присваивает одной единственной клетке альтернативное значение, а затем выполняет цепочку необратимых изменений, которые повлекло за собой это первое присвоение.
Сколько клеток получат свое значение на одном ходе – дело конкретного случая.
Сколько будет ходов всего – дело конкретного случая.
Но если алгоритм на определенном ходу заходит в тупик, то производится «откат» с очисткой
всех ячеек измененных на этом ходу.
Программа работает практически мгновенно. При условии, что Судоку реальное
(т.е. не менее 20 клеток на начальный момент заполнено)…
Если заданы значения одной или двух клеток, то вариант может быть и не предсказуемым…
Например: «решение не найдено», но над этим мы еще поработаем.
Кроме того, программа позволяет при первом найденном решении, продолжить поиск и будет
останавливаться при каждом следующем найденном решении, услужливо спрашивая пользователя: «Продолжить? Или уже достаточно?».
Скачивайте и тестируйте
программу,
Другие примеры на тему «Компьютерные игры (учебные, простенькие)»
Другие примеры на языках «C»,«C++»,«C#»
Можно достаточно легко переделать программу на составление (генерацию) судоку...
Поделиться в соц сетях:
