Рубрика «np-complete»

EricGrig

Предисловие

Я хотел бы начать предисловие со слов благодарности двум замечательным программистам из Одессы: Андрею Киперу (Lohica) и Тимуру Гиоргадзе (Luxoft), за независимую проверку полученных мною результатов, на начальном этапе исследования.

1. Статья «Linear algorithm for solution n-Queens Completion Problem» была опубликована в (arXiv.org) в начале первого дня 2020 года. Изначально статья была написана на русском, поэтому здесь представлено базовое изложение, а там — перевод.

2. Данная задача, и некоторые другие из множества NP-Complete (задача выполнимости булевых формул (3-SAT), задача о поиске максимальной клики, или клики заданного размера …) в разное время, входили в сферу моих интересов. Я искал алгоритмическое решение на основе различных вычислительных экспериментов, но конкретного успеха не было. Это было похоже на то, как человек пытается научиться подтянутся на турнике на одной руке. Результата нет, но каждый раз появляется надежда, что скоро все получится. Последний раз я решил, что следует подольше остановиться на задаче n-Queens Completion (как одной из представителей семейства) и попытаться что-то сделать. Здесь уместно вспомнить замечательный Одесский анекдот: «В переполненном автобусе, который вечером по ухабистой дороге возвращается в пригород, раздается голос женщины – Мужчина, если уж полностью на меня легли, так сделайте хоть что-нибудь».

3. Исследование длилось достаточно долго – почти полтора года. С одной стороны, это связано с тем, что в процессе исследования, рассматривались и другие задачи, с другой – по ходу решения были сложные вопросы, без ответа на которые не удалось бы идти вперед. Перечислю некоторые из них:

— в матрице решения n строк, в какой последовательности следует выбирать индекс строки, если число возможностей для такого выбора составляет n!
Читать полностью »

Привет!

В данном посте речь пойдет о моем участии в конкурсе Ludum Dare 34, который был около трех недель назад.

В результате получился пазл под названием Growing Sakura, геймплей которой можно видеть на гифке (не пугайтесь, она весит всего 300Кб):

О сложности выращивания сакуры: как я участвовал в Ludum Dare 34 - 1

Кратко о правилах игры: изначально у нас есть гексагональное поле и несколько корневых бутонов (или один, как на гифке выше). Из него можно пустить 3 ветки (двумя способами — кликая левой или правой кнопкой мыши). Из каждого бутона на ветке левым кликом мыши можно сделать Y-разветвление, а правым — просто продолжить ветку дальше (I-разветвление). Если в каком либо направлении ветка расти не может (соответствующая клетка занята или в нужном направлении нет клетки) — то ветка не растет. В соответствии с последним условием нужно правильно выбирать порядкок «разворачивания» веток. В итоге получится дерево (или несколько деревьев) такое, что между двумя смежными ветками нет острых углов. Цель игры — покрыть все клетки игрового поля.

Не заглядывая под кат попробуйте подумать секунд 10 и прикинуть, насколько сложной может быть эта игра.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js