Задача о расстановке ферзей, известная всем шахматистам и математикам-прикладникам, имеет давние корни. Вот, например, одна из версий (http://golovolomka.hobby.ru/books/gik/04.shtml)
Одной из самых знаменитых математических задач на шахматной доске, наряду с задачей о ходе коня, является задача о восьми ферзях. Если задачей о ходе коня занимался великий математик Леонард Эйлер, то задача о восьми ферзях привлекала внимание другого великого математика — Карла Гаусса. Сколькими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т. е. никакие два не стояли на одной вертикали, горизонтали и диагонали? Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко. Значительно труднее подсчитать общее число расстановок, в чем, собственно, и состоит задача.
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете “Illustrierte Zeitung” от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей) .
Так вот, та самая "гораздо более интересная" задача об отыскании количества решений для произвольного размера доски (NxN) решена на настоящий момент всего лишь.. .для N=26! (http://en.wikipedia.org/wiki/Eight_queens_puzzle) На это потребовалось около полугода вычислений на кластере с приблизительно 300-ми мощными машинами.. .
Кроме того известно, что для получения решения для следующего номера N, нужно в N/2 раз увеличить мощность вычислительной сети. То есть для получения числа всех возможных решений для N=27, нужно либо считать 6,75 лет, либо использовать 4050 машин.. .
Скептикам: эта задача имеет важное прикладное значение (к ней сводится задача о коммивояжере, с ее помощью вычисляют оптимальное рапределение памяти, она помогает избегать дедлоков в базах данных и проч. , и проч.) .
А теперь внимание, вопрос: в этом контексте увеличение количества ядер с одного до двух (четырех, восьми... ) что-либо даст? Ну допустим, мы сможем посчитать для доски 27 на 27, но 28 на 28 нам уже не преодолеть.. .Давайте нарастим еще ядер :)
Отсюда можно сделать один вывод: на "прогресс" в области IT следует смотреть со здоровым скептицизмом.
Другие языки программирования и технологии
Сколькими способами можно расставить N ферзей на шахматной доске NxN так, чтобы они не угрожали друг-другу? комбинаторно
8 ферзей. ещё в 7 классе эту задачку решали.
что за 8 ферзей в первом ответе? к чему это вообще... в 7 классе решал... как из данных, которые дали в условии ты получил 8?
Похожие вопросы
- Дана шахматная доска размером 8 х 8. Определить цвет клетки с заданными координатами.
- Есть шахматная доска, на ней расположен кароль и три ладьи,
- Объявление массива С++. С клавиатуры вводится число n, потом надо задать массив nxn. Как это сделать?
- Задача ферзей. Pascal abc
- Нужно создать цепочку из N каталогов, вложенных друг в друга.
- Вводится число N, а затем N чисел. Подсчитайте, сколько среди данных N чисел нулей.
- Задача о восьми ферзях
- C++ Вывести сколько выпил каждый из друзей в литрах, сколько выпито всего и ...
- Даны натуральные числа N и A1,…, AN. Образовать новые одномерные последовательности B1, …, BN и C1, …, CN
- Вычислить произведение n>=2 (n четное) сомножителей y=(2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7)*..