Credo tu debba implementare un algortmo di tipo greedy, cioè basato su step successivi e ad ognuno verifichi che il parametro che tu stai utilizzando stia migliorando o meno.
Quindi in sostanza ti serve una funziona che ti dia la "distanza" dal tuo obiettivo senza considerare le caselle occupate. Per la regola del tassista, ti basta fare la differenza delle cordinate, senza badare al fatto che si avanzi a zig zag o no.
Parti dalla posizione blu e testi tale distanza sulle posizioni vicine e "scegli" quella che diminuisce maggiormente la distanza dall'obiettivo e ti segni i valori ottenuti. A parità di distanza scegli a caso. Ti sposti nella posizione scelta e fai lo stesso test e ti sposti nuovamente ovviamente sempre scartando le posizioni occupate
Prima o poi così arriverai a destinazione e ti segni il risultato.
Dopo torni indietro al "branch" precedente e scegli la seconda alternativa migliore e prosegui con l'algoritmo anche per questa seconda strada. Se ottieni un risultato finale migliore aggiorni la best route.
Ora, secondo me, trovere una soluzione "ottima" con un numero di iterazioni basse è impossibile, perchè dovresti testarle tutte. L'algoritmo greedy però ti permette di raggiungere un risultato buono (magari ottimo) prefissando un numero di route ragionevolmente basso: tipo decidi di fare una decine di possibili rotte e poi ti fermi.