Мне кажется, тут стоит использовать алгоритм поиска как раз для минимизации кол-ва ходов. Например, найти ферзей, которые пересекаются и двигать дальше только их. Затем исключить клетки, которые не подходят под условие и среди оставшихся найти для конкретного ферзя ближайшую.
Хотя такое решение жадное может быть