Backtracking

[zeroblank]

im solving this puzzle using Backtracking kinda of a practice ,however, i dont seem to understand some parts of this concept so i would really use some help with this one here .

#include<iostream>

using std::cout;
using std::endl;


bool check(int *river ,int * bank,bool watch)
{
    for(int i  = 0 ; i < 2 ; i++)
    {
        if(((river[i] && river[i+1] )|| (bank[i] && bank[i+1])) && !watch)
        {
            return true;
        }
    }
    return false;
}

bool solve(int * river , int * bank , int D)
{
    if(D == 3)
    {
        return true;
    }
    else
    {
        for(int i = 0 ; i < 3 ; i++)
        {
            if(river[i] != 0)
            {
                bank[i] = river[i];
                river[i] = 0;
                int Di = D+1;
                bool x;
                if(Di > 1)
                {
                    x= check(river , bank , 1);
                }
                else 
                {
                    x = check(river,bank , 0);
                }
                if(x)
                {
                    river[i] = bank[i];
                    bank[i] = 0;
                }
                else
                {
                    if(solve(river , bank , Di))
                    {
                        cout<<bank[i]<<endl;
                        return true;
                    }
                    else
                    {
                        river[i] = bank[i];
                        bank[i] = 0;
                    }
                }
            }
        }
    }
    return false;
}

int main()
{
    int river[3] = {1,2,3};
    int bank[3] = {0,0,0};
    solve(river,bank,0);
}

here are my questions :-
-the code works to find one solution how can i make it proceed to find out next solutions ?
-Line 53 if i remove the return true statement , i only get the output of the current function im in and not the other , could someone tell me why ?


just in case here is the puzzle , i used 1 2 3 as the rice sheep and wolf

A man finds himself on a riverbank with a wolf, a goat, and a head of
cabbage. He needs to transport all three to the other side of the river in
his boat. However, the boat has room for only the man himself and one
other item (either the wolf, the goat, or the cabbage). In his absence, the
wolf would eat the goat, and the goat would eat the cabbage. Show how
the man can get all these “passengers” to the other side

[dhayden]

the code works

Does it? When I run it, The output I get is:

3
1
2

What does that mean? I see it must be in reverse order, so the man transports item 2 (the sheep) to the far bank, then... returns for item 1 (the cabbage). And then returns again for the wolf? But during the return, the sheep eats the cabbage.

I think you've missed the point of the problem. Something might eat something else on either bank of the river.

Your check() function looks bad. If watch is true then it always returns false. What is watch supposed to represent?

[doug4]

Before you figure out why your backtracking doesn't work, you need to analyze your code and understand what you are telling the computer to do. I'm not sure you have things quite correct.

First of all, decide if you are going to use the terminology wolf-sheep-rice or wolf-goat-cabbage. It's the same problem, but mixing terminology can confuse things.

Next, you should create an enum for each of these players. It should be
enum Player {MAN, WOLF, GOAT, CABBAGE, NUM_PLAYERS};. (If you end up needing a value indicating "empty", add "NONE" to the beginning of the enum values, but that's not how I see this problem working itself out.)

Look at how you defined your data structures in lines 69 and 70. Line 69 is basically saying "I've got 3 spots in the river, and they currently are occupied by the cabbage, goat and wolf. That's not actually what you want. What you were trying to do here was create a boolean value indicating that the player in question is on the river. So line 69 should be bool river[NUM_PLAYERS].

I think even better would be to create a second enum: enum Location{ORIG_BANK, RIVER, FINAL_BANK}; and then declare an array of the locations of each of the players as such:

Location currentLocation[NUM_PLAYERS];
for (int i = 0; i < NUM_PLAYERS; ++i)
{
	currentLocation[i] = ORIG_BANK;
}

Then your check function only needs to determine if 2 adjacent players are in the same location and the man is not there.

You need to realize that each trip across the river is 2 step. In the first, the man and 0 or 1 other players are on ther river. In the second, the man and the other player are on the other bank.

When you get that logic worked through, you can tackle the backtracking part of the problem. Unfortunately, I've got to get back to work, so that's all I have time to help you with today.

[dhayden]

Doug4, I think he can actually get by with a boolean that says which bank the player is on:
bool onOrigBank[NUM_PLAYERS];