The boat can only carry the farmer and one load of goods at a time. The Wolf will eat the sheep, and the sheep will eat the grass. It is safe only when the farmer is around. Now want to make all items including farmers are safe passage across the river, using the program to achieve the solution.

2 Design analysis: Farmer, Wolf, sheep and grass are arranged in the order of “farmer, Wolf, sheep and grass”. A Boolean array is used to represent their states. The Boolean value state false represents that the corresponding person (object) has not crossed the river, and the state true represents that the corresponding person (object) has crossed the river. The advantage of using a Boolean value is that the current state can be reversed to get the state across the river (regardless of whether the river was crossed or not).

The initial state is: status[4] = [false, false, false, false]

A state change of status[4] array is used to represent the situation of river-crossing, so the river-crossing rule corresponds to the computer logic as: 1) Every time the river is crossed, the farmer needs to participate — every time the state changes, the 0 bit (note: 0 subscript begins to count) must be changed; 2) Only one item can be carried across the river at a time, and the farmer is required to punt the boat. Each time, the 1st, 2nd and 3rd position can only change one of them at most, and the change position must be synchronized with the 0 position. 3) If one of the three is the food of the other, it must be safe to have a farmer present. After each change, the first, second and third places must be the same as the 0 place if the neighboring places are the same.

According to this rule, an array is used as the root node of the current state to generate all the subsequent states, and then enumerate the subsequent cases to obtain a numeral-shaped state structure:

In this tree, the state to the right of the third layer (that is, the farmer brings the sheep there and then brings the sheep back) is the same as the root, so we can stop generating children. Other nodes, such as the right-most state at level 4, do not need to continue to generate (traverse) the subtree if they are the same as one of the parent nodes, because the subsequent state of this state is bound to repeat the previous state.

3 coding

Start with the flow chart:

According to the rules, to determine whether a state is safe (legal) – when one thing is food for another, if they are on the same side of the river, the farmer must be there. The code logic is as follows (Python code) :

def is_valid_status(status): if status[1] == status[2]: if status[0] ! Return False if status[2] == status[3]: if status[0]! = status[2]: # return False return TrueCopy the code

In the current state, the enumeration generates all cases for the next state, which is all possible cases for the next river crossing. To take the inverse of a state is to cross the river, whether it is past or back — take the inverse. The code logic is as follows:

def create_all_next_status(status): next_status_list = [] for i in range(0, 4): if status[0] ! = status[I]: # Continue next_status = [status[0],status[1],status[2],status[3]] Next_status [0] = not next_status[0] next_status[I] = next_status[0] next_status_list.append(next_status) return next_status_listCopy the code

 

Tree recursive traversal logic code steps roughly as follows, 1) based on the current state, generating all under a state of all cases, 2) to generate the status of the traverse all cases judgment, (1) if the next state is the final desired state (river), the output current path as a result, (2) if the next state has appeared in history, (3) If the next state is a new state, the state is recorded in history and the recursion enters step 1.

Here’s the search code, which is at the heart of tree recursive traversal logic (as an aside: board game recursive traversal logic is similar) :

def search(history_status): global scheme_count current_status = history_status[len(history_status) - 1] next_status_list = create_all_next_status(current_status) for next_status in next_status_list: if next_status in history_status: Continue history_status.append(next_status) if is_done(next_status): scheme_count += 1 print("scheme " + str(scheme_count) + ":") print_history_status(history_status) else: search(history_status) history_status.pop()Copy the code

It is easier to determine whether they have crossed the river:

def is_done(status):
    return status[0] and status[1] and status[2] and status[3]Copy the code

 

The complete code is as follows:

#-* -coding: utF-8 -* -name = ["farmer", "Wolf ", "sheep", "grass"] scheme_count = 0 # def is_done(status): Return status[0] and status[1] and status[2] and status[3] def create_all_next_status(status): next_status_list = [] for i in range(0, 4): if status[0] ! = status[I]: # Continue next_status = [status[0],status[1],status[2],status[3]] Next_status [0] = not next_status[0] next_status[I] = next_status[0] Append (next_status) return next_status_list def is_valid_status(status): if status[1] == status[2]: if status[0] ! Return False if status[2] == status[3]: if status[0]! Return False return True def search(history_status): global scheme_count current_status = history_status[len(history_status) - 1] next_status_list = create_all_next_status(current_status) for next_status in next_status_list: if next_status in history_status: Continue history_status.append(next_status) if is_done(next_status): scheme_count += 1 print("scheme " + str(scheme_count) + ":") print_history_status(history_status) else: Search (history_status) history_status.pop() def readable_status(status, is_across): result = "for I in range(0,4): if status[i] == is_across: if len(result) ! Def print_history_status(history_status) def print_history_status(history_status): for status in history_status: Print (readable_status (status, False) + "material material material material material material material material material material" + readable_status (status, True)) if __name__ = = "__main__" : Status = [False, False, False, History_status = [status] search(history_status) print(" Finish search, find " + str(scheme_count) + " scheme")Copy the code

5 Running Results

According to the output results, there are two cases:

Plan A: 1) The farmer brings the sheep 2) the farmer returns by himself 3) the farmer brings the Wolf 4) the farmer brings the sheep 5) The farmer brings the grass 6) The farmer returns by himself 7) the farmer brings the sheep