Problema dos dois baldes de água

Enunciado do problema: Você recebe dois baldes de água, um de quatro litros e outro de três litros. Nenhum deles possui qualquer marcação de medida. Há uma torneira que pode ser utilizada para encher os baldes de água. Como colocar exatamente dois litros d'água dentro do balde de quatro litros? [RIC 94]

O espaço de estados para este problema pode ser modelado como o conjunto de pares ordenados de números naturais (x,y) tal que x = 0, 1, 2, 3 ou 4 e y = 0, 1, 2 ou 3, onde x representa a quantidade de água no balde de 4 litros, e  y representa a quantidade de água no balde de 3 litros.

O estado inicial do problema é o estado no qual ambos os baldes estão vazios: (0,0), e o conjunto de estados finais é constituído por todos os estados onde a quantidade de água no primeiro balde é 2, ou seja: (2,n), onde n = 0, 1, 2 ou 3.

Possível conjunto de regras de produção para o problema:

r1 (x,y|x<4)?? (4,y) Encher o balde de 4 litros

r2 (x,y|y<3)?? (x,3) Encher o balde de 3 litros

r3 (x,y|x>0)?? (0,y) Esvaziar o balde de 4 litros no chão

r4 (x,y|y>0)?? (x,0) Esvaziar o balde de 3 litros no chão

r5 (x,y|x+y>4)?? (4,y-(4-x)) Despejar água do balde de 3 litros dentro do balde de 4 litros até que este esteja cheio

r6 (x,y|x+y>3)?? (x-(3- y),3) Despejar água do balde de 4 litros dentro do balde de 3 litros até que este esteja cheio

r7 (x,y|x+y?4 e y>0)?? (x+y,0) Despejar toda a água do balde de 3 litros dentro do balde de 4 litros

r8 (x,y|x+y?3 e x>0)?? (0,x+y) Despejar toda a água do balde de 4 litros dentro do balde de três litros

Uma possível solução seria aplicar as regras na seguinte seqüência: r2 ,r9,r2 ,r7,r5 e r9 Situação dos baldes à cada aplicação:
Litros no balde de 4 l
Litros no balde de 3 l
Regra aplicada
0
0
3
3
4
0
2
0
3
0
3
2
2
0
2
7
2
5
3
7

[Voltar]