ソートの交換回数の最小化(Ruby)

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

問題:
例えば 1~3 の数字が任意に並んだ 3桁の数字を、各桁の入れ替えによってソートする場合、その入れ替えの数が最小になるようにソートしたとします。たとえば 231 なら 231→132→123 で 2回の入れ替えになります。これをすべての順列において行い、入れ替え数の合計を出します。例えば 1~3 の場合なら、最小の入れ替え数の合計は 7回になります。
さて、これを 1~7 の 7桁の場合において求めて下さい。

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

h = {"1234567" => 0}
queue =[["1234567", 0]]
while (x = queue.shift)
  st, depth = x
  [*0..6].combination(2) do |i, j|
    st1 = st.dup
    st1[i], st1[j] = st1[j], st1[i]
    next if h[st1]
    h[st1] = depth + 1
    if h.size == 5040
      puts h.values.inject(:+)    #=>22212
      exit
    end
    queue.push([st1, depth + 1])
  end
end

求める最小の入れ替え数の合計は 22212回になります。かかった時間は僕の環境で 0.1秒あまりです。

ソートの目標の "1234567" から出発して、すべての入れ替えを行い、深さを 1ずつ増やしていって最終的にすべてのパターン(7! = 5040 とおり)があらわれるまで繰り返します。そして、最後に合計数を求めます。

ただこれ、幅優先探索で正解が求められるのですが、深さ優先にするとダメなのですよね。どうしてなのかいまひとつよくわからないのが恥ずかしい…。
いや、当り前か。いきなり深く潜ったらもっと早く出ている筈のパターンが深くなってしまうか。

ちなみに、深さの最大値は 6 です。これは考えてみたら当然ですね。7桁なら最大 6回入れ替えればソートできると。