Recursive Backtracking Search Problem

[tehloki]

I have to use a recursive backtracking search to solve the classic "bucket" problem. ie. You have two buckets, one holds 5L, the other 3L. Find a way to get 4L into the 5L bucket, while only being able to fill/empty either bucket, or to pour one of them into the other one.

The solution to this problem is easy to find, the problem is writing the search. So far, my code seems to try various combinations of instructions, and then exits without finding or printing the solution.

It is in "debug mode", printing out each step and the status after completion, so you'll have to hit enter to step through the instructions.

Any help or advice would be greatly appreciated.

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

struct step
{
	int b3;
	int b5;
	int stype;
};

int fill_3(int *bucket)
{
	*bucket=3;
	return 1;
}

int fill_5(int *bucket)
{
	*bucket=5;
	return 2;
}

int empty_3(int *bucket)
{
	*bucket=0;
	return 3;
}

int empty_5(int *bucket)
{
	*bucket=0;
	return 4;
}

int pour_3_into_5(int *three, int *five)
{
	int poured;
	int overflow;
	
	poured = *three;
	
	*three -= poured;
	*five += poured;
	
	overflow=(*five-5);
	
	if (overflow>0)
	{
		*five -= overflow;
		*three += overflow;
	}
	return 5;
}

int pour_5_into_3(int *five, int *three)
{
	int poured;
	int overflow;
	
	poured = *five;
	
	*five -= poured;
	*three += poured;
	
	overflow=(*three-3);
	
	if (overflow>0)
	{
		*three -= overflow;
		*five += overflow;
	}
	return 6;
}

void print_state(int three, int five)
{
	printf("-----------------------------\nBucket 3 holds: %dL\nBucket 5 holds: %dL\n",three,five);
}

void print_step(int stype)
{
	switch(stype)
	{
		case 1:
			printf("\nFill bucket 3\n");
			break;
		case 2:
			printf("\nFill bucket 5\n");
			break;
		case 3:
			printf("\nEmpty bucket 3\n");
			break;
		case 4:
			printf("\nEmpty bucket 5\n");
			break;
		case 5:
			printf("\nPour bucket 3 into bucket 5\n");
			break;
		case 6:
			printf("\nPour bucket 5 into bucket 3\n");
			break;
	}
}

void print_solution(struct step *s, int *position)
{
	int x;
	
	printf("\nSOLUTION\n");
	printf("--------");
	
	for (x=0; x<=*position; x++)
	{
		print_step(s[x].stype);
	}
}

void find_solution(int *b3, int *b5, int *position, struct step *s)
{
	int i,x;
	char *dummy;
	
	int found=0;
	
	int temp3,temp5;
	
	temp3=*b3;
	temp5=*b5;

	for (i=1; i<=6; i++)
	{
		switch(i)
		{
		case 1:
			temp3=*b3;
			temp5=*b5;
			fill_3(&temp3);
			if (temp5==4)
			{
				print_solution(s,position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}
		case 2:
			temp3=*b3;
			temp5=*b5;
			fill_5(&temp5);
			if (temp5==4)
			{
				print_solution(s, position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}
		case 3:
			temp3=*b3;
			temp5=*b5;
			empty_3(&temp3);
			if (temp5==4)
			{
				print_solution(s, position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}
		case 4:
			temp3=*b3;
			temp5=*b5;
			empty_5(&temp5);
			if (temp5==4)
			{
				print_solution(s, position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}
		case 5:
			temp3=*b3;
			temp5=*b5;
			pour_3_into_5(&temp3,&temp5);
			if (temp5==4)
			{
				print_solution(s, position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}
		case 6:
			temp3=*b3;
			temp5=*b5;
			pour_5_into_3(&temp5,&temp3);
			if (temp5==4)
			{
				print_solution(s, position);
				print_step(i);
				printf("------------------\n");
				return;
			}
			print_step(i);
			print_state(temp3, temp5);
			scanf("%c",dummy);
			
			found=0;
			for (x=0; x<*position; x++)
			{
				if((s[x].b3==temp3)&&(s[x].b5==temp5))
				{
					found=1;
					continue;
				}
			}
			
			if (!found)
			{
				s[*position].b3=temp3;
				s[*position].b5=temp5;
				(*position)++;
				*b3=temp3;
				*b5=temp5;
				find_solution(b3,b5,position,s);
			}else{		
				break;
			}	
		}
	}

}

int main()
{
	int b3=0;
	int b5=0;
	/*int stemp;*/
	
	struct step s[1000];
	
	int position=0;
	
	find_solution(&b3,&b5, &position, s);

	return 0;
}

[Aia]

Just something to think about it.

/*
 * bleh.c
 */
#include <stdio.h>

int main ( void )
{
	int i;
	
	for ( i = 1; i <= 6; i++ )
	{
		switch( i )
		{
			case 1:
				puts( "One here, and two's coming right up" );
				break;
			case 2:
				puts( "Two here, and three's coming very soon" );
				break;
			case 3:
				puts( "Three here, and four is at the corner" );
				break;
			case 4:
				puts( "Four reporting in, and I met five coming up stairs" );
				break;
			case 5:
				puts( "Five is present, and six is at the door" );
				break;
			case 6:
				puts( "Six ready, and default will never happen" );
				break;
			default:
				puts( "I work in secret ways" );
				break;
		}
	}
		getchar();
		return 0;
}

[Salem]

> char *dummy;
Well you're spraying random data all over memory with your scanf calls, so the code is broken before it's begun.

Is it me, or is every single case of your find_solution() identical, except for one line?
Consider simplifying the code if this is the case.

You're also ignoring all the return results of all your 'fill' and 'empty' functions. If you really don't need them, then make them all void.