In the old video game Q*Bert, Q*Bert hops on squares on a 7-high pyramid to try to change them a certain color. Q*Bert can also jump off the edge onto discs, which drop him back on the top square, which then changes.
In my sample level(s) I also place a disc in the bottom right.
x <-Q*Bert starts here and doesn't change its color originally. x x x x x x x x x x x x x x x x x x x x x x x x x x x <there is a disc up and right from the lower right
On level 1, Q*Bert changes them from color X to color Y on the first jump, and the second jump does nothing. I can prove the minimum number of jumps is 31.
The proof is sort of like the checkerboard problem. Q*Bert must always jump from an odd numbered row to an even and vice versa, except when he takes the disc, which moves him from an odd to an odd. There are 16 odd squares to fill and 12 evens. Since the first jump is to an even, you'll need at least 32 jumps without the discs, but the disc saves a jump since you hit 2 odd squares in a row. It's not hard to construct a series of jumps that works, minimally.
On level 2, Q*Bert must change each square twice (X->Y->Z), and the number of jumps is 62, by similar reasoning.
But figuring level 3 is a bit different. On level 3, Q*Bert changes a square from color X to color Y and back again.
The current best pattern I've found is (DR = down right, UL = up left, etc.)
DR.DR.DR.DR.DR.DR.UR (onto the disc).DL DR.DR.DR.DR.DR (this puts us in a corner) UL.DL.UL.UR.DR.UL.DL.DL.UR (this dance costs us 6 moves e.g. 9 moves to cover 3 squares but I don't see an easier way to do it) UL.UL.UL.DL.DR.DR.DL.UL.UL.DL.DR.UL.DL.UR
This is 36 moves, which seems pretty good. There seems to be no way to avoid losing 2 moves finishing the level in the left corner, and there seems to be no way to avoid losing a few moves in the right corner. But my question is, then: is my move to cover the lower right optimal? If so, why? And if not, how can I do better?
I suppose once it's provable that Q*bert's dance that costs 6 moves is optimal, I can figure out the minimum # of moves for any size board, or even for the later levels that go X->Y<->Z and X->Y->Z->X, but ... is there a way to prove that what I am doing is optimal? Or can I do better?