Сложность понимания рекурсии головоломки

Question

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

я могу проверить, если данная проблема разрешима или нет:

bool Solvable(int a[], int index, int target, int sz, int b[]) { 
    static int b_ind = 0; 
    if (target == 0 && index == sz-1) 
     return true; 
    if (index >= sz || index < 0) 
     return false; 
    int u_ind = index+a[index]; 
    int d_ind = index-a[index]; 
    bool u_y = Solvable(a,u_ind,a[u_ind],sz,b); 
    if (u_y) { 
     b[b_ind++] = u_ind; 
     return u_y; } 
    else { 
     bool d_y = Solvable(a,d_ind,a[d_ind],sz,b); 
     if (d_y) { 
      b[b_ind++] = d_ind; 
      return d_y; } 
    } 
} 

, но я не в состоянии напечатать последовательность индексов посетил правильный решение.

Answer 1

2 вещи, чтобы сделать:

1. Когда критерий достигается, например, if (target == 0 && index == sz-1), отобразить переменную b. b где ваш магазин исследуемый путь?
2. когда решаемые (...) возвращает false вы должны уменьшаете b_ind

NB: ваш код немного подозрительный, поскольку последний if не имеет какого-либо другое; это отсутствует:

 if (d_y) { 
      b[b_ind++] = d_ind; 
      return d_y; 
     } /* the following block is missing */ 
     else 
     { 
      b_ind--; 
      return false; 
     } 

Answer 2

Вы не можете напечатать индексы на вашем пути, потому что вы не знаете заранее, будет ли вам найти решение или нет. Итак, что вам нужно сделать, в ваших рекурсивных вызовах передать список («путь») посещенных позиций. Убедитесь, что вы не изменяете существующие пути, но фактически создаете копии.

Кроме того, вы можете продолжить поиск после того, как нашли первое решение, иногда есть несколько.

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

В исполняемом псевдокоде (они называют его Python) это что-то вроде:

def puzzle(lst): 
    def solve(pos, path): 
     if 0 <= pos < length: # position is inside puzzle 
      if pos not in path: # we've already been here; prevent looping 
       val = lst[pos] 
       newpath = path + [pos] # newpath is a *copy* of path with pos appended 
       if val == 0: # we've found one solution 
        print(newpath) 
       else: 
        solve(pos-val, newpath) 
        solve(pos+val, newpath) 
    length = len(lst) 
    solve(0, []) 

puzzle([3, 6, 4, 1, 3, 4, 2, 5, 3, 0]) 

Для примера это дает:

[0, 3, 2, 6, 8, 5, 9] 
[0, 3, 4, 1, 7, 2, 6, 8, 5, 9] 
[0, 3, 4, 7, 2, 6, 8, 5, 9]