Алгоритм быстрых шахмат

Нужно написать программу по данной задаче: На шахматной доске размером n ´ n расставлено k фигур. Предполагается использование только следующих типов фигур: ладья, слон, конь, ферзь. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти минимальную последовательность ходов, после которой на доске останется одна фигура.

Исследовать асимптотическую временную сложность решения задачи в зависимости от n и k. Пожалуйста, прошу помочь