.NET Разработчик

День сто пятьдесят третий. #ЗаметкиНаПолях

Решатель судоку

По мотивам давнишнего поста 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