TwiddleLab / Искусственный интеллект / Поиск, игры и планы
Головоломки с ограничениями
Что ты узнаешь
- У задачи с ограничениями есть переменные (кружки, клетки, страны), у каждой область допустимых значений, и ограничения между ними.
- Распространение: каждый выбор убирает варианты у соседей; клетка с одним оставшимся вариантом решена.
- Поиск с возвратом: попробуй значение, иди дальше, а в тупике отмени последний выбор и попробуй следующее значение.
- Расписания, судоку и раскраска карт это головоломки одного вида.
Как идёт урок
Пять кружков, три кабинета, два времени, и все хотят робототехнику. Сможет ли компьютер найти работающее расписание?
Сначала ставка: каждый кружок может попасть в любое из 6 мест. Сколько расписаний пришлось бы перебрать слепому поиску?
Составь расписание кружков. Нарушенные правила сразу подсвечиваются.
Перетащи каждый кружок в кабинет и время. Брось на другой кружок, чтобы поменять их.
Судоку 4 x 4. В каждой пустой клетке видны цифры, которые она ещё может принять.
Нажми на цифру, чтобы поставить её. Смотри, как она исчезает из строки, столбца и блока.
Это задачи с ограничениями.
Каждый кружок, клетка или страна это переменная. Её допустимые значения это её область. Правила это ограничения. Вычёркивать варианты после каждого выбора это распространение. Отменить выбор в тупике и попробовать следующий это поиск с возвратом.
Раскрась карту 3 цветами, как компьютер: попробуй, проверь, отступи.
Соседи (соединённые линией) должны отличаться. «Шаг» или «Пуск».
Поиск застрял. У какой страны не осталось цвета?
Нажми на неё.
D граничит с B, C и F, которые уже заняли жёлтый, синий и красный. У D пустая область: тупик. Поиск должен отменить последний выбор (C) и попробовать что-то другое.
Твой ход: раскрась карту тремя цветами.
В коде это раскраска графа: страны это вершины, границы это рёбра.
Спринт по судоку: реши, сделав не больше 2 ошибок.
Нажми на клетку, потом на число. Варианты можно включить.
Для твоего расписания пришло новое правило. Исправь его.
Двигай кружки, пока ни одно правило не будет нарушено.
Новое правило ограничивает только кабинет шахмат. Время шахмат уже задано Аной и Кэт, поэтому исправление в том, чтобы сменить кабинет в этом же времени. Все остальные кружки могут остаться.
Предыдущий урок: Планирование: от цели к шагам · Следующий урок: Проект: робот-навигатор · Часть курса: Поиск, игры и планы
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
