Расстановка ладей с максимальной суммой

[Cash]

Пусть в каждой клетке на доске размером $n \times n$ записано действительное число. Требуется из всех расстановок небьющих друг друга ладей выбрать расстановку с максимальной суммой.

Кроме полного перебора ничего на ум не идет...

[venco]

Есть алгоритм со сложностью $n^3$. Искать по словам "Венгерский алгоритм" или "алгоритм Манкреса" (Hungarian algorithm, or Munkres assignment algorithm).

[Cash]

Спасибо!