How to create models for solving logic puzzle

Question

this is not about getting an answer for this problem, but to create models for solve them, below I will show a simple puzzle in order to demonstrate what I mean:

Lets say two friends just left a bar with 8 liters of alcohol in an weird bottle with 8 liters. You on the other hand want half of this amount, and he is willing to give it to you based on your friendship. However you have two bottles one with 5 liters and the other one with 3. And you want to divide it the in a half while keeping your own bottles.

Things that must assume as true: 1. You won't be able to calculate the volume of any bottle based on its shape (not even with surface integrals, weird theorems from vector calculus, etc) 2. You don't have anything to measure any volume despite of the bottles.

So to make it simpler to understand:

three bottles: 
-> 8 liters (full)
-> 5 liters
-> 3 liters

And each person must have 4 liters

(at the end of changing fluids from one bottle to another one)

One solution:

Fill the 3 one with the 8.
Then, move from 3 to five.
Then, fill again the 3 one.
Fill the 5 one (and there will be one liter left in the 3)
then fill the 8, with the 5, move the one liter to the 5 and finally fill the 3.

There you'll have:

-> 8 (filled with 4)
-> 5 (filled with 1)
-> 3 (full)

My question:

This kind of problem is not so hard to solve, but how to create models to solve them ? Or perhaps an algorithm to do this kind of task ?

Answer 1

Often, the stupid straightforward thing works very well.

You can model the current distribution of alcohol as simply being a triple of numbers saying how much is contained in each bottle.

e.g. you start at (8,0,0)

Then, you simply go over each possible distribution of alcohol and try everything you can do from that state.

e.g. from (8,0,0) you can go to (3,5,0) or (5,0,3)

If you only consider distributions that can be reached in your search (e.g. you wouldn't consider the distribution (3,2,3) until you've already shown you can reach it), and take care not to duplicate work (e.g. you remember that you've considered (3,2,3), so if you see it a second time, you don't spend more time considering it again), then you will have a rather efficient algorithm.

Following this algorithm:

1. (8,0,0)
2. (3,5,0) (from 1)
3. (5,0,3) (from 1)
4. (0,5,3) (from 2) (we can reach (8,0,0) from 2. But we've seen that already, so skip it)
5. (3,2,3) (from 2)
6. (5,3,0) (from 3)
7. (6,2,0) (from 5)
8. (2,3,3) (from 6)
9. (6,0,2) (from 7)
10. (2,5,1) (from 8)
11. (1,5,2) (from 9)
12. (7,0,1) (from 10)
13. (1,4,3) (from 11)
14. (7,1,0) (from 12)
15. (4,4,0) (from 13)

And stop. The path 15 <- 13 <- 11 <- 9 <- 7 <- 5 <- 2 <- 1 lets us wind up with a desired solution. By the way I've ordered the search, I think we're even guaranteed that there cannot be any shorter strategies. (Yours, I'm guessing, would be #16 on my list if I kept going, and has the same length)

The hardest part, when doing this by hand, is that it's often easy to overlook a move. A computer has no trouble with this algorithm, of course.

Answer 2

A theoretical computer science guy's approach:

What is our input?

• $n$ bottles
• $c_1 , \dots , c_n$ which denote the capacity of each bottle
• $s_1 , \dots , s_n$ which denote the initial fill level of each bottle
• $t_1 , \dots , t_n$ which denote the target fill level we want at the end

All values are in $\mathbb{N}$.

What is our output?

Either a sequence of steps which solves our problem or false if there isn't such a sequence.

For example, your particular instance would translate to $(3,8,5,3,8,0,0,4,1,3)$. Or more precise you would run the algorithm for each input $(3,8,5,3,8,0,0,4,x,y)$ with $x+y=4 \wedge x \leq 5 \wedge y \leq 3$.

So, what does the algorithm look like? First, we introduce some working variables

• $x_1, \dots, x_n$ denote the current fill level of each bottle

We define two operations $check()$ and $fill(i,j)$:

• $check()$ returns true iff the current fill levels match the target fill levels
• $fill(i,j)$ returns the pair $(a,b)$ s.t. after filling the current contents of bottle $i$ into bottle $j$ then $i$ contains $a$ liter and $j$ contains $b$ liter. Note, the call $fill(i,i)$ returns $(x_i,x_i)$ (do nothing)

Now, we can employ a non-deterministic Turing machine to easily solve our task using the following simple algorithm:

1. $(x_1,\dots,x_n) \leftarrow (s_1,\dots,s_n)$ // initialize $x_i$s
2. Guess a sequence of fill steps $S = ((i_1,j_1),\dots,(i_k,j_k))$
3. for $ l=1 $ to $ k $: $(x_{i_l}, y_{j_l}) \leftarrow fill(i_l,j_l) $
4. if $check()$ = true then return $S$
5. else return false

For people not familiar with the concept of non-deterministic Turing Machines (NTM) here is how it works: if there exists a sequence such that our target fill levels are satisfied then the NTM will guess exactly such a sequence and the algorithm returns it. Otherwise it will return false. I believe the crude guys from the practical branch of CS call this approach brute force(but that's only true when you use a deterministic machine!).

Now, what does $k$ look like? How many different filling states across all bottles can you possibly have? Let $c_{max}$ be the maximum capacity over all bottles. $$ k = (c_{max}+1)^n$$ (a $z$ liter bottle can contain $0$ liter thus the $+1$) Why is this sufficient? Suppose there is a working sequence requiring more than $k$ steps. Then some fill state must occur at least twice in the procedure of applying the fill steps thus you have an unnecessary cycle(steps you can remove and still have a working sequence).

On a sidenote: if you fix parameter $n$ (meaning it is not part of the input anymore) then $k$ and therefore the guessed sequence is polynomial w.r.t. to the length of the input(if I'm not mistaken) and therefore this problem lies in $NP$ (instead of returning the sequence simply return true in the decision version). It seems to bear some resemblance to SUBSET-SUM only with more facets I guess.. might it be even NP-complete?

[edit] After thinking about reducing SUBSET-SUM to this I rather believe there might be some non-obvious(at least to me) properties to the transition between fill states which might give rise to an efficient solution (no brute force).