Rick Dearman said:
Jeez! Has anyone noticed that in all the replies not one person
bothered to attempt to complete the puzzle only to spend their time
being critical of the "specification".
Fair enough. It would seem that there are no longer any programmers
here in comp.lang.c only a bunch of pedantic nit-pickers, more
concerned with telling people to go to another newsgroup for the
answer to the problem.
I would have been happy just to see the "printf" only solution
mentioned, at least that would have mean someone actually attempted it
and compiled it.
This problem can be solved using only ANSI C and you don't even have
to have a C99 compliant compiler to do it.
So lets see some C!!
My effort uses totally random attempts until it finds a solution by
accident. So it may not complete on your machine.
By redefining nedges and edges variables, I think you can define any sort of
network, but I haven't tried it.
Arrays here tend to be 1-based.
/* Solve cube puzzle */
#include <stdio.h>
#include <stdlib.h>
void movenext(void);
int finished(void);
#define nedges 12
char edges[nedges+1][2] ={{0,0},{'A','B'},{'B','C'},{'C','D'},{'D','A'},
{'E','F'},{'F','G'},{'G','H'},{'H','E'},
{'A','F'},{'B','G'},{'C','H'},{'D','E'}};
char cv; /* current vertex, eg. 'A' */
char cvhistory[1000];
int ncv; /* number of vertices in cvhistory */
char visited[nedges+1]; /* Number of visits along each edge */
int main (void) {
int i,j,k;
restart:
while (1) { /* Start new traversal */
cv='A'; /* Always start at A */
cvhistory[1]=cv; /* Reset vertex history */
ncv=1;
for (i=1; i<=nedges; ++i) /* Reset visited flags */
visited
=0;
while (1) { /* Start traversing edges */
movenext(); /* Step CV to new vertex */
j=finished();
if (j==1) exit(0); /* Finished */
if (j==2) goto restart; /* Error so start again. Can prob avoid
using goto but not at 2am... */
} /* End inner while */
} /* End outer while */
}
int finished(void) {
/* Return:
0: not yet finished (some edges not visited)
1: finished: path used is displayed here
2: error: one edge traversed too many times
*/
int i;
for (i=1; i<=nedges; ++i) {
if (!visited) return 0; /* Edge not visited */
if (visited>2) return 2; /* Error */
}
/* Finished, so show path */
puts("Solved:");
for (i=1; i<ncv; ++i) {
printf(" %c -> %c\n",cvhistory,cvhistory[i+1]);
}
return 1;
}
void movenext(void) {
/* Work out where to go next from vertex cv */
int i,j,n,r;
n=0; /* Count edges that involve cv */
for (i=1; i<=nedges; ++i) {
if (cv==edges[0] || cv==edges[1])
++n;
}
/* Get a vaguely random number 1..n */
r=(rand()%n)+1;
/* Now choose the r'th edge that involves cv */
i=1;
j=0;
while (1) {
if (cv==edges[0] || cv==edges[1]) {
++j;
if (j==r) { /* Use this edge */
if (cv==edges[0]) /* Use opposite vertex */
cv=edges[1];
else
cv=edges[0];
cvhistory[++ncv]=cv; /* Remember new vertex */
++visited; /* And this visit to edge */
return;
}
}
++i;
if (i>nedges) i=1; /* Wrap (may be needed when r too high?) */
}
}