Китайская головоломка., рекурсивная работа с матрицей. Опции

[madrabbit]

Всем привет!
......o o o.....
......o o o.....
o o o o o o o
o o o .. o o o
o o o o o o o
......o o o.....
......o o o.....

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


вот тут мы уже разобрались с рекурсией подобного типа. Еще раз спасибо всем, кто помог.
Теперь треба идеи по поводу реализации данной задачки а именно сам алгоритм.
Спасибо.
:yessss: ну я погнал на шмиру...

"Неприличными словами не выражаться!" (С) Шариков
Перевожу: "Шмира" - Охрана
Volvo

Сообщение отредактировано: madrabbit - 9.03.2005 21:50

[madrabbit]

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

Ну так что, никто не блеснет идеей, с какого угла за нее взяться?

Даже volvo отписался шуткой-переводом 8)

жаль...

[hiv]

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

[hiv]

К стати можно потренироваться на сайте с такой игрушкой
http://www.wadim.ru/internet_games/go/go.html

[madrabbit]

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

спасибо.
жаль, хотел сам решить.
может напишешь в двух словах на пальцах алгоритм *) ?

[hiv]

Я опишу действия самой рекурсивной ф-ции:
1. Пробегаем по всем шашечкам
2. Проверяем может ли шашечка ходит вниз, если да, то ходим и запускаем рекурсивно нашу ф-цию с новой позицией, если нет, то идем дальше.
3. Проверяем может ли шашечка ходит вверх, если да, то ходим и запускаем рекурсивно нашу ф-цию с новой позицией, если нет, то идем дальше.
4. Проверяем может ли шашечка ходит влево, если да, то ходим и запускаем рекурсивно нашу ф-цию с новой позицией, если нет, то идем дальше.
5. Проверяем может ли шашечка ходит вправо, если да, то ходим и запускаем рекурсивно нашу ф-цию с новой позицией, если нет, то идем дальше.
6. Когда пробежали все шашечки и ни один из рекурсивных вызовов ф-ции не дал положительного ответа TRUE, то проверяем может всего-то одна шашечка осталась? Если это так, то решение найдено и возвращаем true. Тогда все рекурсивные вызовы начинают завершаться и освобождать память.

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

[madrabbit]

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

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

[hiv]

Это не секрет - на физфаке, отделение теоретической физики. Когда мы по кафедрам распределялись, на этой сказали - здесь нужно всего два инструмента: ручка и бамажка.
А вообще-то чтоб была золотая голова - нужна свинцовая задница!
В гениальности 99% труда и 1% вдохновения. - Т. Эдисон