Search not working for river crossing problem in python

Question

The problem of the river crossing description: We have a farmer, a wolf, a goat and a cabbage and they need to cross the river with the following restrictions:

1. The wolf can’t be on the shame side with the goat
2. The goat can’t stay at the same side with the cabbage
3. -Initial state: (‘L’,‘L’,‘L’,‘L’)
4. -Finale state: (‘R’,‘R’,‘R’,‘R’)
   The state list describes where everyone is, (farmer, wolf, goat, cabbage) so state(‘L’,‘R’,‘L’,‘R’) means that the wolf and the cabbage are on the right side and the farmer and the goat are on the left side of the river. I don’t want to make it more complex by implementing list of lists.

Answer 1

The Farmer Problem

I'm going to approach your problem from a different angle. Instead of debugging your problem I've solved it in a step-by-step method that has tests as we go.

The setup and rules

First lets define the situation and the rules

FARMER = 0
WOLF = 1
GOAT = 2
CABBAGE = 3

START_STATE = ['L','L','L','L']

def wolfRule(state):
    return state[FARMER] == state[WOLF] or state[WOLF] != state[GOAT]

assert( wolfRule(['L','L','L','L']) == True)
assert( wolfRule(['R','L','L','L']) == False)
assert( wolfRule(['R','L','R','L']) == True)

def goatRule(state):
    return state[FARMER] == state[GOAT] or state[GOAT] != state[CABBAGE]

assert( goatRule(['L','L','L','L']) == True)
assert( goatRule(['R','L','L','L']) == False)
assert( goatRule(['R','L','L','R']) == True)

def validRule(state):
    return wolfRule(state) and goatRule(state)

def winRule(state):
    return state == ['R','R','R','R']

assert( winRule(['L','L','L','L']) == False)
assert( winRule(['R','L','L','L']) == False)
assert( winRule(['R','R','R','R']) == True)

We have defined each rule, added some assert statements so we know they work, and when we run the above code we can be sure it all is good-to-go.

Generating moves

Part of the recursive search is to generate the next valid move. We will do this in two parts. The first just generates all possible moves, and the second part will filter out only the valid moves

def generateMoves(state):
    # The farmer moves to the other side and can bring 0 or 1 other things so long as it is on the same starting side
    for other in [FARMER, WOLF, GOAT, CABBAGE]:
        if state[FARMER] == state[other]:
            move = copy(state)
            move[FARMER] = 'L' if state[FARMER] == 'R' else 'R'
            move[other] = 'L' if state[other] == 'R' else 'R'
            yield move

assert( list(generateMoves(START_STATE)) == [['R','L','L','L'],['R','R','L','L'],['R','L','R','L'],['R','L','L','R']]  )

Again, we add a test to make sure it is doing what we expect when we generate some moves

def validMoves(state_list):
    return [ state for state in state_list if validRule(state)]

assert( list(validMoves(generateMoves(START_STATE))) == [['R','L','R','L']]  )

Indeed the only first valid move is for the farmer to move the goat!

Depth First Search

Now we do a depth first search, using a previous_states list to keep track of where we have been. This function only returns a winning answer.

def depthFirstSearch(state, previous_states):
    previous_states.append(state)
    if winRule(state):
        return previous_states
    for move in validMoves(generateMoves(state)):
        if move not in previous_states:
            result = depthFirstSearch(move, previous_states)
            if result is not None:
                return result
            previous_states.pop()
    return None

again, at least one test to make sure it is giving expected results

assert( depthFirstSearch(['L','R','L','R'],[]) == [['L','R','L','R'],['R','R','R','R']]  )

Final output

We run it

depthFirstSearch(START_STATE,[])

and get the solution!

[['L', 'L', 'L', 'L'],
 ['R', 'L', 'R', 'L'],
 ['L', 'L', 'R', 'L'],
 ['R', 'R', 'R', 'L'],
 ['L', 'R', 'L', 'L'],
 ['R', 'R', 'L', 'R'],
 ['L', 'R', 'L', 'R'],
 ['R', 'R', 'R', 'R']]