Wolf, Goat, and Cabbage Puzzle¶
In [1]:
import itertools
entities = ['Man','Wolf','Goat','Cabbage']
state = (1,1,1,1) # 0-1 list to indicate which entities are on the Start riverbank
goalstate = (0,0,0,0) # if entities are not on the Start riverbank, they are on the Final riverbank
In [2]:
# Helper function to print the current state tuple in readable text
def printState(State):
e = ' '.join(itertools.compress(entities,State))
print(e,end=" ")
print("\t|~~~| ".expandtabs(22-len(e)),end=" ")
opp = [(x+1)%2 for x in State]
e = ' '.join(itertools.compress(entities,opp))
print(e,end=" ")
print("\n")
In [3]:
printState(state)
In [4]:
printState(goalstate)
In [5]:
visited = set() # do not return to already visited states
visited.add(state)
In [6]:
# Helper function to perform logical AND on 0-1 tuples
def listAND(list1,list2):
return([a and b for a, b in zip(list1,list2)])
In [7]:
# Helper function to determine if state violates conflict rules
def validState(State):
if State[0]==1: # if State has Man, invert to opposite riverbank
State = [(x+1)%2 for x in State]
WGconflict = (0,1,1,0) # Wolf and Goat cannot be together without Man
GCconflict = (0,0,1,1) # Goat and Cabbage cannot be together without Man
if sum(listAND(WGconflict,State))==2 or sum(listAND(GCconflict,State))==2:
return False
else:
return True
In [8]:
# Return a set of all valid states that can be reached from the current state of the start riverbank
def candidateMoves(State):
candidates = set()
if State[0]==1:
# print("Man on start riverbank")
template=[0]+list(State[1:]) # all candidate moves will have the man on the final riverbank
newstate = template[:]
if validState(newstate) and tuple(newstate) not in visited:
candidates.add(tuple(newstate))
visited.add(tuple(newstate))
for i in range(1,4):
if template[i]==1:
newstate = template[:]
newstate[i]=0
if validState(newstate) and tuple(newstate) not in visited:
candidates.add(tuple(newstate))
visited.add(tuple(newstate))
return candidates
else:
# print("Man on final riverbank")
template=[1]+list(State[1:]) # all candidate moves will have the man on the start riverbank
newstate = template[:]
if validState(newstate) and tuple(newstate) not in visited:
candidates.add(tuple(newstate))
visited.add(tuple(newstate))
for i in range(1,4):
if template[i]==0:
newstate = template[:]
newstate[i]=1
if validState(newstate) and tuple(newstate) not in visited:
candidates.add(tuple(newstate))
visited.add(tuple(newstate))
return candidates
In [9]:
# Generate all possible first moves
print("Move 1")
print("Root:",state)
branches1 = candidateMoves(state)
root2 = set()
for b in branches1:
print("\t",b)
root2.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [10]:
# Generate all possible second moves, etcoks/WGC10.ipynb
print("Move 2")
for s in root2:
print("Root:",s)
branches2 = candidateMoves(s)
root3 = set()
for b in branches2:
print("\t",b)
root3.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [11]:
print("Move 3")
for s in root3:
print("Root:",s)
branches3 = candidateMoves(s)
root4 = set()
for b in branches3:
print("\t",b)
root4.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [12]:
print("Move 4")
for s in root4:
print("Root:",s)
branches4 = candidateMoves(s)
root5 = set()
for b in branches4:
print("\t",b)
root5.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [13]:
print("Move 5")
for s in root5:
print("Root:",s)
branches5 = candidateMoves(s)
root6 = set()
for b in branches5:
print("\t",b)
root6.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [14]:
print("Move 6")
for s in root6:
print("Root:",s)
branches6 = candidateMoves(s)
root7 = set()
for b in branches6:
print("\t",b)
root7.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
In [15]:
print("Move 7")
for s in root7:
print("Root:",s)
branches7 = candidateMoves(s)
root8 = set()
for b in branches7:
print("\t",b)
root8.add(b)
if b == goalstate:
print("*** Goal State Reached ***")
Manually follow the chain backwards up the tree to assemble the sequence of states that led to the Goal State.
[0,0,0,0] -- has parent --> [1,0,1,0]
[1,0,1,0] -- has parent --> [0,0,1,0]
[0,0,1,0] -- has parent --> [1,1,1,0]
[1,1,1,0] -- has parent --> [0,1,0,0]
[0,1,0,0] -- has parent --> [1,1,0,1]
[1,1,0,1] -- has parent --> [0,1,0,1]
[0,1,0,1] -- has parent --> [1,1,1,1]
In [16]:
# order the sequence in the forward direction, print in a readable format
chain = [[1,1,1,1],[0,1,0,1],[1,1,0,1],[0,1,0,0],[1,1,1,0],[0,0,1,0],[1,0,1,0],[0,0,0,0]]
# print it
for s in chain:
printState(s)
