In Mathematica, we can use FindPath[graph, start, end, Infinity, All]
to find all self-avoiding paths, which means the path can not cross vertex and edge repeatedly.
Drawing code as follows:
v = Graphics[{GrayLevel[1], EdgeForm[RGBColor[0, 0, 0]], Disk[{0, 0}]}];
G4 = GridGraph[{4, 4}, VertexSize -> 0.2, VertexShape -> v, ImageSize -> 640, VertexLabels -> Table[i -> Placed[i, Center], {i, 16}]];
paths = FindPath[G4, 1, 16, Infinity, All];
ArrowedGraph[graph_, path_] := HighlightGraph[
graph, (*Rule@@@Partition[path,2,1]*){},
Prolog -> {Blue, Thickness[.003], Arrowheads[Table[.03, 15]], Arrow[BSplineCurve[GraphEmbedding[graph][[path]], SplineDegree -> 2]]}
]
ArrowedGraph[G4, RandomChoice@paths]
It can find all the 184 self-avoiding paths.
Edge self-avoiding path allow passes through the same point multiple times, but the edges cannot be repeated.
For example, the path {1, 5, 6, 7, 3, 2, 6, 10, 11, 12, 8, 7, 11, 15, 16}
is a legal edge self-avoiding path, but not a legal self-avoiding path.
How to find all such paths?