Задача о 8 ферзях
Автор Леон задал вопрос в разделе Прочие развлечения
Как за 1 млн $ расставить на шахматной доске 8 ферзей таким образом, чтобы ни один из них не попадал под удар другого? и получил лучший ответ
Ответ от Dos Horner[гуру]
Задача о том, как расставить восемь ферзей на шахматной доске так, чтобы они не били друг друга, является классической головоломкой. Никакого миллиона долларов за её решение не предложат, поскольку все варианты давно найдены и изучены. Всего на стандартной доске существует ровно 92 таких расположения. Если считать все возможные способы разместить 8 фигур на 64 клетках без ограничений, их будет 4 426 165 368. Однако задачу можно существенно упростить. Поскольку два ферзя не могут стоять на одной горизонтали или вертикали, достаточно рассматривать только перестановки, где на каждой линии находится по одной фигуре. Это сокращает число вариантов до 40 320. Современные компьютеры находят все решения мгновенно с помощью алгоритма поиска с возвратом, который проверяет угрозы по диагоналям прямо в процессе генерации позиций, делая перебор максимально быстрым.
Гони мой миллион баксов
Так это уже давно известно! Таких позиций больше 80..Задача не стоит миллиона!
Хорошо у них ученые живут, миллионами бросаются !
Не восемь, а тысячу. И проблема не в расстановке, а в том, что подобные задачи решаются только методом перебора, а вопрос стоит в поиске эффективного алгоритма.
Давай миллион, расставлю
Можно и рублей
За баллом
Не знаю
Эта задача решена ещё в XIX веке, поэтому 1 млн на совсем других условиях
Эта задачка лёгкая! Я такие в первом классе решал!
Нужно внимательнее быть и не давать спуску противнику
Ха-ха-ха! Я лучше сам автора отвечу! Чтобы моё решение НЕ УКРАЛИ!
Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4 426 165 368 (= 64!/(8!(64-8)!)). Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16 777 216 (то есть 88) вместо 4 426 165 368. Генерируя перестановки, которые являются решениями задачи о восьми ладьях и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40 320 (то есть 8!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.
возможно, но не утверждаю
Всё будет хорошо..
Вот спрашивается, а зачем это искать? Какой практический смысл в этом?
Хоть на умных людей поглядела))
8-7 минут минимум.
Подписывался на меня и задай любой вопрос! Только если полпиман!
Никак
см. ссылка
Задача о 8 ферзях. паскаль
Забей все значения статически, чтобы каждый раз их не пересчитывать, и просто меняй их при нажатии
подробнее...
На что в древней Индии играли в шахматы?
Шахматы
В Древней Индии войско состояло из пехоты, конницы, колесниц и слонов. Но
подробнее...
Когда шахматные фигуры получили свои названия?
Истинный возраст игры, известной в западном мире как Шахматы, покрыт мраком тайны. Некоторые
подробнее...
Какая шахматная фигура появилась самой последней? Кто и при каких обстоятельствах её придумал? (красивая легенда)
Средневековый шахматист и поэт писал:
Кто мы? Не те же ль самые фигуры?
Мечась меж
подробнее...