Можно найти последовательность действий поиском в ширину по состояниям трёх сосудов. Каждое состояние записывается как количество воды в А, Б и В. Программа проверяет наполнение, опустошение и переливание до полного или пустого сосуда и останавливается, когда в каком-либо сосуде окажется ровно 1 л.

from collections import deque

capacity = (6, 10, 15)
start = (0, 0, 0)
queue = deque([start])
previous = {start: None}
action = {}
goal = None

while queue:
    state = queue.popleft()

    if 1 in state:
        goal = state
        break

    for i in range(3):
        # Наполнить сосуд i
        next_state = list(state)
        next_state[i] = capacity[i]
        next_state = tuple(next_state)
        if next_state not in previous:
            previous[next_state] = state
            action[next_state] = f'Наполнить {"АБВ"[i]}'
            queue.append(next_state)

        # Опустошить сосуд i
        next_state = list(state)
        next_state[i] = 0
        next_state = tuple(next_state)
        if next_state not in previous:
            previous[next_state] = state
            action[next_state] = f'Вылить {"АБВ"[i]}'
            queue.append(next_state)

        # Перелить из сосуда i в сосуд j
        for j in range(3):
            if i == j:
                continue
            amount = min(state[i], capacity[j] - state[j])
            next_state = list(state)
            next_state[i] -= amount
            next_state[j] += amount
            next_state = tuple(next_state)
            if next_state not in previous:
                previous[next_state] = state
                action[next_state] = f'Перелить из {"АБВ"[i]} в {"АБВ"[j]}'
                queue.append(next_state)

steps = []
while previous[goal] is not None:
    steps.append(action[goal])
    goal = previous[goal]

for step in reversed(steps):
    print(step)

Поиск рассматривает только допустимые действия и находит последовательность, приводящую к 1 л; программа выводит её по шагам.

Поделись с друзьями