Backtracking in a adjacency matrix in C?

Question

I'm trying to find all the paths between node 1 and node 12. The only restriction is that I cannot traverse any path between two nodes more than once. Currently, my program just works in the forward direction. I need to consider paths such as 1 > 2 > 5 > 3 > 2 > 6 > 8 > 11 > 12, where the program travels back to a node. The counter is just there to count the number of paths available (there should be 640 total paths, but I only have 16 paths). This is what I have so far. Any ideas?

#include <stdio.h>

int edges[12][12] = {
    {0,1,0,0,0,0,0,0,0,0,0,0},
    {1,0,1,1,1,1,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,1,1,0,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,1,0},
    {0,0,0,0,1,1,0,0,1,1,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,1,1,1,1,0,1},
    {0,0,0,0,0,0,0,0,0,0,1,0}
};


int visited[12] = {0,0,0,0,0,0,0,0,0,0,0,0};

int counter = 0; 


struct Node {
    int node;
    struct Node *prev;
};


void visit (int node, struct Node *prev_node) { 
    struct Node n = { node, prev_node };
    struct Node *p = &n;
    if (node == 1){
        printf("%s", "1->");
    }
    if (node == 1){
        do 
            printf ("%d%s", p->node + 1, (p->prev != 0)?  "->" : "\n");
        while ((p = p->prev) != 0);
    }
    if (node == 1){
        counter++; 
        printf("%d\n", counter);
    }

    visited[node]=1;
    int i;
    for (i=0; i<12; ++i){
        if ((visited[i] == 0) && (edges[node][i] == 1))
            visit (i, &n);
            visited[node]=1;
    }
    visited[node]=0;

}


int main (int argc, char *argv[]) {

    int i;
    for (i=11; i<12; ++i) {
        visit (i, 0);
    }
    return 0;
}

Answer 1

The biggest error was that your requirement is to visit each edge a maximum of once, but you were tracking nodes.

Also, I recommend always using {} braces after your ifs, whiles, etc. You have some misleading whitespace in your post.

GCC 4.7.3: gcc -Wall -Wextra backtrace.c

#include <stdio.h>

int edges[12][12] = {
    {0,1,0,0,0,0,0,0,0,0,0,0},
    {1,0,1,1,1,1,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,1,1,0,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,1,0},
    {0,0,0,0,1,1,0,0,1,1,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,1,1,1,1,0,1},
    {0,0,0,0,0,0,0,0,0,0,1,0}
};

int visited[12][12] = {
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0}
};

int counter = 0;


struct Node {
    int node;
    struct Node *prev;
};

void print(struct Node* p) {
    do
        printf ("%d%s", p->node + 1, (p->prev != NULL)?  "<-" : "\n");
    while ((p = p->prev) != NULL);
    printf("%d\n", ++counter);
}

void flag(int i, int j) {
  visited[i][j] = visited[i][j] ? 0 : 1;
  visited[j][i] = visited[j][i] ? 0 : 1;
}

void visit (int first, int last, struct Node *prev_node) {
    struct Node n = { first, prev_node };

    if (first == last){ print(&n); return; }

    int i;
    for (i=0; i<12; ++i){
        if ((visited[first][i] == 0) && (edges[first][i] == 1)) {
            flag(first, i);
            visit(i, last, &n);
            flag(first, i);
        }
    }
}


int main (int argc, char *argv[]) {

    visit (0, 11, NULL);
    return 0;
}

Answer 2

There was a previous version of this question as Finding all the paths in an adjacency matrix in C that has now been deleted by Ace (but 10K users can still see it). It was the same problem, though. Here's a different solution from Adam's, mainly posted because I'm stubborn and spent time on it. It finds the 640 solutions that were required. It is more verbose than Adam's solution, but the issue fixed is the same — tracking the edges used rather than the nodes visited.

It takes one command line option, -v, to be more verbose in its output (very verbose!). It prints the solutions forwards rather than backwards. It identifies the edges and reports the edges traversed in the output. It doesn't use global variables for the main data structures. I managed to go through some complex red herrings and I probably haven't removed everything. Since some of the arrays are VLAs (variable length arrays), they cannot be initialized statically, so there are functions to do that initialization (not complex, just code — and yes, memset() could be used too or instead). The chk_array_properties() function ensures that the array is symmetric and has zeros on the leading diagonal. The prt_links() function is not necessary; it gives a simple print of the connections in the matrix.

Network diagram

Time for some ASCII Art — what does the network really look like? (Transferred from my previous answer.)

         +------ 3 ---+
         |            |
         | +---- 4    |
         |/       \   |
1 ------ 2         \  |
         |\         \ |
         | +--------- 5 --------- 7 --------+ 
         |             \                    |
         |              \   +------------+  |
         |               \ /              \ |
         +------ 6 ------ 8 ------ 9 ------ 11 ------ 12
                           \                |
                            +----- 10 ------+

Allowing for revisiting a node N as long as you do not enter from a node (along an edge) that was already used to get to N, and therefore leaving N to a node not already used to get from N, there is some possibility of there being 640 paths in this matrix.

For example, if you're allowed to visit a node several times by different paths, then you can have:

1 ⟶ 2 ⟶ 4 ⟶ 5 ⟶ 3 ⟶ 2 ⟶ 6 ⟶ 8 ⟶ …
1 ⟶ 2 ⟶ 4 ⟶ 5 ⟶ 2 ⟶ 6 ⟶ 8 ⟶ …
1 ⟶ 2 ⟶ 3 ⟶ 5 ⟶ 2 ⟶ 6 ⟶ 8 ⟶ …
1 ⟶ 2 ⟶ 3 ⟶ 5 ⟶ 4 ⟶ 2 ⟶ 6 ⟶ 8 ⟶ …
1 ⟶ 2 ⟶ 6 ⟶ 8 ⟶ 5 ⟶ 3 ⟶ 2 ⟶ 4 ⟶ 5 ⟶ 7 ⟶ 11 ⟶ 8 ⟶ 10 ⟶ 11 ⟶ 12

The longest paths seem to be of length 16 (2 hops longer than the full path above). Of course, there are many permutations of those paths. The distribution of the lengths (number of nodes visited) is:

Length Number
  6    3
  7    8
  8    5
  9    8
 10   44
 11   56
 12   12
 13   48
 14  236
 15  176
 16   44

Code

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

struct Node
{
    int node;
    int edge;
    struct Node *prev;
};

static int vflag = 0;
static int num_solutions = 0;

static void prt_fwd_path_r(struct Node *p)
{
    char *pad = "";
    if (p->prev != NULL)
    {
        prt_fwd_path_r(p->prev);
        pad = " ->";
    }
    printf("%s N%d (E%d)", pad, p->node + 1, p->edge);
}

static void prt_fwd_path(struct Node *p)
{
    prt_fwd_path_r(p);
    putchar('\n');
}

static void visit2(int node, struct Node *prev_node, int size, int edges[size][size], int end, int *traversed)
{
    struct Node n = { node, 0, prev_node };
    struct Node *p = &n;

    if (vflag) printf("-->> %s (%d)\n", __func__, node);
    if (node == end)
    {
        printf("Solution %d: ", ++num_solutions);
        prt_fwd_path(p);
    }
    else
    {
        if (vflag) prt_fwd_path(p);
        for (int i = 0; i < size; ++i)
        {
            int e = edges[node][i];
            if (e != 0 && traversed[e] == 0)
            {
                traversed[e] = 1;
                n.edge = e;
                visit2(i, &n, size, edges, end, traversed);
                traversed[e] = 0;
            }
        }
    }
    if (vflag) printf("<<-- %s\n", __func__);
}

static void chk_array_properties(char const *tag, int n, int a[n][n])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] != a[j][i])
                fprintf(stderr, "Broken symmetry: %s[%d,%d] = %d, %s[%d,%d] = %d\n",
                        tag, i, j, a[i][j], tag, j, i, a[j][i]);
        }
        if (a[i][i] != 0)
            fprintf(stderr, "Non-zero leading diagonal: %s[%d][%d] == %d\n",
                    tag, i, i, a[i][i]);
    }
}

static void prt_links(int size, int edges[size][size])
{
    int edge_num = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = i; j < size; j++)
        {
            if (edges[i][j])
                printf("%2d: %d -> %d\n", ++edge_num, i+1, j+1);
        }
    }
}

static int count_edges(int size, int edges[size][size])
{
    int count = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = i; j < size; j++)
        {
            if (edges[i][j])
                count++;
        }
    }
    return count;
}

static void dump_array(char const *fmt, int size, int edges[size][size])
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
            printf(fmt, edges[i][j]);
        putchar('\n');
    }
}

static void mark_matrix(int n, int paths[n][n], int nodes[n][n])
{
    int pathnum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            if (paths[i][j] == 0)
            {
                nodes[i][j] = 0;
                nodes[j][i] = 0;
            }
            else
            {
                pathnum++;
                nodes[i][j] = pathnum;
                nodes[j][i] = pathnum;
            }
        }
    }
}

static void zero_array(int n, int a[n][n])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            a[i][j] = 0;
    }
}

static void zero_vector(int n, int v[n])
{
    for (int i = 0; i < n; i++)
        v[i] = 0;
}

static void usage(char const *arg0)
{
    fprintf(stderr, "Usage: %s [-v]\n", arg0);
    exit(1);
}

int main(int argc, char **argv)
{
    enum { N = 12 };
    int paths[N][N] =
    {
        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
    };
    int opt;

    while ((opt = getopt(argc, argv, "v")) != -1)
    {
        switch (opt)
        {
        case 'v':
            vflag = 1;
            break;
        default:
            usage(argv[0]);
            break;
        }
    }
    if (optind != argc)
        usage(argv[0]);
    puts("Connections:");
    dump_array(" %2d", N, paths);
    chk_array_properties("paths", N, paths);

    int matrix[N][N];
    int nedges = count_edges(N, paths);
    int edges[nedges + 1];
    zero_array(N, matrix);
    zero_vector(nedges + 1, edges);
    mark_matrix(N, paths, matrix);
    puts("Edges numbered:");
    dump_array(" %2d", N, matrix);
    chk_array_properties("matrix", N, matrix);
    puts("Edges enumerated:");
    prt_links(N, matrix);
    visit2(0, NULL, N, matrix, N-1, edges);
    printf("%d Solutions found\n", num_solutions);

    return 0;
}

Partial output

Connections:
  0  1  0  0  0  0  0  0  0  0  0  0
  1  0  1  1  1  1  0  0  0  0  0  0
  0  1  0  0  1  0  0  0  0  0  0  0
  0  1  0  0  1  0  0  0  0  0  0  0
  0  1  1  1  0  0  1  1  0  0  0  0
  0  1  0  0  0  0  0  1  0  0  0  0
  0  0  0  0  1  0  0  0  0  0  1  0
  0  0  0  0  1  1  0  0  1  1  1  0
  0  0  0  0  0  0  0  1  0  0  1  0
  0  0  0  0  0  0  0  1  0  0  1  0
  0  0  0  0  0  0  1  1  1  1  0  1
  0  0  0  0  0  0  0  0  0  0  1  0
Edges numbered:
  0  1  0  0  0  0  0  0  0  0  0  0
  1  0  2  3  4  5  0  0  0  0  0  0
  0  2  0  0  6  0  0  0  0  0  0  0
  0  3  0  0  7  0  0  0  0  0  0  0
  0  4  6  7  0  0  8  9  0  0  0  0
  0  5  0  0  0  0  0 10  0  0  0  0
  0  0  0  0  8  0  0  0  0  0 11  0
  0  0  0  0  9 10  0  0 12 13 14  0
  0  0  0  0  0  0  0 12  0  0 15  0
  0  0  0  0  0  0  0 13  0  0 16  0
  0  0  0  0  0  0 11 14 15 16  0 17
  0  0  0  0  0  0  0  0  0  0 17  0
Edges enumerated:
 1: 1 -> 2
 2: 2 -> 3
 3: 2 -> 4
 4: 2 -> 5
 5: 2 -> 6
 6: 3 -> 5
 7: 4 -> 5
 8: 5 -> 7
 9: 5 -> 8
10: 6 -> 8
11: 7 -> 11
12: 8 -> 9
13: 8 -> 10
14: 8 -> 11
15: 9 -> 11
16: 10 -> 11
17: 11 -> 12
Solution 1:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E14) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)
Solution 2:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E14) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 3:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E15) -> N9 (E12) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 4:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E15) -> N9 (E12) -> N8 (E14) -> N11 (E17) -> N12 (E0)
Solution 5:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E16) -> N10 (E13) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)
Solution 6:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E16) -> N10 (E13) -> N8 (E14) -> N11 (E17) -> N12 (E0)
Solution 7:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 8:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E12) -> N9 (E15) -> N11 (E14) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 9:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E12) -> N9 (E15) -> N11 (E16) -> N10 (E13) -> N8 (E14) -> N11 (E17) -> N12 (E0)
Solution 10:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)
Solution 11:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E13) -> N10 (E16) -> N11 (E14) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)
Solution 12:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E13) -> N10 (E16) -> N11 (E15) -> N9 (E12) -> N8 (E14) -> N11 (E17) -> N12 (E0)
Solution 13:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 14:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 15:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)
Solution 16:  N1 (E1) -> N2 (E2) -> N3 (E6) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E9) -> N8 (E14) -> N11 (E17) -> N12 (E0)
...
Solution 624:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E4) -> N2 (E2) -> N3 (E6) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 625:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 626:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E6) -> N3 (E2) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 627:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E6) -> N3 (E2) -> N2 (E4) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 628:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E7) -> N4 (E3) -> N2 (E2) -> N3 (E6) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 629:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E7) -> N4 (E3) -> N2 (E4) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 630:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E9) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 631:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E15) -> N9 (E12) -> N8 (E13) -> N10 (E16) -> N11 (E17) -> N12 (E0)
Solution 632:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E4) -> N2 (E2) -> N3 (E6) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 633:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E4) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 634:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E6) -> N3 (E2) -> N2 (E3) -> N4 (E7) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 635:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E6) -> N3 (E2) -> N2 (E4) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 636:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E7) -> N4 (E3) -> N2 (E2) -> N3 (E6) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 637:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E7) -> N4 (E3) -> N2 (E4) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 638:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E9) -> N5 (E8) -> N7 (E11) -> N11 (E17) -> N12 (E0)
Solution 639:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E16) -> N10 (E13) -> N8 (E12) -> N9 (E15) -> N11 (E17) -> N12 (E0)

Solution 640:  N1 (E1) -> N2 (E5) -> N6 (E10) -> N8 (E14) -> N11 (E17) -> N12 (E0)
640 Solutions found