#моделирование_ограничений — Public Fediverse posts

[Перевод] Решение головоломки NYTimes Pips с помощью решателя ограничений

Кажется, что головоломка NYT Pips — это просто игра с домино и цветными клетками. Но если взглянуть на неё как на задачу удовлетворения ограничений, она превращается в удобный полигон для современных решателей вроде MiniZinc. В статье автор показывает, как описать Pips не в виде алгоритма перебора, а в виде системы ограничений: сетка, домино, суммы по областям, симметрии и «мусорные» решения. По ходу дела выясняется, что войти в мир constraint solving можно буквально за пару часов, а заодно на практике понять, почему эти инструменты умеют разруливать экспоненциальный хаос вариантов за миллисекунды — но иногда внезапно «залипают» на одной и той же головоломке. Читать разбор

https://habr.com/ru/companies/otus/articles/975004/

#решатели_ограничений #MiniZinc #моделирование_ограничений #поиск_решений #бэктрекинг #оптимизация_перебора #головоломки #алгоритмическое_моделирование