ru.algorithms

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

 
  Как-то раз Yasha Davidov писал Egorov Pavel следующее:
 
  YD> Пока я сделал так:
  YD> Я перебираю значения в таком порядке:
  YD> [01234567]
  YD> [01234576]
  YD> [01234657]
  YD> [01234675]
  YD> ...
  YD> Всё это очень похоже на простой перебор чисел. Поэтому я делаю так,
 
 Бу!
 Hе делай так больше :)
 Это делается Backtracking'ом (он же "поиск в глубину" и "перебор с возвратом")
 Ты же перебираешь много чего лишнего. Так, например, если уже первый ферзь бьет 
 второго, то положение всех остальных перебирать не надо.
 
 Алгоритм примерно такой:
 Все поле свободно.
 Ставим первого ферзя и объявляем все поля, что он бьет, занятыми.
 Если удается поставить на свободное место следующего ферзя - ставим. иначе
 убираем последнего поставленного ферзя и ставим на следующее место.
  YD> когда я нахожу перестановку, являющуюся решением я беру все её 8
  YD> отражений, и если хоть одно из этих отражений меньше, (то есть было
  YD> раньше) чем текущая доска (я могу легко это определит), то значит этот
  YD> тип доски я уже находил раньше. В противном случае это решение. Плюс я
  YD> перебираю только от [01234567] до [476543210], то есть только
  YD> половину.
 
 Hу а так все ок!
 
 Всем спасибо, до свидания! С вами был Егоров Павел :)
 
 --- 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