задача о расстановке ферзей

[erwins]

8 ферзей надо расставить на шахматной доске 8*8 найти количество перестановок. сами перестановки не нужны

интересны ссылки на не переборные решения

[erwins]

просто читал что количество решений нашли для 8*8 аналитически(без перебора) во времена Эйлера

[romanz]

Вам нужны расстановки не атакующих ферзей? Если да, то это известная классическая задача. См. Задачу о восьми ферзях (Википедия)

[erwins]

именно эта задача, но не переборный вариант

[Yu_K]

Может попробовать записать систему равенств и неравенств для переменных булевского типа для неизвестных $x_{i,j}$ - уравнения - это суммы по строкам, столбцам и неравенства - суммы по диагоналям - получится 8+8 уравнений и 30 неравенств для 64 неизвестных. И посмотреть все базисные решения этой системы.

-- Вс дек 05, 2010 13:18:58 --

Может попробовать записать систему равенств и неравенств для переменных булевского типа для неизвестных $x_{i,j}$ - уравнения - это суммы по строкам, столбцам и неравенства - суммы по диагоналям - получится 8+8 уравнений и 30 неравенств для 64 неизвестных. И посмотреть все базисные решения этой системы.

[erwins]

решение сводится к перебору... для 8*8 приемлимо, а вот для больше нет...

просто читал, что для 8*8 задача была решена через "определитель"... что и как не знаю... может кто читал...

[erwins]

нет идей?

[Yu_K]

http://archive.ite.journal.informs.org/ ... ggiero.pdf - здесь система выписана про которую я писал, но ссылка битая на макрос - можете сами попробовать в екселе - но это тоже будет переборное решение в конечном счете. Можно попробовать идею симплекс метода как то притянуть к этой системе - по крайней мере перебор может удастся упорядочить.
http://mathworld.wolfram.com/QueensProblem.html
http://oeis.org/search?q=The%20problem% ... 0&start=10 и
http://oeis.org/A000170 посмотрите ссылки здесь.

Поэкспериментируйте с определителями - посмотрите матрицы из 0 и 1.

Кто бы еще из модераторов падежи поправил в названии топика.

[Yu_K]

Пример решения в Excel

Но если пытаться применить симплекс метод, то что-то слишком горомоздкая получается система - 90 переменных и 42 ограничения. Наверное, лучше бек-трэкинга нечего не придумать.

[Sonic86]

Если записать систему булевых линейных ограничений, то число ее решений найти можно без перебора решений. (перебор в этой формуле своеобразно отражается)
Вот только формулу я Вам не скажу - секрет фирмы .

[erwins]

жаль... просто очень интересно...
можно сделать 2мя уравнениями, но тоже дальще хрен его знает как

-- Ср дек 08, 2010 15:31:20 --

буду благодарен за любые мысли и идеи

-- Ср дек 08, 2010 15:31:42 --

данная задача для меня модельная