ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Egorov Pavel                         2:5080/169.35  18 Feb 2002  00:26:48
 To : Yasha Davidov
 Subject : 8 ферзей
 -------------------------------------------------------------------------------- 
 

 
  Как-то раз Yasha Davidov писал All следующее:
 
  YD> Решил тут написать программку решения задачу о 8 ферзях. Если кто не
  YD> помнит условие, то надо расположить на шахматной доске 8 ферзей так,
  YD> чтобы они друг друга не "били".
  YD> Возникла проблема: решения получаются, их 92 штуки, однако
  YD> несимметричных лишь 12. Hужен алгоритм, который позволил бы убрать
  YD> лишние варианты.
 
  YD> Hаше положение доски хранится в виде [04752613].
  YD> Ясно, что есть также
  YD> [06471352] (Отражение относительно главной диагонали)
  YD> [73025164] (Отражение относительно горизонтали)
  YD> [31625740] (Отражение относительно вертикали)
  YD> .
  YD> .
  YD> .
  YD> И т.д. Итого 8 штук. Вопрос такой: можно ли как-нибудь придумать
  YD> какое-то разделение множества всех позиций на 8 подмножеств (где каждое
  YD> получается из другого поворотами и отражениями), а потом определить
  YD> относится ли положение к какому-нибудь из них?
 
 Hу, так и делать:
 1 Hашел и сохранил в список все расстановки, объявив их непомеченными.
 2 N=1
 3 выбрал любую непомеченную и пометил ее N
 4 попременял к ней симметрии
 5 все полученные в п.3 пометил N
 6 N = N+1
 7 перешел к п.3
 
 В п.4 попременял симметрии означает вот что:
 перед началом ты выписал два преобразования симметрии (гор. и верт. - из них
 можно получить любое другое отображение шахматной доски на себя)
 А в п.4 применяешь к текущей оба преобразования - результат помещаешь в очередь 
 С каждым из результатов делаешь тоже самое.
 В общем в п.4 ты как раз и будешь получать все расстановки получаемые друг из
 друга посредством преобразований движения (симметрии и поворотов)
 
 Всем спасибо, до свидания! С вами был Егоров Павел :)
 
 --- GoldED/386 3.00.Alpha3+
  * Origin: 2+2=4 это не тождество, а выражение равное TRUE (2:5080/169.35)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    8 ферзей   Yasha Davidov   16 Feb 2002 00:49:38   8 ферзей   Max Alekseyev   15 Feb 2002 19:15:40   Re: 8 ферзей   Yasha Davidov   16 Feb 2002 15:16:10   8 ферзей   vitalie vrabie   23 Feb 2002 02:00:52   8 ферзей   Egorov Pavel   18 Feb 2002 00:26:48   Re: 8 ферзей   Yasha Davidov   18 Feb 2002 01:44:00   Re: 8 ферзей   Zeram Z   18 Feb 2002 13:32:29   Re: 8 ферзей   Andrew Ezhguroff   18 Feb 2002 16:48:59   8 ферзей   Egorov Pavel   19 Feb 2002 00:33:19   8 ферзей   Dan Raskovalov   21 Feb 2002 10:23:31