Using Simulated Annealing to Solve Logic Puzzles
The other day, I was watching Ted Ed’s collection of YouTube videos on riddles and came across this interesting logic puzzle described as “Einstein’s Riddle”. Einstein probably didn’t make up the riddle, but the problem itself is kind of interesting for a few reasons. You can either watch the video or keep reading for a retelling of the problem below.
The world’s rarest fish has been stolen from the city aquarium, and the police have followed the scent to a street of 5 identical looking houses all in a row. The police can only search one house without the thief getting away, and so we have to find out which house contains the fish.
We have the following information:
- Each house’s owner is of a different nationality,
either Dane, Brit, Swede, Norwegian, or German.
- The interior walls of each house are coloured differently,
either yellow, red, white, green, or blue.
- Each house contains a different animal,
either horse, cat, bird, fish, or dog.
- The owner of each house drinks a different beverage,
either water, tea, milk, coffee, or root beer.
- The owner of each house smokes a different kind of cigar,
either Pall Mall, Prince, Blue Master, Dunhill, or Blends.
Furthermore, we have the following 15 clues:
- The Brit lives in the house with red walls.
- The Swede has a dog.
- The Dane drinks tea.
- The house with green walls is directly to the left of the house with white walls.
- The owner of the house with green walls drinks coffee.
- The person who smokes Pall Mall cigars owns a bird.
- The owner of the house with yellow walls smokes Dunhill.
- The man living in the center house drinks milk.
- The Norwegian lives in the first house.
- The man who smokes blends lives next to the cat owner.
- The horse’s owner lives next to the man who smokes Dunhill.
- The man who smokes Blue Master drinks root beer.
- The German smokes Prince.
- The Norwegian lives next to the house with blue walls.
- The man who smokes Blends lives next to the man who drinks water.
Using nothing but this information, it is possible to figure out who has the fish.
Don’t read ahead yet if you want to figure this out on your own first.
I remember having seen this problem several years ago, and I solved it on paper using the traditional logical solution shown in the video using a lot of process of elimination. Solving the problem using this method is probably how it was meant to be done, and I’d recommend trying it first to compare the different methods.
When I first learned about the problem years ago, I didn’t have much programming knowledge. But now, I wondered if I could use my programming knowledge to solve the problem a different way. At first I wondered if it could be brute forced, just trying every possible arrangement.
How many arrangements are there? Well for the first house, there are 5 “attributes” to pick (nationality, wall colour, animal, beverage, and cigar), and each has 5 options. This gives 55 possibilities for the first house. Then for the second house, there are still 5 attributes to pick, but only 4 options for each. This gives 45 possibilities for the second house, 35 for the third, 25 for the fourth and 15 for the fifth. Multiplying these together gives 24 883 200 000 or almost 25 billion possibilities. If we could check 100 000 possibilities every second, it would take 69 hours to check all the possibilities.
There are many ways we could speed up the process, like using some of the clues to significantly reduce the size of the search space. We could also turn the clues into logic expressions in code and use them to perform a similar process of elimination technique to simulate how it would be done on paper. I thought to use a technique I learned in my cooperative and adaptive algorithms class called simulated annealing. Simulated annealing can be used to solve problems like this, where there’s a large search space and we are trying to find a global optimum. In this case, the global optimum is the arrangement in which all 15 of the clues are satisfied.
The idea behind simulated annealing is fairly simple.
We start with an initial state (or “solution”), where a state is one of the almost 25 billion possibilities described above. That is, for each house and for each of its attributes, one of the five choices for the attribute is picked.
We also need to define a cost function which, when given a state, tells us how “good” the state is. Here, a natural cost function would be “the number of clues that are NOT satisfied”. For example, if out of the 15 clues, 12 are satisfied, but 3 are not satisfied, our cost function would give us 3 for the corresponding state. We seek to minimize the cost of our state. If the cost of a state is 0, that means all the clues are satisfied!
So now we have the concept of a state and a cost function. Now what if the initial state we picked doesn’t have a cost of zero? Then we want to reduce it, right? But how? We have to pick a new state to replace our initial one and evaluate its cost and hope its cost is better (lower). But if we just pick another totally random state, that’s basically just doing the brute-force method described earlier.
Instead, we can try to take advantage of what we have and change it little by little. We can do that by defining what’s called a “neighbour state”. Here, a neighbour state is simply a state which can be reached by swapping an attribute choice between two houses. For example, if our current state has the German in the second house and the Brit in the fourth house, a neighbour of the current state would be the state in which everything is the same except that the German is in the fourth house and the Brit is in the second house. For a given state, there are 5C2 = 10 choices for the two houses to swap, and 5 attributes to choose from, giving a total of 50 neighbouring states for any state. The hope is that by simply performing a swap, the cost will probably not drastically increase.
Now that we have the concept of a neighbour state, we can simply choose a random neighbour and “move” to it; that is, change our current state to the neighbour state. But we probably don’t want to do that if it has a worse cost right? If our current state has cost 3, then we probably don’t want to move to a state of cost 7. However, we will not always be able to move to a state of lower cost. For this problem, it turns out we’ll often get stuck in a local minimum, a state in which all neighbouring states have cost greater than or equal to the cost of the current state.
We won’t be able to find the global minimum just by choosing neighbours with lower cost all the time, because eventually there won’t be any. We can escape this trap either by moving to another random state, or instead, we can sometimes accept worse solutions. The hope here is that by following this worse solution, we can eventually get to the global minimum.
Simulated annealing performs the latter using what’s called an acceptance probability. The acceptance probability is used to determine whether we want to move to a neighbouring state or not. There are a few basic properties of the acceptance probability.
If the neighbouring state has lesser or equal cost, then we will always move to it.
If it has greater cost, we will only move to it with a certain probability. Otherwise we’ll stay where we are and choose another neighbour. We define the cost delta denoted by Δc, which is simply the current cost subtracted from the neighbour cost, and a parameter t, which stands for temperature, and influences how likely we are to accept the neighbouring state.
Looking at the exponential function, the greater the cost delta, the lower the power, and thus the lower the acceptance probability is. If the neighbouring cost is much higher than the current cost, we are not likely to move to it.
t affects how often we pick worse solutions. The greater the value of t, the higher the acceptance probability is. t is a parameter we choose which typically starts high and steadily decreases every so often, so we are less likely to accept worse solutions as time goes on (where we are hopefully close to finding the global minimum).
Note that since Δc and t are both positive, the exponential function’s value is in the range (0, 1). We can use a random number in this range to choose, based on the acceptance probability, whether we should move to the new state or not. If the random number is less than the acceptance probability’s value, we should move to the new state.
Turning It Into Code
We now have everything necessary to apply this technique to our problem. To summarize:
- Pick an initial solution and compute its cost
- Pick a random neighbour of the current solution
- Compute its cost, the cost delta, and the acceptance probability
- Move to the neighbour if a random number in (0, 1) is less than the acceptance probability
- Repeat steps 2-4 until the current solution’s cost is 0. Decrease the temperature
tevery so often.
We’ll write the code in python because it’s great for stuff like this. First, we need to setup the initial state.
For each attribute, the ith house will take on the ith choice for the attribute. Thus, the initial state can be represented by a list of 5 houses, each of which is a list of the attributes it takes on.
For convenience, we’ll also define the following constants:
Each index in the list for a house corresponds to a specific attribute as shown above.
Now we’re ready to define our simulated annealing procedure.
There’s two functions we haven’t defined yet that are used above. These are
We first deepcopy the current state since we don’t want to mutate the current state when determining the neighbour state. We then pick two houses to swap (
j) and an
attr_index (one of NAT, COL, ANI, BEV, and CIG, the constants we defined earlier). Finally, for the two houses picked, we swap their attribute choices for the corresponding attribute and return the neighbour state.
We now need to define the
cost_of_state function, which when given a state returns its cost. As mentioned earlier, it will be the number of clues that are not satisfied by the state.
The above 15 boolean expressions correspond to the 15 clues in the order they were presented at the beginning of this post. For each house, we check how many clues are satisfied and subtract this total from the current cost. After doing this for each house we have our cost for the state.
Finally we have everything we need to run the simulated annealing technique.
We use a seed value of 100 for the random number generator so we can produce the same results over and over. The output of the above is:
We found the solution! In 9870 iterations of simulated annealing, we found that the German has the fish in the fourth house. We only had to look at about 0.00004% of the possibilities to find the solution. If you’d like to review the code in full, it can be found here.
Although taking the time to code this may have taken longer than to solve the problem by hand, this technique can be applied to many other problems, most notably, the Travelling Salesman Problem in which we would swap cities instead. The only things we would need to change are the state representation, the neighbouring state selection, and the cost function. The technique itself is generally applicable to all sorts of problems.
It’s worth noting that simulated annealing has many tunable parameters (initial temperature, temperature reduction function, stopping conditions, acceptance probability function). If these are changed, the number of iterations taken to find the solution can vary drastically. In my tests, I saw as many as a million iterations and as few as 200 iterations to converge to the solution. Choosing the parameters wisely is part of the art of making simulated annealing performant.
Logic problems can be often be solved in a variety of ways. Doing it this way allows us to do very little thinking with regards to the clues and how they all relate to each other. We let the computer do the work for us.
The applications of techniques like this are of course not limited to logic puzzles like this. Simulated annealing in particular can be used for circuit board placement, physics simulations, and structural optimization. Artificial intelligence techniques in general have wide-reaching applications and implications. Learning about different techniques is both interesting and valuable, if only for solving fun logic puzzles like this one.