@SergProgC++

Приветствую всех форумчан!!!!
Дана задача:
Найти возможные способы для удара ферзем максимального количества вражеских фигур за N проходов исходя из определенного задаваемого положения вражеских фигур, не изменяющих своего положения. Определить кратчайшие.
Подскажите кто может с чего начинать алгоритм выполнения и может ссылочки какие есть с готовыми кодами?

0

KuKu

Напомнило "задачу комивояжора", посмотри может поможет.

0

@Andrew_Lvov

Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём.
При каждом взятии увеличивается счётчик.
Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку.
Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами.

0

@SergProgC++

А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно

0

KuKu

Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.

0

@SergProgC++

подскажи какой алгоритм тут надо использовать

0

KuKu

вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором.

0

@SergProgC++

было бы не плохо еслиб код кто выложил или часть кода с чего начать можно

0

valeriikozlov

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

0

KuKu

Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.

Миниатюры

 

0

valeriikozlov

KuKu, согласен. А как картинку вставить в ответе?

0

KuKu

в расширенном режиме, нажать скрепку.

0

valeriikozlov

В расширенный режим что бы перейти, нужно нажать значек А/А?

0

KuKu

вот так

Миниатюры

   

0

@alexzak

Для начала надо постоить взвешенный граф всех передвижений ферзя от одной фигуры к другой. Вершины графа - это поля на шахматной доске, где находятся фигуры или сам ферзь. Вес ребра в графе будет равен количеству шагов, которое ферзь должен сделать от поля одной вершины к другой. Сделаем это для твоего рисунка. Но сначала определим координаты фигур (в шахматной нотации):

ферзь: c2
фигуры: c5, c8, f3, f5

Вершины в нашем графе будут такие: c2, c5, c8, f3, f5.
Ребра:
c2-c5, вес=1
c2-c8, 1
c2-f3, 2 (нужно два шага)
c2-f5, 1
c5-c8, 1
c5-f3, 2
c5-f5, 1
c8-f3, 2
c8-f5, 1
f3-f5, 1

После построение этого графа задача сводится к комивояжеру, т.е. нужно найти путь в графе, обходящий все вершины с наименьшей суммой весов ребер.

Но есть еще одна тонкость. Иногда таким образом будут находится неверные пути, т.е. ферзь с с2 на с8, перескакивая через с5. Поэтому в конце программы нужно проверять пути и отбрасывать неверные.

0

@SergProgC++

А пример кода или пошаговый алгоритм ко всему этому есть?

0