Think outside the Box

One of the most important things to get right when it comes to problem solving is correct identification of the constraints. If you assume constraints that don't actually exist then you are limiting yourself to the range of solutions that fit within your assumed constrains. This makes finding a workable solution harder than necessary and may even make solving the problem impossible. Where a solution is possible it may be far less efficient or harder to understand than alternatives that meet the required constraints but which ignore your assumed one. Alternatively if you ignore a required constraint then what you develop may not solve the problem at all.

To understand how assuming additional constraints can make a problem impossible to solve let's consider two classic puzzles.

In the first puzzle you start with nine equally spaced dots arranged in a square with three dots in each row and three in each column. The problem requires that you join all the dots together using straight lines in a way that allows you to trace a path from any dot to any other dot following those lines. The constraint is that you can only use four lines and each line must start where the previous line finished.

Now if the first constraint didn't exist you could draw one line across the top row, a second down to the second row, a third across the second row, a fourth down to the third row and a fifth across the third row resulting in all nine dots being joined using five straight lines that all start where the prior line finished.

If the second constraint didn't exist then you could draw one line across each row and then a fourth line down one column joining all the dots together with four lines but where your pen or pencil needs to be lifted off the page at least once.

Many people are unable to solve this puzzle because they assume a third constraint. They assume that all four lines must be within the box delineated by the dots. If they realise that constraint doesn't exist then they may assume that all of the lines need to be horizontal or vertical. There is no such constraint and in fact the problem would be unsolvable if either of those was a constraint. To solve this puzzle you need to think outside the box. The first line joins the dots on the top row and continues on to the point where the second straight line can be drawn through the third dot on the second line and the second dot on the third line. This second straight line then extends to where it is directly under the first column. The third line goes from there back to the starting point and then the fourth line is another forty five degree line passing through the second dot on the second line and the third dot on the third line.

Nine dots, five continuous lines, four non-continuous lines, four continuous lines.

The second puzzle involves someone needing to cross a river in a boat. They have three pets that they need to take across with them - a dog, a cat and a bird. The boat is big enough to for them and one pet so they will have to make multiple trips to transport all three pets across. The constraint is that if the dog and cat are left alone together they will fight and if the cat and bird are left alone together the cat will eat the bird so the solution must not leave either of these pairs together on the same side while transporting the other animal.

This makes the first move obvious. To comply with the constraint the cat must be taken across first leaving the dog and bird together. In fact if you correctly apply the constraints each of the subsequent moves is equally obvious. The only reason this particular puzzle is impossible for some people to solve is because they assume an additional constraint that doesn't exist. They assume that you can't bring animals back across the river. It doesn't matter whether you choose to take the dog or the bird across on the second trip as either way the constraints that apply force you to bring the cat back with you when you return to collect the third animal (as otherwise you'd have two animals together that the constraints say can't be left alone together). After the third trip both the dog and bird are across and you then simply return to make a fourth trip across with the cat.

Each of these problems has very specific constraints without which there wouldn't be a puzzle to solve. If the constraint of only being able to take one animal at a time or on which animals can be left alone together didn't exist in the second puzzle then you could either take all across together or take them across one at a time in any order. Also with each puzzle the solution is quite simple and the only reason that people have difficulty solving either one is that they assume additional constraints that don't actually exist.

When looking at any programming problem the same situation applies. Applying non-existent constraints is just making the problem more difficult than it needs to be. It eliminates possible solutions that meet all of the actual constraints but which do not fit with your preconceived idea of how the problem can be solved leading either to a less than optimal solution or no solution at all. Disregarding or not properly identifying the constrains that do need to apply means that the problem you end up solving is not the one that needs to be solved. Each of the solutions I have presented for these two puzzles that disregard one or other of the real constraints gives the appearance of having solved the problem but because it doesn't satisfy the constraints it is completely irrelevant to the real problem.

Let's look at one more classic puzzle where disregarding a constraint makes the problem trivially easy to solve but where the constraint makes the situation far less obvious.

Imagine that we have twelve gold coins and a balance scale that allows us to compare the weight of the coins to see whether they are the same weight. Imagine also that we know that there is one and exactly one counterfeit amongst the coins and that coin can only be distinguished from the real gold coins because it is not the same weight. We need to use the balance scales to compare the weights of the coins and identify the counterfeit one. The constraint is that you can only use the balance scale three times.

To make this easier to visualise I suggest that you use twelve actual coins and split them into the various groupings you want to try weighing and write out the possible outcomes.

Without that constraint limiting you to three weighings you can just keep comparing the weights of the coins two at a time until you get two coins of different weights. That then means that one of those two is the counterfeit and by weighing one of them against any of the other coins you would be able to tel which. This approach would require up to seven weighings on the scale. Each of the first six weighings compare the weights of pairs of coins so since we know that eleven coins are genuine as soon as we get two coins of different weights we know that one of those is the counterfeit. Now we might get lucky and pick the counterfeit in the first or second pair of couns in which case we can still meet the constraint of only using the scape three times. There is a one third chance of meeting the constraint using this approach but we need to meet the constraint all the time and not just one third of the time. If you think that ought to have read half rather than one third because you can weigh three pairs in three weighings then you have overlooked that we don't know which of the pair that are different weights is the counterfeit because we don't know whether the counterfeit is heavier or lighter - just that it is not the same weight - so an extra weighing is required to determine that.

To solve the proble without ever needing more than three weighings we need to weigh more of the coins in each weighing. Weighing six against six would not help because all it teslls us is that either one of six coins is a heavier counterfeit or one of the other six is a lighter counterfeit. That is not enough information to be able to finish distinguishing the counterfeit in two more weighings.

Weighing three against three will identify six of the coins as genuine (if the scale doesn't balance then the counterfeit is on the scale and the other six are genuine and if it does balance then the six on the scale are genuine and the counterfeit is in the other six). This looks more promising as a second weighing of three of the suspect coins against three that are known to be genuine will reduce the group containing the counterfeit to three (if these don't balance then the counterfeit is one of the three plus we know whether it is heavier or lighter, if they balance then the counterfeit is in the other three and we also know whether it is heavier or lighter from the first weighing - but not if the counterfeit were in the six that weren't used for the first weighing). A third weighing of two of the remaining three suspect coins will identify the counterfeit provided that we already know whether it is heavier or lighter from one of the first two weighings or when this weighing balances. Unfortunately if the counterfeit was not included in either of the first two weighings and is included in the third weighing then we still don't know which of the two coins it is. This means that this approach solves the problem within the constraints five sixths of the time. Unfortunately we need a solution that will always solve the problem within the constraints.

That last runthrough gives a clue to the real solution to this particular problem. The third unequal weighing does identify the counterfeit provided that one of the earlier weighings has already determined whether it is heavier or lighter than the other coins. The actual solution to this problem involves weighing four against four. This will either identify the counterfeit as being one of the four unweighed coins or one of the eight coins that were weighed (where we also know that if it is one of four it is heavier or one of the other four and is lighter). If it is one of the four then we simply weigh three of those against three genuine coins and if they balance the unweighed coin is the counterfeit. If they don't balance we know whether the counterfeit is heavier of lighter and simply weigh two of the remaining suspect coins to determine which of the three is counterfeit. If the counterfeit is in the other eight coins then we use the second weighing to split that group into three. We leave three of the coins where they are on one side of the scale, we replace the three on the other side with three genuine coins, and we swap the remaining two coins to the opposite side of the scale. Now if the scale tips the same way the counterfeit is amongst the three that were not moved and we know whether it is lighter or heavier. If the scape tips the other way then the counterfeit is one of the two that was swapped and if the scale now balances it is one of the three we took off for the second weighing. For each of the groups of three we know whether the counterfeit is lighter or heavier and while we don't know that yet for the remaining two simply weighing one against a genuine coin will tell us. In fact with this approach we not only identify the counterfeit in three weighings, we also identify whether it is lighter or heavier. The only situation where we identified the counterfeit without knowing if it is lighter or heavier is where the first weighing identified it as being in the unweighed group of four and the second weighing identified as the only coin that hadn't been weighed. So if the constraints required that we identify whether it is lighter or heavier as well as which coin it is we could use the third weighing to determine that.

Note that with this particular puzzle that even if unlimited weighings were allowed that a solution that only requires three may be a more efficient solution to the problem even if the code to apply it is slightly longer.

Making sure that you properly understand the constraints that apply to your particular problem is an important first step to finding an appropriate solution. Not applying constraints that need to be applied means that you are wasting your time trying to solve a different problem from the one you need to solve. Applying constraints that don't actually exist means that you may be overlooking obvious solutions. If the boat in the river problem were big enough to carry two animals or four weighings were allowed in the coin problem then a solution that is easier to understand can be applied in solving those problems. Defining exactly what the real constraints are defines the scope within which you need to look for a solution. Applying non-existent constraints that you simply assume apply means that you have limited or possibly eliminated the scope in which a solution can be found. There will be occasions where some of the constrains are assumed and not directly specified though so you need to ask questions to make sure that you identify any assumed constraints.

 

This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow
Donate