Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken
Don't be so quick to reject your approach!  Your approach is a great solution.  On a $15\times 15$ grid, you'll only have to try 225 different options.  Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds.

As Knuth supposedly said once, "premature optimization is the root of all evil". My advice: Try that solution, implement, and measure its performance, before you even consider anything else.