|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 11 Oct 2001 11:52:52
To : Rustam Gadeyev
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
Replying to a message of Rustam Gadeyev to All:
RG> Мне сегодня один товарищ сказал, что когда он был студентом, то его
RG> рекурсивная программа находила все 92 варианта расстановки не бьющих
RG> друг друга ферзей на шахматной доске за 45 минут. Что-то меня задело
RG> такое долгое время счета и где-то за полчаса родил программу, которая
RG> идет ниже в письме. Эти 92 позиции на доске 8х8 без вывода на экран
RG> считаются на P3-450 0.11сек, а 14х14 считаются 22.5сек. Вопрос:
RG> можно ли сделать лучше? :)
С точностью до поворотов и отражений расстановок ферзей на доске 8x8 всего 12
штук. Можно ускорить программу засчет поиска только этих "базовых" расстановок.
А потом для получения всех расстановок достаточно "поповорачивать" и
"поотражать" базовые расстановки.
В частности, определить базовые расстановки для доски nxn определить так:
1) в первой вертикали ферзь стоит на клетке (1,x), причем x<=n/2;
2) в клетках (n,t), (t,1) и (t,n) нет ферзей, если t<x или t>n-x.
Это определение не до конца корректно в том смысле, что есть шанс получить две
базовые расстановки, получающиеся друг из друга поворотами или отражениями. Hо
это легко отследить.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
8 мирных ферзей 
