| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] Задача о расстановке ладей |
| Автор: YauhenKlimat 15.11.2009, 13:53 |
| Ребята, доброго времени суток откликнувшимся. Помогите составить алгоритм задачи. Условие: Расставить МАКСИМАЛЬНОЕ кол-во белых ладей на поле m*n , чтобы они не били друг друга (понятно, что белые, впрочем как и черные не бьют друг друга, но имеется ввиду не были в поле зрения друг друга), +условие: на поле уже могут стоять черные фигуры в указанных местах). Спасибо. Очень надо, все сроки поджали. |
| Автор: Qawra 17.11.2009, 23:35 |
| Насколько я помню в книжке была задача о шахматных королевах . Их можно поставить на поле 8 штук так что не одна из них не сможет аттаковать другую. Существуют 12 уникальных растановок и много симметричных от них . Трюк в том что каждая королева должна находиться точно на растоянии "хода конём" от следующей королевы. Про чёрные фигуры в той задаче ничего небыло сказано . |
| Автор: YauhenKlimat 17.11.2009, 23:44 |
| да, я тоже читал про эту задачу, она есть во многих книгах. Но у меня именно такое условие, как написано. |
| Автор: Qawra 19.11.2009, 23:44 |
| Посмотрите здесь ... http://en.wikipedia.org/wiki/Eight_queens_puzzle |
| Автор: Alexk553 20.11.2009, 02:32 |
| Решение зависит от целей, которые ставил преподаватель. Если это приложение к комбинаторике, то и решение должно быть комбинаторным. В данной задаче число комбинаций не астрономическое, так что можно их спокойненько все перебрать, отсекая, естественно, все ненужные подмножества комбинаций (например, если две ладьи на одной клетке, то бессмыссленно перебирать все остальные комбинации других ладьей), благо компьютеры сейчас очень мощные, не то что раньше. |
| Автор: YauhenKlimat 21.11.2009, 18:38 |
| Ребята, спасибо всем, кто откликнулся. Сажусь за прогу. Да, задача на перебор всех вариантов с отсечениями( по допустимости, рекорду). |