Решатель судоку
По мотивам давнишнего поста https://t.me/NetDeveloperDiary/83 решил сделать небольшую библиотеку для решения судоку на C#. Код здесь: https://dev.azure.com/sbenzenko/NetDeveloper/_git/SudokuSolver
Краткое описание
Сетка судоку представляет собой двумерный массив типа
byte. Первоначально заполняется цифрами из задачи судоку, свободные клетки нулями.Решение задачи (метод SolveSudoku):
1) В методе
FindNextCellToFill находим следующую свободную клетку (со значением 0). Если метод возвращает -1, значит свободных клеток нет, задача решена.2) В цикле пробуем записать в клетку цифры от 1 до 9. В методе
IsValid проверяем, не нарушает ли новая цифра правила:- нет одинаковых цифр в текущем секторе 3х3
- нет одинаковых цифр в текущем столбце
- нет одинаковых цифр в текущей строке
3) Если правила не нарушены, рекурсивно вызываем
SolveSudoku (которая выполняет процедуру для следующей пустой клетки). Если
SolveSudoku вернёт true, значит сетка заполнена и задача решена (см. п.1). Выходим из процедуры.В противном случае нужно отменить сделанные изменения:
- устанавливаем значение клетки обратно в
0,- увеличиваем количество «отмен» в переменной
BackTracks (для статистики).4) Если мы прошли по циклу в п.2 и ни одно число не подошло, возвращаем
false, т.е. решений задачи нет.В тестовом проекте (
SudokuSolverTests) есть три примера решений судоку (лёгкого, среднего и «самого сложного известного»). Они же записаны в консольном проекте SolveSudokuConsole от простого к сложному. Можете раскомментировать один из них и посмотреть решение. По количеству выводимых «отмен» (Backtracks) очевидна сложность задачи.Примечания:
- Пока нет визуального UI, возможно сделаю позже.
- Решение можно оптимизировать: выполнять поиск доступных цифр в п.2.
Источник и подробности с решением на Python (на английском языке): https://www.youtube.com/watch?v=auK3PSZoidc