Есть поле на котором действуют 2 правила:

тут 3 варианта, но в сущности первый и третий это одно и то же, просто для наглядности
Т.е. коротко:
- Начинать можно с любой позиции поля, где на пути имеется хоть одна цифра
- Ход может быть только в горизонтальном или вертикальном направлении
- Ход возможен только до упора(пока цифра не встретилась, остановиться нельзя), при встрече с цифрой она сдвигается на 1 клетку и уменьшается на единицу(если больше единицы) или исчезает(если была единица)...
- И дальше можно менять направление.
- Если при сдвиге цифры сдвигаются на соседние, то они складываются
- Выход сдвиг цифры за пределы поля не возможен(заложено в алгоритме генерации)... Это в общем не нужно, т.к. не встретится, но на всякий случай.

Вот пример поля

Начинать можно с любого места, цель - убрать все цифры с поля.

Главный вопрос:
Можно ли свести решение этой задачу к какому-либо стандартному алго? Или может к графу?
Скорее всего да, но я никак не придумаю к какому.
Для просто брута уже это поле требует достаточно времени. Я реализовал, это конечно можно долгое время оптимизировать по скорости, но это изначально тупиковый вариант думаю, т.к. 
Видел программу, которая решает за секунды и это особенно захватывает, при чём относительно большие поля, а не этот простой пример!
Значит можно! Осталось только продумать логику.

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

Я начал с того, что ограничил все возможные начала работы алгоритма, отрезав все дубли по возможности.
Примерно следующим образом:

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

Кто может навести на путь истинный? Как правильнее подойти к решению.


Это сообщение отредактировал(а) Isaev - 26.5.2013, 05:29

игра прикольная

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

в таком случае вся сложность сводится к выбору эвристик

но вообще, такие варианты на тот случай, если ничего нормального не придумается...

maxim1000, эвристика да, поможет максимально быстро выйди к нужному началу скажем так... 
А с самим алго решения как быть? снова брут?
скажем так, у второго хода, учитывая, что их макс 4, эвристику мы уже не высчитаем, т.к. пока не дойдём до тупика ситуацию сложно оценить

Это сообщение отредактировал(а) Isaev - 26.5.2013, 20:31

Чем-то напоминает игру Voracity... 

если пытаться оченить точно - сложно
а можно попробовать простые правила и посмотреть, что получается

например "меньше заполненных клеточек", "больше заполненных клеточек", "меньше сумма чисел", "меньший разброс по полю"

Добавлено через 34 секунды
хотя гадание всё это, к сожалению

нормального ничего в голову не приходит

а можно "правила" описать текстом? а то я не понял...

Этот ответ добавлен с нового Винграда - http://vingrad.com

В первом посте под первой картинкой описаны текстом правила

Не указано, что произойдёт, если "черепаха" достигнет края поля (точнее, в выбранном направлении движения нет полей с цислами).


Более простой вариант - неограниченное поле.