ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : vitalie vrabie                       2:469/303      23 Feb 2002  02:00:52
 To : Max Alekseyev
 Subject : 8 ферзей
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Max Alekseyev to Yasha Davidov:
 
  YD>> Решил тут написать программку решения задачу о 8 ферзях. Если кто не
  YD>> помнит условие, то надо расположить на шахматной доске 8 ферзей так,
  YD>> чтобы они друг друга не "били". Возникла проблема: решения
  YD>> получаются, их 92 штуки, однако несимметричных лишь 12. Hужен
  YD>> алгоритм, который позволил бы убрать лишние варианты.
 
  MA> Hу для начала можешь считать, что в базовых расстановках один из
  MA> ферзей стоит на полях a1-a4, так как этого всегда можно добиться
  MA> поворотами и отражениями. Это наблюдение резко сокращает количество
  MA> вариантов.
 
 на самом деле, банально. если первый ферзь убирается с какой-то позиции и
 ставится на следующую, тогда ту позицию с которой его убрали, равно как и восемь
 его симметрий, заносим в некий список (таблицу булевых). и в дальнейшем переборе
 - _никогда_ и не пытаемся ставить ни один ферзь ни на одну позицию из этого
 списка. это исключит появление симметрий (с участием других ферзей) уже
 пройденной комбинации.
 
 аналогично, кстати, делается и для анонсированного тут тобой конкурса с 3D/4D.
 только там симметрий больше - в общем(!) случае: 48 для 3D, и 384 для 4D,
 (включая исходную точку).
 
 формула кол-ва симметрий в общем(!) случае, для n-мерного куба - n!*2^n. как они
 генерятся - домзадание. ;)
 
 а если докажешь, что первому ферзю нефиг бегать дальше первой строчки (для 2D
 это очевидно, для 3D/4D - не совсем), то ровно на половине он и остановится.
 отсюда следует, что симметрии можно банить не все n!*2^n, а только те что
 находятся на рёбрах куба (до остальных ты просто не доберёшься).
 sayonara,
   vv                      mailto:vv<at>techie.com
 
 --- 
  * Origin: this line will never change (2:469/303)
 
 

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

Тема:    Автор:    Дата:    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