Welcome! Log In Create A New Profile

My Missionary and Cannibals Code

Announcements		Last Post
	SoC Curricula	09/30/2017 01:08PM
	Demarcation or scoping of examinations and assessment	02/13/2017 07:59AM
	School of Computing Short Learning Programmes	11/24/2014 08:37AM
	Unisa contact information	07/28/2011 01:28PM

Forums Messages New

ilanpillemer

My Missionary and Cannibals Code
June 15, 2007 01:51PM

Registered: 18 years ago
Posts: 1,682
Rating: 0

Hi.. Here is how I solved the missionary and cannibals problem in C.

It uses breadth first through a FIFO Queue. The Queue does not accept repeated states (to avoid infinite loops). The Queue stores nodes of the search tree; and so when a solution is found it can print out the solution by tracing back up the tree to the first node. This lends itself to a recursive display algorithm.

#include <stdio.h>
#define L 1
#define R 0

char* boatpos(int boat);
void * malloc (size_t n);

struct 
{
  int c;
  int m;
  int boat;
} typedef worldstate;

struct
{
  worldstate state;
  void * parent;
  void * next;
} typedef node;



worldstate  suc1(worldstate);
worldstate  suc2(worldstate);
worldstate  suc3(worldstate);
worldstate  suc4(worldstate);
worldstate  suc5(worldstate);


void push(worldstate state, node * current);
node * solve(worldstate init, node * parent);
node * front; 
node * back;
node * begin;
void showsolution(node * solution);

int main()
{ 
  
  worldstate init;		/* set initial state */
  init.c = 0;
  init.m = 0;
  init.boat = R;
 
  node * solution;
  
  if (solution = solve(init,NULL))
    {
      
      printf("Solution to Missionary and Cannibals Problems\n";
      printf("CM[LR] - C is #Cannibals M is #Missionaries [LR] is bank with boat..\n";
      printf("For initial state 00R and Goal State 33L\n\n"; 
      
      showsolution(solution);
    }
  else
    printf("no solution.\n";
  
  node * cleanup = begin;
  while (cleanup != NULL)
    {
      node * tmp;
      tmp = cleanup;
      cleanup = cleanup->next;
      free(tmp);
    }
}

void showsolution(node * solution) /* Recursive diplay of solution as
				      it has the unwound from the
				      solution */
{
  if (solution->parent != NULL)
    showsolution(solution->parent);
  printf("%d%d%s\n",(solution->state).c,(solution->state).m,boatpos((solution->state).boat));
}

char* boatpos(int boat)
{
  char * retval = (char *) malloc(2); 
  retval[0] = boat ? 'L' : 'R';
  retval[1] = '\0';
  return retval;
}

int forbidden(worldstate current) {
  if 
    ((current.c > current.m && current.m != 0)
     ||
     (current.m > current.c && current.m !=3)) {
    
    return 1;
  }
  return 0;
}

int goal(worldstate * current)
{
  if ((current->c == 3)   
      &&
      (current->m == 3)
      &&
      (current->boat == L))
    {
      return 1;
    }
  else
    return 0;
}




worldstate suc1(worldstate state)
{
  
  if (state.boat == L) {
    if (state.c > 0) {
      (state.c)--;
      state.boat = R;
    }
  }

  else if (state.boat == R) {
    if ((state.c) < 3) {
      (state.c)++;
      state.boat = L;
    }
  }
  
  return state;
}

worldstate suc2(worldstate state)
{
  
  if (state.boat == L) {
    if (state.c > 1) {
      (state.c)-=2;
      state.boat = R;
    }
  }
  
  else if (state.boat == R) {
    if ((state.c) < 2) {
      (state.c)+=2;
      state.boat = L;
    }
  }
  
  return state;
  
}

worldstate suc3(worldstate state)
{
  
  if (state.boat == L) {
    if (state.m > 0) {
      (state.m)--;
      state.boat = R;
    }
  }
  
  else if (state.boat == R) {
    if ((state.m) < 3) {
      (state.m)++;
      state.boat = L;
    }
  }
  return state;
}

worldstate suc4(worldstate state)
{
  if (state.boat == L) {
    if (state.m > 1) {
      (state.m)-=2;
      state.boat = R;
    }
  }
  
  else if (state.boat == R) {
    if ((state.m) < 2) {
      (state.m)+=2;
      state.boat = L;
    }
  }
  
  return state;
}


worldstate suc5(worldstate state)
{
  
  if (state.boat == L) {
    if ((state.m > 0) && (state.c > 0)) {
      (state.m)--;
      (state.c)--;
      state.boat = R;
    }
  }
  
  else if (state.boat == R) {
    if ( (state.m) < 3  && (state.c)< 3 ) {
      (state.m)++;
      (state.c)++;
      state.boat = L;
    }
  }
  
  return state;
}

int empty();
node * dequeue();
node * solve(worldstate state, node * parent)
{
  
  push(state , parent);	
  if (goal(&(front->state)))
      return front;
  else
    {
      
      while (!empty()){

	if (goal(&(front->state)))
	  return front;
	else { 
	  
	  if (!forbidden(suc1(front->state))) push(suc1(front->state), front);
	  if (!forbidden(suc2(front->state))) push(suc2(front->state), front);
	  if (!forbidden(suc3(front->state))) push(suc3(front->state), front);
	  if (!forbidden(suc4(front->state))) push(suc4(front->state), front);
	  if (!forbidden(suc5(front->state))) push(suc5(front->state), front);
	  
	}
	dequeue();	 
      }
    }
  
}


node * dequeue()
{
  front=front->next;
  return front;
}

int empty() {
  return (front==NULL)?1:0;
}


int equals(worldstate lhs, worldstate rhs);
void push(worldstate state, node * parent)
{
  
  /* Check if state has already been added.... if so do not add. */
  node * t;
  for(t=begin;t!=NULL;t=t->next)
    if (equals(state,t->state)) return;
  
  node * new = (node *) malloc(sizeof(node));
  (new->state).c=state.c;
  (new->state).m=state.m;
  (new->state).boat=state.boat;
  new->parent = parent;
  
  if (front == NULL && back == NULL) { 		/* Init */
    
    new->next = NULL;
    front = back = begin = new;
  }
  else
    {
      new->next = NULL;
      back->next = new;
      back = new;
    }
  
}

int equals(worldstate lhs, worldstate rhs)
{
  if ((lhs.c == rhs.c)   
      &&
      (lhs.m == rhs.m)
      &&
      (lhs.boat == rhs.boat))
    { 
      return 1;
    }
  else
    return 0;
  
}