DaniWeb Forum Index > Software Development > C

Recursive Backtracking Search Problem

Please support our C advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Oct 2006

Posts: 18

Reputation: tehloki is an unknown quantity at this point

Solved Threads: 0

tehloki

Offline

Newbie Poster

Recursive Backtracking Search Problem

Nov 13th, 2007

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.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
#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;
}
#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;
}

•

Join Date: Dec 2006

Posts: 2,042

Reputation: Aia has much to be proud of

Solved Threads: 178

Aia

Offline

Postaholic

Re: Recursive Backtracking Search Problem

Nov 13th, 2007

Just something to think about it.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
/*
 * 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;
}
/*
 * 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;
}

Last edited by Aia; Nov 13th, 2007 at 6:57 pm.

"If it moves, tax it. If it keeps moving, regulate it, and if it stops moving, subsidize it" - Ronald Reagan

•

Join Date: Dec 2005

Posts: 5,850

Reputation: Salem has a reputation beyond repute

Solved Threads: 751

Salem

Offline

Void main'ers are DOOMed

Re: Recursive Backtracking Search Problem

Nov 13th, 2007

> 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.