Peg Solitaire Solver (using a graph and backtracking)

peg_solitaire.c

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

typedef struct {
	int a;
	int w;
	void *next;
} *List;

typedef struct {
	int n;
	List *v;
	int *b;
} *Graph;

List NewEl (int a, int w, void *next) {
	List l;
	l = malloc (sizeof(*l));
	l->a = a;
	l->w = w;
	l->next = next;
	return l;
}

Graph NewGraph (int n) {
	int i;
	Graph g;
	g = malloc (sizeof(*g));
	g->n = n;
	g->v = malloc (g->n*sizeof(List));
	g->b = malloc (g->n*sizeof(int));
	for (i=0;i<g->n;i++) {
		g->v[i] = NULL;
		g->b[i] = 1;
	}
	return g;
}

void NewEdge (Graph g, int a, int b, int v) {
	List l;
	l = g->v[a];
	g->v[a] = NewEl(b,v,g->v[a]);
	g->v[b] = NewEl(a,v,g->v[b]);
}

int EdgeValue (Graph g, int a, int b) {
	List l;
	for (l=g->v[a];l!=NULL;l=l->next) {
		if (l->a==b) {
			return l->w;
		}
	}
	return -1; 
}

int visit (Graph g, int c) {
	int i,*v,j,ev,*n;
	List l;
	// Only one marble left
	if (c==1) {
		return 1;
	}
	for (i=0;i<g->n;i++) {
		if (g->b[i]) {
			// This part of code is executed
			// when one of the marbles is available
			for (l=g->v[i];l!=NULL;l=l->next) {
				ev = l->w;
				j = l->a;
				// Check whether the spots that can be
				// reached are available (e.g. there's
				// an empty spot where the marble will
				// "land" and there's a marble between
				// the two spots.
				if (g->b[ev] && !g->b[j]) {
					g->b[i] = !g->b[i];
					g->b[ev] = !g->b[ev];
					g->b[j] = !g->b[j];
					if (visit (g,c-1)) {
						printf ("%d -> %d\n",i,j);
						return 1;
					}
					g->b[i] = !g->b[i];
					g->b[ev] = !g->b[ev];
					g->b[j] = !g->b[j];
				}
			}
		}
	}
	return 0;
}

int main () {
	Graph g;
	FILE *fp;
	char line[256];
	int a,b,v[3],i;
	fp = fopen ("input.txt","r");
	fgets (line,sizeof(line),fp);
	a = atoi (line);
	g = NewGraph (a);
	while (fgets (line,sizeof(line),fp)) {
		sscanf (line, "%d %d %d",&v[0],&v[1],&v[2]);
		NewEdge (g,v[0],v[2],v[1]);
	}
	g->b[10] = !g->b[10];
	visit(g,a-1);
	fclose (fp);
	return 0;
}

~input.txt

33
0 3 6
0 1 2
1 4 7
2 5 8
3 6 9
3 4 5
4 7 10
5 8 11
28 27 6
28 30 32
27 29 31
27 6 7
6 9 12
6 7 8
7 10 13
7 8 21
8 11 14
8 21 22
21 23 25
22 24 26
30 29 9
29 9 10
9 10 11
9 12 15
10 11 23
10 13 16
11 14 17
11 23 24
32 31 12
31 12 13
12 15 18
12 13 14
13 14 25
13 16 19
14 17 20
14 25 26
15 16 17
18 19 20

~output

4 -> 10
13 -> 7
19 -> 13
23 -> 10
5 -> 11
6 -> 8
0 -> 6
2 -> 0
9 -> 3
0 -> 6
10 -> 16
11 -> 5
15 -> 9
17 -> 15
18 -> 12
9 -> 15
22 -> 8
26 -> 22
27 -> 7
7 -> 21
22 -> 8
5 -> 11
11 -> 17
20 -> 14
25 -> 13
32 -> 12
13 -> 31
28 -> 32
32 -> 12
15 -> 9
9 -> 30