[Edit: The gibberish sentence "A variation moving up is also allowed." was meant to say "A variation of this solution can be used to solve the case where moving up is also allowed."]