Finding Pairs for Letters
Ruby 319 313 310 304 287 283

F=-&gt;s{l=s.split ?\n
b=[]
t={}
[*0...m=l.size].product([*0...n=l[0].size]).map{|y,x|c=l[y][x]
c!=' '&amp;&amp;c&gt;?Z?b&lt;&lt;[c,y,x]:t[c.downcase]=[y,x]}
b.map{|q|c,y,x=q
u,i=t[c]
(m*n).times{|w|e=([u-(y+w)%m,i-(x+w)%n].map &amp;:abs).max
e&gt;c.ord-97||q&lt;&lt;w+e}
q[3]&amp;&amp;[q[3],q[0]]}.compact.sort.map{|a,b|b}}

This is a function that takes as input a string (without trailing newline) and returns an array of the lowercase letters in the correct order.
Here's a version you can run online with tests: http://ideone.com/5jiwLq
I've made a lot of modifications to the code. The history of modifications is available here.
Here's the indented and annotated version to make it easier to see what's going on (also available online):
F=-&gt;s{
  l=s.split ?\n
  m=l.size
  n=l[0].size

  # Make an array with lowercase letters and their coords (`b`)
  # Make a hash that for each target (uppercase letter) holds
  # its coordinates
  b=[]
  t={}
  [*0...m].product([*0...n]).map{|y,x| 
    c=l[y][x]
    c!=' '&amp;&amp;(c&gt;?Z?b&lt;&lt;[c,y,x]:t[c.downcase]=[y,x])
  }
  
  # `l` is a function that, given an array of the form
  # [lowercase_letter, y-coord, x-coord] will append to that array
  # the number of steps required for the letter to reach its
  # uppercase correspondent
  l=-&gt;q{
    c,y,x=q
    u,i=t[c]
    d=c.ord-97
    (m*n).times{|w|
      e=([u-y,i-x].map &amp;:abs).max
      e&lt;=d&amp;&amp;q&lt;&lt;w+e
      y=(y+1)%m
      x=(x+1)%n
    }
  }

  # apply function `l` to each of the lowercase letters...
  b.map &amp;l

  # ...then sort accordingly and return the array
  b.map{|x|[x[3],x[0]]}.select{|a,b|a}.sort.map{|a,b|b}
}