打印一个递归回溯问题的过程

Question

学校给了我这个作业：

你得到了一个由一排正方形组成的谜题，每个正方形包含一个整数，如下所示：

6, 4, 1, 3, 3, 1, 4, 1, 1, 0

初始方块上的粗体数字是一个标记，可以沿行移动到其他方块。在拼图的每一步，您都可以将标记移动其当前占据的方格中的整数所指示的方格数。标记可以沿行向左或向右移动，但不能移过任何一端。拼图的目标是将标记移动到行远端的 0。

程序会检查您当前所在的索引，并根据数组中该索引处的整数向左或向右移动一定数量的方块。它根据数组的边界决定这一点，如果它不能向左移动所需数量的方块，它将向右移动，反之亦然。在这个程序中，第一步必须向右移动 6 格，因为它不能在不出界的情况下向左移动 6 格。然后，它向左移动4，因为它不能向右移动4，就这样。

我已经开始工作了，打印这个过程值得额外加分。我让它打印了这个过程，但它出了问题。

这是我的代码：

def self.solvable(start, board)

     return false if start>= board.length || start<0
     return false if @@infinite[start] == -1
     return true if board[start] == 0

     @@infinite[start] = -1

     if solvable(board[start] + start, board)
          puts "Shifted right " + board[start].to_s + " spaces, from index " + start.to_s + " to index " + (board[start] + start).to_s
          return true
     else
          puts "Shifted left " + board[start].to_s + " spaces, from index " + start.to_s + " to index " + (start - board[start]).to_s
     end       
     return solvable(start - board[start], board)
end

print "Enter an array of numbers: "
input = gets.chomp!

board = input.each_char.map(&:to_i)
@@infinite = input.each_char.map(&:to_i)
puts solvable(0, board)

我不明白如何以更合乎逻辑的顺序输出代码，向右打印 6 个空格，向左打印 4 个空格等...而不是当前输出，即：

左移 4 个空格，从索引 6 到索引 2

左移 3 个空格，从索引 3 到索引 0

左移 1 个空格，从索引 2 到索引 1

左移 1 个空格，从索引 5 到索引 4

右移 1 个空格，从索引 8 到索引 9

右移 1 个空格，从索引 7 到索引 8

右移 3 个空格，从索引 4 到索引 7

右移 4 个空格，从索引 1 到索引 5

右移 6 个空格，从索引 0 到索引 6

Answer 1

假设

我假设游戏从位置 0 开始。每一步都会增加或减少一个整数量的位置。 objective是在第一步走完后回到位置0。

我们得到一个整数数组 arr，以及从位置到数组索引的映射。对于位置 p，arr 的索引由 p % arr.size.

给出

如果我们在位置 p，我们获得的值可能会移动到位置 p + n 或 p - n，其中

n = arr[p % arr.size]

对于给出的示例：

arr = [6, 4, 1, 3, 3, 1, 4, 1, 1, 0]

(arr.size #=> 10) 和 p 最初为零，

n = arr[0 % 10]
  #=> arr[0] => 6

所以我们可能会移动到位置+6 或-6。如果我们移动到+6，我们计算

n = arr[6 % 10]
  #=> 4

所以我们可以移动到位置 6+4 #=> 10 或 6-4 #=> 2。如果我们移动到-6，我们计算

n = arr[-6 % 10]
  #=> 3

所以我们可以移动到位置 -6-3 #=> -9 或 -6+3 #=> -3。

请注意，arr[9] #=> 0 可以视为 吸收状态 。

代码

我选择使用的方法是递归的。

def onward_to_zero(arr, pos=0)
  n = arr[pos % arr.size]
  return [] if n.zero?
  return [-n] if (pos-n).zero?
  return [n] if (pos+n).zero?
  if rand < 0.5
    rv = onward_to_zero(arr, pos-n)
    return [-n] + rv unless rv.empty?
    rv = onward_to_zero(arr, pos+n)
    return [n] + rv unless rv.empty?
  else
    rv = onward_to_zero(arr, pos+n)
    return [n] + rv unless rv.empty?
    rv = onward_to_zero(arr, pos-n)
    return [-n] + rv unless rv.empty?
  end
  []
end

我相信总有一条归零之路是可以证明的，但我还没有想过证明。

例子

arr = [6, 4, 1, 3, 3, 1, 4, 1, 1, 0]

onward_to_zero(arr)
  #=>       [-6, 3, 1, -1, 1, -1, -1, 4]
  # pos % 10  0  4  7   8  7   8   7  6    
  # pos->  0 -6 -3 -2  -3 -2  -3  -4  0

arr = [3, 2, 4, 1, 3, 6, 2]

onward_to_zero(arr)
  #=>    [3, -1, 4, 2, 2, 1, -3, 2, -1, -4, -6, -2, 3]
  # pos-> 3   2  6  8 10 11   8 10   9   5   -1 -3  0

arr = [3, 3]

onward_to_zero(arr)
  #=>    [-3, 3]
  # pos-> -3  0

arr = [7, 26, 33, 18, 7, 13]
onward_to_zero(arr)
  #=>     [-7, -13,  7, 13]
  # pos->  -7  -20 -13   0

讨论

请注意，if rand < 0.5 使我在大约一半的时间里考虑在增加头寸之前减少头寸。如果我总是在增加之前考虑减少，反之亦然，我很容易得到 stack level too deep 错误。

然而，即使使用这种概率机制，该方法也会给出非常不同的结果，并且仍然可能导致 堆栈级别太深 错误。这是我运行第一个例子10次得到的结果。

[6, -4, 1, -3] 
[-6, 3, 1, -1, -1, 4] 
[6, 4, 6, 4, 6, 4, 6, 4, 6,..., -1, -1, 4] (824 elements) 
[6, 4, -6, -3, 4, 1, -4, -1,..., -4, 1, -3] (386 elements) 
[-6, 3, 1, -1, -1, 4] 
[-6, -3, 4, 1, 4] 
[-6, 3, 1, -1, 1, -1, -1, 4] 
[-6, -3, -4, -1, -4, 1, -3, 6, 4, 6, 4] 
[-6, -3, -4, 1, -1, -1, -4, -1, 4, 1, 4, 6, 4]
[-6, 3, -1, 4]

打印一个递归回溯问题的过程

Printing the process of a recursive backtracking problem

ruby

recursion

recursive-backtracking