↑↑↓↓←→←→ⒷⒶ Войти !bnw Сегодня Клубы

Обнаружен список решений для задачи об N королевах на разных ЯП: http://rosettacode.org/wiki/N-queens_problem Интересно только, как они считают решения. Для больших N там неведомые триллионы решений, уникальных с точностью до поворота или отражения: https://oeis.org/A002562 Поскольку формулы, которая бы давала количество решений от N так никто и не вывел, непонятно, откуда взяли эти цифры. Неужели специально гоняли суперкомпьютер (с невъебенным количеством памяти), чтобы сгенерировать все решения, отфильтровать неуникальные и посчитать? Никакого более простого способа это сделать нигде не нашёл…

Рекомендовали: @corpse
#BCA1HU / @goren / 3899 дней назад

обнаружен жж артемия лебедева
#BCA1HU/54K / @238328 / 3899 дней назад
Хороший вопрос. Я решал её не бэктрекингом а испоьзовал как бенчмарк для своей библиотеки двоичных решающих диаграмм (на racket). Максимальный размер задачи был 10х10, и у меня получиллось как по книге (правда я вские симметрии не учитывал).
#BCA1HU/ZAK / @engineer / 3899 дней назад
@engineer Ты находил одно решение или считал, сколько их всего?
#BCA1HU/NJC / @goren --> #BCA1HU/ZAK / 3899 дней назад
@goren Находил всё. Задавал задачу как предикат от NxN двоичных аргументов и создавал BDD ему соответствующую. При создании дерево упрощается и тривиально решается задача SAT. На выходе я имел набор битвекторов удовлетворяющих предикату.
#BCA1HU/5U0 / @engineer --> #BCA1HU/NJC / 3899 дней назад
@engineer Я ни слова не понял ._.
#BCA1HU/2XJ / @goren --> #BCA1HU/5U0 / 3899 дней назад
@goren но есть же всё в википедии, почитай книги по алгоритмам, научные статьи, не программист чтоле? Как ты хочешь жить в 21 веке без этого? так и будешь всю жизнь — слугой у Технарей
#BCA1HU/5WN / @238328 --> #BCA1HU/2XJ / 3899 дней назад
@goren Вот, я по этой статье делал http://www.itu.dk/courses/AVA/E2005/bdd-eap.pdf Я говорил это к тому что задача тут была просто как бенчмарк, бектрекингом быстрее решается.
#BCA1HU/GOH / @engineer --> #BCA1HU/2XJ / 3899 дней назад
@goren Читай Logic in Computer Science - Modelling and reasosing about systems, chapter 1.6
#BCA1HU/A4G / @ntsm --> #BCA1HU/2XJ / 3899 дней назад
ipv6 ready BnW для ведрофона BnW на Реформале Викивач Котятки

Цоперайт © 2010-2016 @stiletto.