Python3, 170 bytes

E=enumerate
def f(b):
 s=0
 while b:s+=1;t=[i for i in b[0]if i][0];b=[K for i,a in E(b)if any(K:=[''if j==t and(i==0 or''==b[i-1][I]) else j for I,j in E(a)])]
 return s

Try it online!

Ruby, 73 bytes

->l{l.permutation.map{|x|x*=?_;1while x.sub!(/(.*)_\1/,'\1');x.size}.min}

Try it online!

Assuming I can accept a list of columns in input

Ruby, 108 bytes

->l{l.map(&:chars).transpose.map(&:join).permutation.map{|x|x*=?_;1while x.sub!(/(.*)_\1/,'\1');x.size}.min}

Try it online!

Otherwise

J, 55 bytes

(1+[:<./$:"1)@((]}.~1{.=)&.>"0/~' '-.~{.&>)`0:@.(''-:;)

Try it online!

Brute force recursion taking away boxes until none are left, and returning the minimum number of steps.

Jelly, 24 bytes

ZWṖ€ṛ¦Ɱ0ịⱮĠƊ$€Ẏ$Ẹ€Ạ$пL’

Try it online!

A monadic link taking a list of Jelly strings (a list of lists of characters) and returning an integer.

Explanation

Z                        | Transpose
 W                       | Wrap in a list
                   $п   | While the following is true:
                Ẹ€       | - Any list is non-empty for each list of lists
                  Ạ      | - All
               $         | Do the following, collecting up intermediate results
            $€           | - For each list:
  Ṗ€ṛ¦Ɱ    Ɗ             |   - Remove the last character of the lists for each of the groups of indices determined by the following:
       0ịⱮ               |     - Last character of each list
          Ġ              |     - Group indices of identical characters
               Ẏ         | - Tighten (join outermost lists together)
                      L  | Length
                       ’ | Subtract 1

All cases (uses Q for 1 extra byte to make it more efficient, but would complete eventually without it)

Python 2, 103 91 bytes

-12 bytes thanks to PurkkaKoodari!

lambda s:f(zip(*s))
f=lambda s:len(s)and-~min(f({r[r[0]==x[0]:]for r in s}-{()})for x in s)

Try it online! The last testcase times out.

The first function just transposes the input, if we can take input as a list of columns it can be omitted.

Pyth, 22 bytes

L&lbhSmhyfT>RqhkhdbbyC

Try it online! Or run all test cases at once.

This is basically ovs's Python solution translated verbatim to Pyth (it seems that their solution's exact algorithm is also shortest in Pyth), so I'm posting it as community wiki. Doesn't time out thanks to Pyth's memoization.

Brachylog, 31 bytes

∧≜.&z{{⟨k≡t⟩|;X}ᵐRtᵛ∧Rhᵐ}ⁱ↖.zĖ∧

Try it online!

It's a bit less efficient than even the other two answers so far (it does the classic recompute everything if it hasn't reached the end in as many steps as it's trying), so I might just delete this when I wake up if it still hasn't spit something out for the second-to-last test case.

Charcoal, 57 bytes

ＷＳ⊞υι≔⟦Ｅθ⮌⭆υ§λκ⟧η≔⁰ζＷ⌊η«≦⊕ζ≔ηθ≔⟦⟧ηＦθＦκ⊞ηΦＥκΦμ∨π¬⁼ξ§λ⁰μ»Ｉζ

Try it online! Link is to verbose version of code. Uses brute force so too slow for the last test case on TIO. Explanation:

ＷＳ⊞υι

Input the pile.

≔⟦Ｅθ⮌⭆υ§λκ⟧η

Rotate the pile by 90° and put it into a list.

≔⁰ζ

Start counting the number of steps.

Ｗ⌊η«

Repeat until there is at least one empty pile.

≦⊕ζ

Increment the number of steps.

≔ηθ≔⟦⟧ηＦθ

Make a copy of the list of piles so that it can be looped over while starting a new list of piles.

Ｆκ

Loop over each column of the pile.

⊞ηΦＥκΦμ∨π¬⁼ξ§λ⁰μ

Remove the letter at the bottom of that column from all of the columns that have it as its bottom letter and push any remaining non-empty columns to the list.

»Ｉζ

Print the number of steps needed.