#Create list of visited solutions
    listPrevSolutions = []
    #Create correspnding list of number of steps to reach solution
    listTotalSteps = []

    list_index_steps = []

    def MoveWater (jugMax,
                    jugState,
                    targetVol,
                    runningTotal,
                    previousSteps,
                    listLength):
        global list_index_steps

    noNewSolutionAdded = 1
    listPosition = listLength

    jugA_max = jugMax[0]
    jugB_max = jugMax[1]
    jugC_max = jugMax [2]

    jugA_state = jugState[0]
    jugB_state = jugState[1]
    jugC_state = jugState[2]

    if jugA_state == targetVol or jugB_state == targetVol or jugC_state == targetVol:
        print ("Target achieved in 1 step. Fill up a fucking jug")
        return True

    #Move 1: move from A into B (if room) AND (if not state doesn't exist)
    if jugA_state !=0:
        if jugB_state < jugB_max:
            #Empty A into B if room
            if jugB_state + jugA_state <= jugB_max:
                new_jugA_state, new_jugB_state = 0, jugB_state + jugA_state
            else: #Empty as much of A into B
                new_jugA_state, new_jugB_state = (jugA_state - (jugB_max-jugB_state)), jugB_max

            new_jugC_state = jugC_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 2: move from A into C (if room) AND (if not state doesn't exist)
    if jugA_state !=0:
        if jugC_state < jugC_max:
            #Empty A into C if room
            if jugC_state + jugA_state <= jugC_max:
                new_jugA_state, new_jugC_state = 0, jugC_state+ jugA_state
            else: #Empty as much of A into C
                new_jugA_state, new_jugC_state = (jugA_state - (jugC_max-jugC_state)), jugC_max

            new_jugB_state = jugB_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 3: move from B into A (if room) AND (if not state doesn't exist)
    if jugB_state !=0:
        if jugA_state < jugA_max:
            #Empty B into A if room
            if jugA_state + jugB_state <= jugA_max:
                new_jugB_state, new_jugA_state = 0, jugA_state + jugB_state
            else: #Empty as much of B into A
                totalToMove = jugA_max - jugA_state
                new_jugA_state, new_jugB_state = jugA_max, jugB_state - totalToMove

            new_jugC_state = jugC_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 4: move from B into C (if room) AND (if not state doesn't exist)
    if jugB_state !=0:
        if jugC_state < jugC_max:
            #Empty B into C if room
            if jugC_state + jugB_state <= jugC_max:
                new_jugB_state, new_jugC_state = 0, jugC_state + jugB_state
            else: #Empty as much of B into C
                new_jugB_state, new_jugC_state = (jugB_state - jugC_max), jugC_max

            new_jugA_state = jugA_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 5: move from C into B (if room) AND (if not state doesn't exist)
    if jugC_state !=0:
        if jugB_state < jugB_max:
            #Empty C into B if room
            if jugC_state + jugB_state <= jugB_max:
                new_jugC_state, new_jugB_state = 0, jugB_state + jugC_state
            else: #Empty as much of C into B
                totalToMove = jugB_max - jugB_state
                new_jugB_state, new_jugC_state = jugB_max, jugC_state - totalToMove

            new_jugA_state = jugA_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 6: move from C into A (if room) AND (if not state doesn't exist)
    if jugC_state !=0:
        if jugA_state < jugA_max:
            #Empty C into A if room
            if jugA_state + jugC_state <= jugA_max:
                new_jugC_state, new_jugA_state = 0, jugA_state + jugC_state
            else: #Empty as much of C into A
                totalToMove = jugA_max - jugA_state
                new_jugA_state, new_jugC_state = jugA_max, jugC_state - totalToMove

            new_jugB_state = jugB_state
            if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
                listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
                listTotalSteps.append(runningTotal+1)
                list_index_steps.append(previousSteps + [listPosition])
                listPosition +=1

                noNewSolutionAdded = 0

            if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
                print (targetVol,"ml reached in", runningTotal+1,"steps")
                print (print_Steps_Taken(previousSteps + [listPosition-1]))
                return True

    #Move 7 - Empty A
    if jugA_state != 0:
        if jugB_state != 0 or jugC_state !=0:
            if [0,jugB_state,jugC_state] not in listPrevSolutions:
                    listPrevSolutions.append([0,jugB_state,jugC_state])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    #Move 8 - Empty B
    if jugB_state != 0:
        if jugA_state != 0 or jugC_state !=0:
            if [jugA_state,0,jugC_state] not in listPrevSolutions:
                    listPrevSolutions.append([jugA_state,0,jugC_state])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    #Move 9 - Empty C
    if jugC_state != 0:
        if jugB_state != 0 or jugA_state !=0:
            if [jugA_state,jugB_state,0] not in listPrevSolutions:
                    listPrevSolutions.append([jugA_state,jugB_state,0])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    #Move 10 - Fill A
    if jugA_state!=jugA_max:
        if jugB_state != jugB_max or jugC_state!=jugC_max:
            if [jugA_max,jugB_state,jugC_state] not in listPrevSolutions:
                    listPrevSolutions.append([jugA_max,jugB_state,jugC_state])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    #Move 11 - Fill B
    if jugB_state!=jugB_max:
        if jugA_state!=jugA_max or jugC_state!=jugC_max:
                if [jugA_state,jugB_max,jugC_state] not in listPrevSolutions:
                    listPrevSolutions.append([jugA_state,jugB_max,jugC_state])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    #Move 12 - Fill C
    if jugC_state!=jugC_max:
        if jugA_state != jugA_max or jugB_state!=jugB_max:
                if [jugA_state,jugB_state,jugC_max] not in listPrevSolutions:
                    listPrevSolutions.append([jugA_state,jugB_state,jugC_max])
                    listTotalSteps.append(runningTotal+1)
                    list_index_steps.append(previousSteps + [listPosition])
                    listPosition +=1

                    noNewSolutionAdded = 0

    if noNewSolutionAdded == 1 and listPrevSolutions.index(jugState) == len(listPrevSolutions) - 1:
        print ("No new possible solutions")
        return True

    return False

def print_Steps_Taken(previousSteps):
    solution = []
    for index in previousSteps:
        solution += [listPrevSolutions[index]]
    return solution


def setjugVolumes():
    #Set jug sizes (a,b,c) and target volume (d)
    a = int(input("Please enter volume of largest jug: "))
    b = int(input("Please enter volume of second largest jug: "))
    c = int(input("Please enter volume of third largest jug: "))
    jugsMax = [a,b,c]
    targetVol = int(input("Please enter target volume: "))
    return jugsMax, targetVol

def possibleStartStates():
    #Set jug states
    # (full, empty, empty), (full, full empty),
    #(empty, full, empty), (empty, full, full),
    #(empty, empty, full) ,(full, empty, full),
    startStates = [
        [5,0,0], [5,3,0],
        [0,3,0], [0, 3,1],
        [0,0,1], [5,0,1]]
    return startStates

if __name__ == "__main__":
    jugMax, targetVol = setjugVolumes()
    #Get all possible start states - add featur later and run for loop for ALL possible
    #...states. Add this feature later
    jugA_max = jugMax[0]
    jugB_max = jugMax[1]
    jugC_Max = jugMax[2]

    #Add first state to list with runningTotal
    listPrevSolutions.append([jugA_max, 0,0])
    listTotalSteps.append(1)

    listPrevSolutions.append([0, jugB_max,0])
    listTotalSteps.append(1)

    listPrevSolutions.append([0, 0,jugC_Max])
    listTotalSteps.append(1)

    listPrevSolutions.append([jugA_max, jugB_max,0])
    listTotalSteps.append(2)

    listPrevSolutions.append([jugA_max, 0,jugC_Max])
    listTotalSteps.append(2)

    listPrevSolutions.append([0, jugB_max,jugC_Max])
    listTotalSteps.append(2)

    list_index_steps.append ([0])
    list_index_steps.append ([1])
    list_index_steps.append ([2])
    list_index_steps.append ([3])
    list_index_steps.append ([4])
    list_index_steps.append ([5])


    #Now run the function

    counter = 0
    for item in listPrevSolutions:
        jugState = item
        runningTotal = listTotalSteps[counter]
        previousSteps = list_index_steps[counter]
        listLength = len(listPrevSolutions)
        x = MoveWater(jugMax,
                    jugState,
                    targetVol,
                    runningTotal,
                    previousSteps,
                    listLength)
        counter +=1
        if x == True:
            break