Depends on the initial state of the puzzle. Sometimes there's always a deterministic set of correct next moves to make. I guess this refers to cases that aren't like that?
Right; we're talking about upper bounds here. Assume that the boards are chosen by some kind of wily, malevolent demon with an obsessive desire to embed tricky 3SAT problems in everything.
Similarly, sometimes your sorting algorithm takes linear time because the input was a sorted list. That's the lower bound, but lower bounds usually aren't as interesting as upper bounds.
