What sensors are you able to use?
Do you have to use the method of inputting coordinates? I would approach it with turns, rather than coordinates.
//Pseudocode
If(Turn is Possible)
turnDirection(turns[nextTurn++]);
Then, put 3 buttons for direction. For the example maze it would be turns[]={L,L,R,L,S,S,L,L}