Конкурс для любителей задач на оптимизацию алгоритмов и программ.

[RXL]

Меня попросили разместить объявление. Ничего плохого или коммерческого там не нашел.

Написал: Zealint.
Почта: flowproblem@mail.ru

Здравствуйте, уважаемые программисты. Предлагаю принять участие в очередном конкурсе для любителей задач на оптимизацию алгоритмов и программ. На этот раз решается задача на перечислительную комбинаторику: сколькими способами можно расположить 6 не бьющих друг друга шахматных ферзей на доске n x n? Месяц назад я вывел общую формулу для 5 ферзей, но для 6 пока не получается. Поэтому для начала хочется выяснить, кто сможет посчитать ответ для максимально возможного значения n. Разрешается использовать любые инструменты и средства программирования. Призовой фонд 3000 р. Подробные правила на моем сайте.

http://zealint.ru/sixqueens-comp.html

[Serg79]

Почитал, что там пишут, интересно. Молодец Zealint, что находит время заниматься организацией таких проектов и, что немаловажно, самому принимать в них активное участие. Одним словом, вызывает уважение.

[Джон]

Ага, а в итоге решается задача для нахождения оптимальных целей самонаводящейся головкой крылатой ракеты.

[RXL]

Попробовал руками в Excel - задачка решается просто:

Алгоритмизация тоже простая: беру матрицу 8х8, ставлю первую королеву в угол и помечаю все клетки, которые она простреливает, после выбираю по спирали следующее свободное угловое место.

Другой вопрос, что по условию нужно много вариантов...

[baldr]

RXL, для "много вариантов", думаю, достаточно будет просто сдвигать это решение с ротацией по горизонтали и вертикали. Ну и покрутить..

[Джон]

Ром, а варианты получаются аналогично. Первый ферзь ставится на А2 (В1) и тд.

Только спрашивается ещё и скорость решения. Те потом такой алгоритм надо оптимизировать.

[RXL]

Тут, IMHO, задачка на перебор вариантов: 64 варианта позиции для первой точки + X оставшихся позиций для второй + Y для третье и т.д., с отвеиванием вариантов, когда все 6 точек разместить не удается. Получается дерево решений.

[baldr]

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

[Джон]

Не, это-то понятно. Метод перебора даст абсолютно все возможные варианты. Более того он абсолютно универсален касаемо размерности доски и количества ферзей. Но будет ли он самым быстрым? Посмотри на сайте "Текущий рейтинг", там приведены результаты с временем.

[Zealint]

Для того, чтобы отыскать частную расстановку, действительно, много усилий не нужно. Сейчас народ умеет делать это для доски миллион на миллион (ставят миллион ферзей) за секунду. Здесь необходимо сказать сколько способов. Причем для доски n x n (где n>5), а не 8 на 8. Посмотрите, пожалуйста, на числа, которые получаются. Для n=28 ответ уже равен 47398421913600. То есть это еще можно посчитать перебором, но дальше числа растут. Чтобы вывести формулу, мне нужно где-то до n=80 посчитать. Тут для начала нужно очень сильно оптимизировать + подключать комбинаторику + параллелить. Вот, кстати, в прошлом конкурсе меня долго пинали, что нельзя использовать CUDA. На этот раз можно, только специалисты по CUDA сразу куда-то делись : )

Полный перебор имеет сложность O(n^12). Это слишком много. Надо как-то понижать порядок. То есть это задача не совсем на тупой перебор. Поэтому я и обращаюсь в большей степени либо к тем, у кого кластер есть, либо к тем, у кого есть опыт в комбинаторике. Что-то подсказывает, что порядок перебора можно сократить до O(n^8). Думаю...

[Алексей++]

ответ уже равен 47398421913600. То есть это еще можно посчитать перебором

ага... прикинем: если рассчитывать по 1000000 решений в СЕКУНДУ, это всё займёт всего лишь полтора годика

[Zealint]

Только спрашивается ещё и скорость решения. Те потом такой алгоритм надо оптимизировать.

Скорость решения мне не важна, я её спрашиваю только ради того, чтобы другие участники могли сверить со своим алгоритмом. Мне нужны только числа - ответы. А считать их можно хоть сутками. Побеждает ведь тот, кто раньше всех даст ответы для максимально возможного n. Кстати, обычный перебор работает дольше суток где-то для n>25. Значит до 30 будет работать как раз до конца конкурса : )

[Dimka]

При тупом переборе количество элементов перебора велико, потому что ферзей мало, а позиций для проверок много.

А никто не пробовал поставить на доску ферзи сразу во всех возможных комбинациях? Интересно, останутся ли при этом незанятые клетки, и если останутся, нельзя ли определять условия их расположения на доске и подойти к задаче с другой стороны? При фиксированном числе ферзей и росте размеров доски таких "дырок" будет всё меньше и меньше.

[Zealint]

ага... прикинем: если рассчитывать по 1000000 решений в СЕКУНДУ, это всё займёт всего лишь полтора годика

Возможно, но программа текущего лидера работает заметно быстрее.

[Алексей++]

Zealint, ну, значит, либо считает 365,25 * 10^6 ходов с секунду, либо не все варианты перебирает. Коли за день справляется

[RXL]

Zealint, если вопрос только в вычислительных ресурсах, то можно было бы использовать boinc, написать генератор заданий, клиентский обработчик и останется только задача привлекать народ.

[Zealint]

Zealint, ну, значит, либо считает 365,25 * 10^6 ходов с секунду, либо не все варианты перебирает. Коли за день справляется

Я об этом и говорю: не надо перебирать все варианты. Надо только сказать их количество. Это гораздо проще (в смысле, быстрее). Мне кажется, что обсуждать что-то в таком ключе сложно и бессмысленно: надо пробовать и смотреть что получается.

Zealint, если вопрос только в вычислительных ресурсах, то можно было бы использовать boinc, написать генератор заданий, клиентский обработчик и останется только задача привлекать народ.

Нет, дело не только в них. Во-первых, если хотите, можете сделать это сами. Это не запрещено по условиям конкурса. Во-вторых, интерес представляет не только решить эту задачу, но и придумать метод её эффективного решения. Чтобы потом атаковать 7 ферзей. Даже если 7 тоже можно решить перебором на мощном кластере, то для 8 вам не хватит суммарной мощности всех машин Планеты. Это не совсем тупая задача, тут есть научных интерес. Просто 6 ферзей - это самая простая задача из огромного класса задач такого рода.

[Zealint]

Конкурс завершён. Всем спасибо. Результаты приводятся здесь: http://zealint.ru/sixqueens-results.html
Удалось вывести явную формулу.

Уже и ссылку то без всяких теорий поставить не можем?  Пришлось поправить.