S.G.Условие не очень, конечно... "Между клетками могут быть заборы, при встрече с которым фишка остается на месте, если ход в сторону клетки перегороженной забором. " Не может ходить через забор, и все. Какой же это алгоритм, который задаст направление через забор, чтобы фишка не могла перейти и пропустила ход?
Вообще-то условие нормальное, если расстановка стен заранее неизвестна.
ТС, к сожалению, экономит на словах, а хорошо бы всё же уточнить такого рода вещи. Скажем, то, что фишки изначально находятся в произвольных клетках, означает, что координаты этих клеток задаются при старте, или мы знаем только то, что фишки находятся на доске?

ЕвгенийВКоординаты задаются на старте.
Если все координаты задаются при старте, то задача становится тривиальной.
Формируешь из начального положения фишек множество возможных положений после нулевого хода - ФФ(0).
Затем из него формируешь множество возможных положений после первого хода ФФ(1). И т.д. Очевидно, что множество ФФ(n) входит в ФФ(n+1).
Процесс продолжаешь до тех пор, пока не выполнится одно из двух условий:
1) фишки попали в лунки (клетки лунок попали нужным образом в множество положений после некоторого хода)
2) множество положений не увеличилось после очередного хода

ЕвгенийВyugl,
Все осложняется тем, что фишек >=2. Сначала можем загнать одну, потом другую.
Алгоритм практически универсален, от числа фишек не зависит, собственно, необходимо только определить правила получения новых возможных положений из текущего.
Единственный (но серьезный) недостаток алгоритма - быстрый рост числа возможных положений при росте числа фишек.

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