Puzzle: You have an infinite grid in the first quadrant. It extends infinitely as X and Y increase. You begin with a pebble in the 0-0 grid in the bottom left hand position. You can perform moves by removing a pebble and placing two new pebbles, one above and one to the right of the old pebble. This can only be performed if both of the new locations are not occupied. Is it possible to clear the area [0-0,0-1,1-0,1-1,0-2,2-0]?
I won't spoil the answer here; but I have implemented a partial checker in Prolog. The complexity is obviously exponential, but it was surprisingly easy to write.
Example (Smallest L in 8 or fewer moves):
play([0-0,0-1,1-0], 4, Moves).
Output:
Moves = [0-0,0-1,1-1,1-0|_A] ? ;
Moves = [0-0,1-0,1-1,0-1|_A] ? ;