Are problems like the fox chicken and grain NP problems?

If I understand your question, you can solve the FCG problem without exploring every possible combination.

For example, CCCCCCCCCCCC…FGFCF…CCCCC is one possible (incorrect) solution that would only be run by a very poor program. Long before that solution had been tested, you’d have the solution.

The answer is rather easy to test as the process requires a finite number of possible steps:
1. If the chicken is left with the grain, it eats the grain
2. If the fox is left with the chicken, it eats the chicken.
3. If the fox is left with the grain, nothing happens.

The solution becomes obvious:
1. You take the chicken across and leave it.
2. You take the fox across and pick up the chicken.
3. You take the grain across and leave the chicken.
4. You take the chicken across.

See this for more information.

For this particular problem, all the moves are forced. There is no other choice. The tricky part is to take the grain back as an intermediate step. River crossing problems can be rather tricky and the general complexity just might be NP. Have you tried the Japanese river crossing problem?

I should have said taking the chicken back.

There is an interesting feature of both the FCG and the Japanese problem that most people are probably unaware of. If, after you solve the problem, you do all the moves in reverse, you have what appears to be a second solution. However, this is not really another solution due to the symmetry in these problems.

In the FCG problem, the fox and the grain are equivalent. They can be left alone together and neither can be left alone with the chicken. If you run the problem in reverse, you get the original solution with the fox and grain exchanging roles.

In the Japanese problem, exchanging genders of the parents and children gives another equivalence. This exchange is what you get by running the solution in reverse.

Knowing this symmetry can aid in the solution to these problems. For example, in the FGC problem, there is a point where the farmer and the chicken and either the fox or grain are on one side. If at this point you did everything in reverse you would end up with the initial problem. Let’s call this reverse sequence of moves S. If the farmer crosses at this point with the chicken, we have a position that is symmetric to the previous one. Doing S but changing the direction of movement and swapping roles of grain and fox will solve the problem. The same technique holds for the Japanese problem, though it is a little trickier.

I don’t think this question (as phrased) makes sense. NP problems are more generic. Any problem with a fixed solution is not NP-hard (or anything else).

You can try to create a “generic” version of the problem and ask if that is NP-hard but I can’t think of one.

Back in the day when Microsoft was growing rapidly and engineers were flocking to work there, Microsoft was said to have come up with tons of questions like these to test job applicants and their ability to think on their feet and to solve problems. The questions were a lot harder than the fox-chicken-grain problem. At one time there was even a web site that published many of these types of problems, but I lost track of it. If anyone has a link to this Microsoft-job-test-question web site, can you please provide it? Hopefully it still exists.

An NP problem must have a variable number of parameters. It is the time required to find a solution as a function of the number of inputs that determines whether a problem is NP or not. An example is the travelling salesman problem which increases in difficulty with the number of cities the salesman is required to visit.

I did a search and found this article that relates such problems to digraphs. You have to go down to page 108 to see the discussion of river crossing puzzles. I have not had a chance to read the article, but it seems to suggest that such problems can be generalized. I will also have to read the article to determine if the solution is of polynomial length complexity.

While I was searching, I came across this article that talks about sliding block puzzles, which the article says may go beyond NP.

Thanks guys

I’ve work out out.

I just needed to created a hyper dimensional cube depending on how many things you need to get across, this cube does not have to be topologically correct.
Giving each item it’s own vector in the hyper cube

Then I’d created more line with no rotational summitry so that would be the same as taking many items at once, then removed all the line that would violate the rules such as can’t move person or cabbage when fox = goat

then just followed the line to the end

@inunsure Can you explain that a bit more precisely? I’m not able to follow.

http://imageshack.us/photo/my-images/805/goatcarrot.png/
Give each item it’s own vector like this

http://imageshack.us/photo/my-images/856/goatcarrot.png/
Create a square using these vectors 0,0,0 is the starting point and 1,1,1 the end point. When an object is at 0 on its scale it’s on the first side and 1 when its at the other side

Now the part on having lines with no rotational symmetry with respects to 1,1,1 is hard to explain so just take my word on it. If you are just allowed to move 1 at a time you dont need to do that anyway.

Now remove the line that are not allowed
http://imageshack.us/photo/my-images/442/goatcarrot.png/
So if you follow this line it goes up what is the vector for goat so move go to other side. (Some lines mean you are moving things back and others mean you are going back to get something and then going back again it’s obvious what ones are what.) Then the line goes right meaning you go and get the fox and bring it back, then down so you bring the goat back, then on the z axis so you bring the carrot across to the second side, and then the line goes up so you bring the goat across.

If you do this for real it works.

Now if you have more than 3 items you will have to create a hyper cube, if Im not wrong you just double the vertexes compared to the dimension and the lines to each vertex goes up by one. you then pick a point and call it 0,0,0,0 what ever that one connects to it 1,0,0,0 or 0,1,0,0 and so on until you reach 1,1,1,1

That is nicely done. It can also be done in two dimensions. The fox and the carrot are equivalent, so you could think of it as moving a goat and two carrots.

@LostInParadise
That’s a nice way of putting it

@LostInParadise
Maybe you could also help me out in working out whats the maximum number of moves you’ll have to take to complete any n dimensional problem assuming it can be done.

I have a feeling it this but I dont know how to create an equation out of it.

so Imagine a cube, cut up all the vertexes so it can be laid into a straight line not cutting off any edges that cant be laid out straight with the other lines.

http://imageshack.us/photo/my-images/88/linet.png/
The red line in the square being one of the possible longest routes without back tracking or going round in circles.
The red line is the cube cut up with black edges coming out where it would not be possible to just cut the cube and have them all in a straight line

(n*2^n-1) -n

I think is the answer to the longest possible route but I cant seem to prove it

last bit was so wrong

Got it. But I think there is a problem with the representation, you are not representing the farmer. Remember, if the farmer is with the fox and the chicken its all good but if he goes away (even on an empty boat) that is a problem. So I think you need to add another dimension to your vector for the farmer.

That being said, there is a bigger problem here.

Lets say you four items x(1), ..., x(4). (Call this the n = 4 version). If left alone, x(a) eats x(a-1). (So in the original problem, the fox is x(3), the chicken is x(2) and the grain is x(1)).

Now, if the farmer takes any item across on the river, he loses right away. Why? Because either x(3) and x(4) are on the same side or x(3) and x(2) are on the same side or x(2) and x(1) are on the same side. No matter what, something gets eaten.

Another way to say this is that in the 4-cube, the point (0, 0, 0, 0) has no edges going out from it.

So, we need another parameter, c. c represents the capacity of his boat. If c = 2 this is easy. Take x(1) and x(3) across. Leave them there and come back. Then take x(2) and x(4) across. Done. That’s 3 crossings.

So with n = 4 and c = 1, no solution.
With n = 4 and c = 2, need 3 crossiings.

If n is even, and c = n/2, then you can always do it in 3 crossings.
1) Take x(1), x(3), ..., x(n-1).
2) Come back empty.
3)Take x(2), x(4), ..., x(n).
DONE

If n is even and c < n/2, you can’t do it. You will need to leave some pair x(a) and x(a+1) behind on your first crossing so you are dead.

If n is odd, you can do it with c = (n-1)/2. But it takes 7 crossings.
1) Take x(2), x(4), ..., x(n-1).
2) Come back empty.
3) Take x(1), x(3), ..., x(n-2)
4) Come back with x(2), x(4), ..., x(n-1).
5) Take x(n)
6) Come back empty.
7) Take x(2), x(4), ..., x(n-1).
DONE

If you work it through, you will see that each move is forced.

If n is odd and c > (n-1)/2, you can do it in 3 moves.
1) Take x(1), x(3), ..., x(n).
2) Come back empty.
3) Take x(2), x(4), ..., x(n-1).
DONE

Finally, of course, if c >= n, you can do it in one move.

To summarize
n even
> c < n/2—> impossible
> n/2 <= c < n—> 3 moves
> c >= n—> 1 move

n odd
> c < (n-1)/2—> impossible
> c = (n-1)/2—> 7 moves
> (n-1)/2 < c < n—> 3 moves
> c >= n—> 1 move

@roundsquare
Looks good I’m going to soak that all in soon as Im busy right now but the bits I have took in make sense to me

I’ve gone through your reply and it is good but I said how many moves it will take regardless of the rules. So it wont always be 4 will eat 3 and 3 will eat 2, so maybe only 4 will eat 3 but 3 wont eat 2.

@inunsure Sure, we can generalize more. In essence, if you are dealing with n objects, you have a bunch of sets of the form: {a, b} that can’t be left alone. You can represent this via a graph.

Any equation will need more than just n as a parameter. At the least, it will need c as well but I suspect it will need more. As shown above, not all problems will be solvable. If they are solvable, we can come up with some some (very broad) upper and lower limits.

Lower limit: 2 * ceiling(n/c) – 1. Why? Assume nothing eats anything else. You can take over c objects on each crossing and come back empty.

Upper limit: 2^(n+1). Why? There are n objects + the farmer. Each can be on either the left or right side of the river. So there are at most 2^(n+1) configurations. If you have take more than that many moves, you have repeated a state.

The lower bound is a tight lower bound (again, in the instance when no animal eats any other animal). I suspect the upper bound is not tight. For example, with 2 animals, you can’t force 8 moves. In fact, it will take at most 3. I’m not sure how to generalize that off the top of my head though.

Thanks you have been very helpful.

Try and work this out for me and I may be able to work it out.

Do you know of Euler circuits
http://curvebank.calstatela.edu/unimulticursal/evenforev.gif
Where they go can you draw this shape in one line without taking the pen off the paper or going over a line?

If they have 3 or more vertexes with an odd number of lines coming out from it it cant be done but can you work out the most amount of lines you can do with one with 3 or more vectors with an odd number of edges coming out?

actually that problem is a Hamilton path and is rock hard