3 ms·

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

• pjscott 12y ago
  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.
• matchu 12y ago
  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.