Think about upper bound

[LukasKalbertodt]

Given an n_n board, after how many moves are we guaranteed to find a solution? One trivial upper bound is: n_n. It's pretty obvious that you can always solve the board with n*n moves. But I'm pretty sure that there is a much smaller upper bound, hopefully a linear one.