Depending on what you mean here, you are misrepresenting the problem. You may not have to guess for what is a valid move that can be done on the board as it is. But you do have to guess for a valid move that will lead you to a completed board. Hence, you search among the possible moves for the one(s) that will lead to a completed board state.
