横着なそろばん(Ruby)

アルゴリズム・パズルです。

問題:
そろばんで例えば「8 + 9」をこの順に計算すると、「8 を入れる」のに玉を 4つ動かし、「9 を足す」のに玉を 2つ動かすので、全部で 6回玉を動かすことになります。また、逆に「9 + 8」の順に計算すると、全部で玉を 8回動かすことになります。このように、同じ答えになる場合でも、玉を動かす回数が異なることがあります。
さて、1 から 10 までの総和をこのようにそろばんで求めるとき、玉を動かす数の最小値はいくらになるでしょうか。

 
Ruby で解いてみました。
q55.rb

@table = [[0, 1, 2, 3, 4, 1, 2, 3, 4, 5],
          [0, 1, 2, 3, 2, 1, 2, 3, 4, 1],
          [0, 1, 2, 3, 2, 1, 2, 3, 2, 1],
          [0, 1, 4, 3, 2, 1, 2, 3, 2, 1],
          [0, 5, 4, 3, 2, 1, 4, 3, 2, 1],
          [0, 1, 2, 3, 4, 1, 2, 3, 4, 5],
          [0, 1, 2, 3, 2, 1, 2, 3, 4, 1],
          [0, 1, 2, 3, 2, 1, 2, 3, 2, 1],
          [0, 1, 4, 3, 2, 1, 2, 3, 2, 1],
          [0, 5, 4, 3, 2, 1, 4, 3, 2, 1]]

def cal(a, b)
  n1, n2 = a / 10, a % 10
  if b == 10
    @table[n1][1]
  else
    @table[n2][b] + ((n2 + b >= 10) ? @table[n1][1] : 0)
  end
end

def solve(before, after, sum, co)
  if before.empty?
    if @min > co
      @min = co
      p [@min, after]    #=>[26, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
    end
    return
  end
  before.size.times do |i|
    a = before[i]
    b = co + cal(sum, a)
    next if b >= @min
    after1 = after + [a]
    before1 = before[0, i] + before[i + 1..-1]
    solve(before1, after1, sum + a, b)
  end
end

@min = Float::INFINITY
solve([*1..10], [], 0, 0)

答えは 26回ですね。ふつうに 1 から 10 まで順に足すのが最小値を与えるようです(この順だけが最小値を与えるわけではありません。最小値を与える足し方は 614880 通りもあります)。かかった時間は自分の環境でほぼ 4.2秒、solve() 呼び出しの回数は 4090969回です。模範解答とはちがって Array#permutation を使ってはいません。

なお、コード中の after の項はここでは本質的に必要ないので、これをカットすると多少高速化し、実行時間は 3.3秒ほどになります。

ちなみに、最大値は 42 で、例えば [3, 2, 4, 1, 5, 8, 7, 9, 6, 10] の順に足すとこれが得られます。なるほど、5 を作っていくと大きくなるようです。26 と 42 とは結構差があるものですね。