TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Решатель судоку
Что ты узнаешь
- Ограничение это правило, которое должен соблюдать любой ответ: ни одна цифра дважды в строке, столбце или блоке.
- Проверка ограничений вроде is_ok проверяет один ход по правилам, прежде чем его сделать.
- Решатель это поиск с возвратом: поставь цифру, которая проходит проверку, иди глубже, отменяй в тупике.
- Если сначала выбирать самую ограниченную клетку (меньше всего вариантов), попыток становится намного меньше. Расписания решают так же.
Как идёт урок
Любое газетное судоку можно взломать короткой программой. Сначала попробуй маленькое.
Цифры от 1 до 4: по разу в каждой строке, каждом столбце и каждом блоке 2 x 2.
Сколько попыток понадобится решателю на этой доске?
Он пробует 1, 2, 3, 4 в каждой пустой клетке, в порядке чтения. Считается каждая проверенная цифра.
Смотри на решатель: попробуй, проверь, иди глубже, отмени.
Красный это столкновение. Когда не подходит ни одна цифра, он отступает и меняет более раннюю.
Каждая пустая клетка это рекурсивный вызов. Он пробует цифры по порядку; цифра, прошедшая проверку, ставится, и начинается следующий вызов. Если более поздний вызов не находит ни одной цифры, он возвращает False, и этот вызов отменяет свою цифру и пробует следующую.
Ограничения и проверка ограничений.
Ограничение это правило, которое должен соблюдать ответ. В судоку их три: каждая цифра по разу в строке, по разу в столбце, по разу в блоке.
Проверка ограничений проверяет один ход: is_ok(board, r, c, d) говорит, может ли цифра d прямо сейчас стоять в строке r, столбце c.
Решатель это поиск с возвратом с проверкой: попробуй цифру, оставь её, только если is_ok говорит True, отмени, когда поиск ниже провалился.
Побудь is_ok. Что мешает фиолетовой цифре?
Нажми на каждую клетку, которая мешает, или на «Подходит», если ничего не мешает.
Классика, часть 1: напиши is_ok(board, r, c, d).
Проверь строку и столбец одним циклом, потом блок 2 x 2. Любое совпадение значит False.
Любого столкновения достаточно, чтобы отвергнуть цифру, поэтому каждая проверка может сразу вернуть False. Вернуть True функция может, только когда ни один цикл не нашёл цифру, поэтому эта строка идёт последней.
Классика, часть 2: напиши solve().
Найди первую пустую клетку, пробуй от 1 до 4 с is_ok, иди глубже, отменяй, если не вышло. Если пустых клеток не осталось, значит, решено.
return False стоит после цикла по цифрам, всё ещё внутри ветки пустой клетки: она срабатывает, только когда все четыре цифры не подошли. return True в самом конце срабатывает, только когда циклы не нашли пустой клетки, то есть доска заполнена.
Классика, часть 3: твой решатель на доске, решённой вручную.
Твоя is_ok и твоя solve. Нажми «Запуск».
Испытание: газетное судоку 9 x 9. Какой порядок требует меньше попыток?
Тот же поиск с возвратом, два способа выбрать следующую клетку. Нажми на один, потом «Проверить».
Порядок чтения часто начинает с клетки, где подходит много цифр, и неверная догадка обнаруживается лишь многими уровнями глубже. Если сначала заполнять самую ограниченную клетку, неверных догадок меньше, и отменять приходится меньше.
Та же идея, настоящая задача: расписание экзаменов.
Шесть экзаменов, три времени. Экзамены с общими учениками не могут быть одновременно. Отменяй в тупике.
Где решатель застрянет?
В одной пустой клетке не подходит ни одна цифра. Нажми на неё, потом «Проверить».
Клетка становится тупиком, когда каждая из 1, 2, 3 и 4 уже есть в её строке, столбце или блоке. Решатель узнаёт это по четырём неудачным проверкам, потом отступает.
Усложни, потом дай своему решателю взломать.
Убери данные цифры, потом нажми «Взломать». Карточка покажет, сколько понадобилось попыток.
Предыдущий урок: Перебор с возвратом: проходим лабиринт · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
