Because I'll be away for a few days I decided to make a suggestion despite it being unfinished (it'd not efficient; there are many references to the sheet and ranges whereas I should really be using in-memory arrays throughout).
In the attached, in cell G8, is a number you can adjust; it causes the macro to pause every n iterations, draw the path at that point, and ask if you want to carry on.
Since the output includes all combinations including all lengths of the path, there's a hell of a lot of them.
Results are written to the sheet at cell A10 and below. This area is never erased by the macros so you'll need to it manually.
Plenty of comments in the code.
Realise, that although you didn't want stuff written for you, it takes an awful lot more effort to try and take you step by step in a tutorial type process, so perhaps the graphic portion of what I have written will help you through the logic; it did me.
p45cal Everyone: If I've helped and you can't be bothered to acknowledge it, I can't be bothered to look at further posts from you.