Насколько я знаю, простого алгоритма для этого не существует.Что касается направления вас в правильном направлении, то сетка 8x8 - это на самом деле особый случай графа, поэтому я бы начал с алгоритмов обхода графа.Я обнаружил, что в подобных случаях иногда помогает подумать, как бы вы решили проблему для сетки меньшего размера (скажем, 3x3 или 4x4), а затем посмотреть, масштабируется ли ваш алгоритм до «полного размера».
РЕДАКТИРОВАТЬ:
Мой предложенный алгоритм представляет собой модифицированный обход в глубину.Чтобы использовать его, вам нужно преобразовать вашу сетку в график.График должен быть ненаправленным, поскольку связанные блоки связаны одинаково в обоих направлениях.
Каждый узел графа представляет отдельный блок, содержащий значение блока и переменную visited.Веса ребер отражают устойчивость их ребер к следованию.Установите их, суммируя значения узлов, которые они соединяют.В зависимости от суммы, которую вы ищете, вы можете оптимизировать ее, удалив ребра, которые гарантированно потерпят неудачу.Например, если вы ищете 15, вы можете удалить все ребра с весом 16 или больше.
Остальная часть алгоритма будет выполняться столько раз, сколько существует блоков, причем каждый блок служитстартовый блок один раз.Пройдите по графику, следуя по краю с наименьшим весом от текущего узла, если это не приведет вас к посещенному узлу.Поместите каждый посещенный узел в стек и установите для его переменной visited значение true.Сохраняйте промежуточную сумму для каждого пройденного пути.
- Когда будет достигнута нужная сумма, сохраните текущий путь в качестве одного из ваших ответов.Не останавливайте прохождение, поскольку текущий узел может быть подключен к нулю.
- Когда сумма превышает желаемую сумму, вернитесь назад, установив для
visited значение false и выбросив текущий узел из стека. - Когда бы ни были исследованы все ребра для данного узла, возвращайтесь назад.
После того, как каждый возможный путь от данного начального узла проанализирован, каждый ответ, который включает этот узел, был найден.Итак, удалите все ребра, касающиеся начального узла, и выберите новый начальный узел.
Я еще не полностью проанализировал эффективность / время работы этого алгоритма, но ... это не хорошо.(Учитывайте количество путей, которые нужно найти в графе, содержащем все нули.) Тем не менее, это намного лучше, чем чисто грубая сила.