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

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

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

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

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

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

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

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