This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in the grid is unoccupied. What is the largest tile that can be produced by any (possible length-zero) sequence of moves (up, down, left,right) from the given game setup, if no new tiles were to be introduced to the grid?
For example, given
2 64 4 32
8 16 8 4
4 32 4 0
2 2 0 0
the answer is 128:
The problem can probably be solved by those AI algorithms (minmax for example), however, I guess that will definitely be an overkill. Is there any simpler algorithm to solve this?