Скачать: CL | DM;

На доске (8х8) расставлено 8 ферзей   Найти похожие ветки 

← →
RiP   (2006-02-21 12:34) [0]

На доске (8х8) расставлено 8 ферзей (ферзь бьет по вертикали, горизонтали и диагонали). Убрать часть из них так, чтобы оставшиеся не били друг друга. Число оставшихся ферзей должно быть максимально.
хотя бы  Подскажите кто нить алгоритм

---

← →
Ega23 ©   (2006-02-21 12:41) [1]

Яндекс рулит.
А вообще - самостоятельно такие задачи надо решать. Их тебе в ВУЗе не просто так задают.

---

← →
TUser ©   (2006-02-21 14:51) [2]

Строим граф G = (V, E), где V - это ферзи. (v1, v2) in E, тогда если ферзь v1 не бъет ферзя v2 и наоборот. Искомое множество ферзей - это максимальная клика в графе. В общем случае задача нерешаема (она NP-полная), но при таком размере я бы решил перебором.

См. также ссылки на тему "задача о вершинном покрытии".

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.029 c