японские кроссворды - Самое интересное в блогах

rss_habr

Решение японских кроссвордов с помощью SAT солвера

Воскресенье, 16 Декабря 2018 г. 17:59 (ссылка)

На Хабре было несколько статей по решению японских кроссвордов, где авторы придумывали различные способы как такие кроссворды решать. В комментарии к статье Решение цветных японских кроссвордов со скоростью света я высказал мысль, что, поскольку, решение японских кроссвордов является NP-полной задачей, то и решать их надо с использованием соответствующего инструмента, а именно SAT солвером. Поскольку моя идея была встречена весьма скептически, я решил попробовать ее реализовать и сравнить результаты с другими подходами. Что из этого получилось можно узнать под катом.
Читать дальше ->

https://habr.com/post/433330/?utm_source=habrahabr&utm_medium=rss&utm_campaign=433330