The complexity is based on the total number of nodes that you look at, not at the depth (the number of moves).
With depth = 0 (no move), you will look at 1 node (the initial state). If you have 2 moves possible, at depth = 1 you'll look at 2 nodes, at level 2 at 4.. At level 30, you will look at 2^30 nodes.
You know how many nodes you will look at, if you check with max level 0, then max level 1, ... , then max level 29?
Let's see: solution
So, if you check FROM level 0 TO level 29, you are actually analysing less nodes that just looking at level 30 (exactly 1 node less). If you have 4 moves, it gets waay worse.
With your method, you are actually looking at level 30, then level 29, and down that way until you don't find a solution, which might be at something like level 10. This has a complexity that saying it's terrible is a great compliment. Your method would probably fail for grids really little bigger than the current one.
With the one I told you, you would get a way faster solution if there is one in less than 30 moves, and if there isn't one, it would take a slightly more than your current one.
So, you have two options: you either implement UC, or you implement interative deepening like I described it. Space state explorations is a kind of problems studied a lot and with precise optimal approaches, I highly suggest you to follow them, unless you want your algorithm not be able to tackle bigger problems (or just be slow with current ones ;) ) @apatriarca since he talks about a LIFO, I think he implemented a depth first search, so it's not guaranteed to be optimal. On this aspect he was right ;)