Misioneros y caníbales, en C

Porque no hay dos sin tres, después de resolver el puzzle de los misioneros y los caníbales en Ruby y volver a hacerlo en Perl, lo he implementado en C: miscan.c.

Para mi sorpresa me ha resultado más fácil y rápido de implementar que en Perl, aunque depurar los fallos ha sido más complicado (Segmentation fault y a tirar de gdb, claro :P).

Además he usado la GList de la librería glib2 para la parte del backtracking, por simplificar (me podría haber implementado una lista doblemente enlazada para el caso, pero seamos realistas... ahí no hay diversión :D).

Como siempre, tener acceso a bajo nivel a la memoria y punteros tiene ventajas e inconvenientes, pero además he podido confirmar dos cosas:

$ time ./misio_can.pl 
Resultado: 
M: 3 C: 3 |\____/ ~~~~~~~~~~| M: 0 C: 0
M: 2 C: 2 |~~~~~~~~~~ \____/| M: 1 C: 1
M: 3 C: 2 |\____/ ~~~~~~~~~~| M: 0 C: 1
M: 3 C: 0 |~~~~~~~~~~ \____/| M: 0 C: 3
M: 3 C: 1 |\____/ ~~~~~~~~~~| M: 0 C: 2
M: 1 C: 1 |~~~~~~~~~~ \____/| M: 2 C: 2
M: 2 C: 2 |\____/ ~~~~~~~~~~| M: 1 C: 1
M: 0 C: 2 |~~~~~~~~~~ \____/| M: 3 C: 1
M: 0 C: 3 |\____/ ~~~~~~~~~~| M: 3 C: 0
M: 0 C: 1 |~~~~~~~~~~ \____/| M: 3 C: 2
M: 1 C: 1 |\____/ ~~~~~~~~~~| M: 2 C: 2
M: 0 C: 0 |~~~~~~~~~~ \____/| M: 3 C: 3

real	0m0.043s
user	0m0.021s
sys	0m0.006s

$ time ./miscan 
Resuelto, 12 pasos:
M: 3 C: 3 |  \__/ ~~~~~~~~~  | M: 0 C: 0
M: 2 C: 2 |  ~~~~~~~~~ \__/  | M: 1 C: 1
M: 3 C: 2 |  \__/ ~~~~~~~~~  | M: 0 C: 1
M: 3 C: 0 |  ~~~~~~~~~ \__/  | M: 0 C: 3
M: 3 C: 1 |  \__/ ~~~~~~~~~  | M: 0 C: 2
M: 1 C: 1 |  ~~~~~~~~~ \__/  | M: 2 C: 2
M: 2 C: 2 |  \__/ ~~~~~~~~~  | M: 1 C: 1
M: 0 C: 2 |  ~~~~~~~~~ \__/  | M: 3 C: 1
M: 0 C: 3 |  \__/ ~~~~~~~~~  | M: 3 C: 0
M: 0 C: 1 |  ~~~~~~~~~ \__/  | M: 3 C: 2
M: 0 C: 2 |  \__/ ~~~~~~~~~  | M: 3 C: 1
M: 0 C: 0 |  ~~~~~~~~~ \__/  | M: 3 C: 3

real	0m0.003s
user	0m0.000s
sys	0m0.002s

Aparte de que es evidente que un programa en C es más rápido que uno en Perl (no me he podido resistir a hacer la comparación :D), y de que la canoa que he dibujado en C es más churro que la canoa en Perl; el resultado obtenido es distinto.

Las dos soluciones son válidas (recordamos que buscamos una solución culquiera), pero son claramente distintas. ¿Alguien sabe decirme por qué?