Puzzles came into vogue in the mid-19th century, appearing in many newspapers and magazines. Puzzles help with the development of problem solving skills. Part of the problem of designing programs is that novice programmers will try to solve the problem during the process of coding, or coding-on-the-fly. Puzzles help develop abstract thinking skills, enhance creativity and problem solving skills. Computer science uses a number of classical puzzles to illustrate concepts. Probably the most widely used puzzle is the Towers of Hanoi, introduced by French mathematician Édouard Lucas in 1883, and used exclusively for illustrating recursion. Other classical examples include the n-queens problem (backtracking), and Bridges of Könisberg (graphs). There are a number of examples of books which provide numerous puzzles including “The Canterbury Puzzles”, published in 1907 by Henry Dudeney, and Sam Loyd’s mathematical puzzles.
Brute force
This method of solving problems works on the principle of exhaustive search, i.e. finding all possible candidates for a solution and seeing which satisfies the problem domain. Brute force will always find a solution, if one exists. An example of brute force is the “Goats from cabbage” puzzle [1]:
“Separate all the goats from the cabbage in the picture by drawing 3 straight lines”
The easiest way of solving this problem is to try and draw lines on the picture using trial and error, and iterate through all possibilities until a solution is found.
Divide and Conquer
This means of problem solving is based on partitioning a problem into smaller subproblems, solving them independently and combining their solutions to arrive at a solution to the original problem. One example of a divide-and-conquer puzzle is “How much does the bottle weigh” [1].
The bottle and glass on the left scale balance the jug on the right scale (a). The bottle alone balances and glass and a plate (b), and 3 of the plates balance 2 jugs (c). How many glasses will balance the bottle?
Solving this puzzle requires breaking the problem down into sub-problems: deciding how substitutions could be performed to solve a problem. Let’s denote the jug, glass, plate, and bottle by J, G, P, and B respectively. In the first subproblem, using (a) we can substitute two bottles (B) and two glasses (G) for the two jugs in (c):
(c) BBGG–PPP
In the second subproblem, we can double the quantities in (b):
(d) BB–GGPP
We can now substitute the two bottles in (c) with GGPP from (d):
(c) GGPPGG–PPP
Now taking two plates off either side will not disturb the balance:
(c) GGGG–P
Thereby leaving one plate balancing 4 glasses. Now in (b), instead of 1 plate put 4 glasses, thereby having 5 glasses balance the bottle.
Another divide-and-conquer problem is the “Bottle’s Volume” [1] .
“If a bottle, partly filled with liquid, has a round, square or rectangular bottom which is flat, can you find its volume using only a ruler? You may not add or pour out liquid.”
It may seem like a challenging problem, because of the shape of the bottle, however the area of a circle, square or rectangle can easily be calculated after measuring sides or diameter with a ruler. Call the area s. With the bottle upright, measure the height h1 of the liquid. The full part of the bottle has the volume sh1.
Turn the bottle upside down and measure the height h2 of the air space. The empty part of the bottle has the volume sh2. The whole bottle has the volume s(h1+ h2).
[1] Kordemsky, B.A., The Moscow Puzzles, 1972.
[2] Dudeney, H.E., Amusements in Mathematics, 1917.