Broken Path Detection
Haskell, 655 bytes

u%w=u!!w
r=zip[-1,0,1,1,1,0,-1,-1][-1,-1,-1,0,1,1,1,0]
g _[]_= -1
g i(e:l)x|x==e=i|1&gt;0=g(i+1)l x
l?x=g 0 l x
d _[]_ _=[]
d i(e:l)t v|i==t=v:l|1&gt;0=e:d(i+1)l t v
c=d 0
f n|all(==0).concat.q$n=n|1&gt;0=f$foldr(\p b-&gt;s b[k,m]p)n$k!m where
 h=length n-1
 e=mapM(\w-&gt;[0..w])[h,h]
 i!j=[[x,y]|[x,y]&lt;-e,x&gt;i-2&amp;&amp;x&lt;i+2&amp;&amp;y&gt;j-2&amp;&amp;y&lt;j+2]
 q o=[[sum[1|[x,y]&lt;-w!l,let
  u=(x-w,y-l)
  p=(w-x,l-y)in u/=p&amp;&amp;('1'==(o%w%l)%(r?u))/=('1'==(o%x%y)%(r?p))]|l&lt;-[0..h]]|w&lt;-[0..h]]
 v[x,y][a,b]|q n%x%y&gt;q n%a%b=[x,y]|1&gt;0=[a,b]
 [k,m]=foldr1 v e
 s w[x,y][a,b]|x==a&amp;&amp;y==b=w|'1'==w%x%y%(r?(a-x,b-y))=z '0'|'1'==w%a%b%(r?(x-a,y-b))=z '1'|1&gt;0=w where z u=c w x$c(w%x)y$c(w%x%y)(r?(a-x,b-y))u


Man... 655 is a lot. I'm sure this isn't the best approach but since no one's answered this challenge yet I figured I would throw something at it.

Input is a list of lists of strings, viz. [[String]] or, equivalently, [[[Char]]]. The string format is "76543210", where the string is a '0' or a '1' in any given position based on whether or not the node points in that corresponding direction. This should conform with the spec:


  7 represents the most significant bit, and 0 the least significant; in other words, the bits are given in the order 76543210.


But the examples below that seem to contradict it, instead doing something more like ?7654321, so I'm not sure.

Test suite:

main :: IO ()
main = print $ f
    [ ["00000100", "00010000", "00000000"]
    , ["00000001", "10000000", "00010000"]
    , ["00000000", "00000000", "10000001"]
    ]


(That's the last test case in the spec^)