From Puzzles to Programming
Puzzles and Programming
Applications and Computer Algorithms
1. The Chess four Knights problem:
Answer
Knight A can either move to F or H. From H it can move either back to its first place or to C. Thereafter, the sequence of movements will be (C to D, D to I, I to B, B to G, G to F, and F back to A). In this sequence, the movements involved all the positions except E because there is no way to pass through E. This is in compliance to the definition of allowed knights moves.
Presenting the moves in a circle would be like the one below. The problem becomes simple. Moving knight form A to I then becomes moving it to four positions (H, C, D then I). The same applies for the black knight to move from C to G. i.e. it has to move through D, I, B and then G.
A H C D F B G I
2. Traffic Light problem: The roads intersection below cause some traffic problem. Roads E and C are one way, the others are two way. Make an algorithm that takes as an input the permissible turns or continuing straights available and constructs a pattern of lights that allow only the simultaneously permissible turns at a time and thus avoiding collisions.
Answer
There are total of 13 turns one might take at an intersection. Some turns like AB (going from A to B), AC and EC can be carried simultaneously, while others like AC and EB cannot be carried simultaneously because they cross each other and can cause traffic or collisions if done at the same time. So the traffic light colors for AB, and EB cannot be of one type signaling that they are not permitted simultaneously.
We can model this problem by a graph whose vertices represent turns and whose edges connect pairs of vertices or turns that cannot be performed simultaneously.
Assigning traffic light color is equivalent to coloring the vertices of the graph in a way that no two vertices connected by an edge have the same color. In other words, it is a problem of coloring the incompatible turns using different but as few colors as possible.
To do so, we follow the steps:
- we select some uncolored vertex and color it with new color. Add it to the list of colored vertices
- Scan the list of uncolored vertices. For each uncolored vertex, determine whether it has an edge to any vertex already colored (i.e. in the list of colored vertices). If there is no such edge, color the present vertex with a new color and add it to the list of colored vertices.
An example, suppose you start coloring AB blue, then we can color AC, AD, BA, DC, ED also blue because these turns have no common edge or are compatible. But we cannot color BD DA, or DB blue because each is connected by an edge to one of the previous vertices already colored blue.
The table below is the output of such an algorithm:
|
COLOR |
TURNS |
|
BLUE |
AB,AC,AD,BA,DC,ED |
|
RED |
BC,BD,EA |
|
GREEN |
DA,DB |
|
Yellow |
EB,EC |
Note that when using the above algorithm, there will be extra turns that are compatible with other turns of different colors. Example, BA,DC,ED compatible with BC,BD,EA though both sets are of different colors.
|
TURNS Compatible Extra turns | |
|
BC,BD,EA |
BA,DC,ED |
|
DA,DB |
AD,BA,DC,ED |
|
EB,EC |
BA,DC,EA,ED |
3. Solitaire Game:
In a solitaire game called "clock", the 52 cards of playing cards dick are dealt face down into 13 piles of 4 cards each. 12 piles are arranged in a circle like a clock and the 13th pile goes into the center. The game proceeds by turning up the top card of the center pile, and then if its face value 'k', we place it next to the kth pile. (1,2,3,…13 are equivalent to A,2,..,10,J,Q,K.) Playing continues by turning up the top card of the kth pile and putting it next to its pile, etc. until we reach a point where it is impossible to continue since there are no more cards to turn up on the designated pile. What could possible arrangement of the cards in a pile 'k' be so that this game is certainly lost?
Answer
Let the pile of cards be represented as 'oriented + directed tree'. A directed graph is a set of vertices and (edges or arcs) in which each arc e is leading from vertex V to vertex Y. We define V as the initial vertex of e and Y as the final vertex of e. We write V = init(e) and Y = fin(e). An oriented path is a path of arcs (e1, e2, e3,…,en) from V to Y in which V = init(e1), Y = fin(en), and fin(ek) = init(ek+1) for 1 < = k < = n.
An oriented tree or rooted tree is a directed graph with vertex R such that:
- Each vertex V ≠ R is the initial vertex of only one edge e[V].
- R is not an initial vertex of any edge.
- For each vertex V ≠ R there is an oriented path from V to R.
An oriented tree will then look like:
Back to our solitaire game, our oriented tree would be one with vertices v1,v2,…v13; arcs e1,e2,…e12. The vertices represent the 13 piles and the arcs represent the possible virtual connections (when turning up a top card) that lead from one pile to another through the game.
To win the game, there should be an arc ej that goes from vj to vk for each card k in pile j. In other words, if in a pile j (vj) you turned up a bottom card (k) then it should lead to another pile k (vk). This is true, because if k is the bottom card in pile j and it does not lead to a pile k (vk) i.e. the bottom card k = j, then this is a dead end as there are no more cards to turn up in pile j and lead to other piles.
This is similar to the case of going to all islands by crossing all bridges each one only once in example 5. That is to say, as there is an entry or an arc to a pile of cards, there should be an arc going from this pile to another one. This is critical when dealing with the bottom card as a potential exit from the pile. In both this example and example 5 we have used what is called as Eulerian circuit (see chapter one).
4. Consider the following domino "a square divided into four parts, each having a specific number in it". How to tile the plane if we have an infinite supply of such dominos?
Answer
To tile the plane with such domino we have to rotate it by 180 degrees vertically or horizontally to get 3 other new forms of dominos. The 4 dominos will make a pattern. Then applying replication on the resulting pattern, we get the whole plane.
The pattern (formed from the 4 dominos) to be replicated is shown below:
5. How can programmers make a PC to play and win a tic-tac-toe or a chess game?
Answer
In programming, the goal is always to find an optimum solution for a problem. The purpose is to run any program faster and more efficiently to save time on the user as well as on the computer. The time spent is usually proportional to the number of steps executed in the program. As an example, suppose you want to search for an item in a list ( e.g. a certain word in a dictionary). You may write a program that passes sequentially and checks on each single word in the dictionary. If there are n words in the dictionary, then in this case the program might execute n steps if the word was located at the end of the dictionary. You may say that is not bad, but take an example a value of n equals to one million or 500 millions or one billion and so on as happens for example when you are searching for an name in a directory on-line or encyclopedia. An alternative way for searching might be a 'binary search' which was discussed before and you may get a time proportional to log (n) instead of n. In the case, n = 1,000,000 the time will be proportional to log (1,000,000) = 6 instead of 1,000,000.
However, the task of finding an optimum solution is not easy for some problems. As an example in some games such as chess, or tic-tac-toe, there are many possible board positions each time a player moves.
In the figure of the tic-tac-toe below assume that the PC or program is playing against a player. Consider the program moves as O and the player moves as X. The program associates a tree called the game tree with each move. Each node represents a board position. Let us call the board position at level 3 in the figure below as 'y'. The children nodes of y are the allowable moves and thus possible next board positions. With each position or child the program assigns -1, 0, 1 depending on whether the board will lose, draw, or win respectively. After the player plays at level 3, the only next move that allows the program not to lose is the move that gets value 0. All the other moves have value -1 with possibility that the player might win in his next move at level 5. In other words, the program chooses the next node or board position that has the maximum value among the other values at level 4 to avoid loss and possibly win later on as the game goes on.
Thus, the tree propagated so far down to level 4 is represented below as:
With this strategy, you can tell that all the positions are at hand a priori. What the program does is actually propagating the tree chosing the maximum of values assigned to the children nodes of a certain position. This is, of course, dependent on the player moves. Thus, the player is in some way determining the tree route propagated by the program.
6. A grocery salesman has 7 watermelons of same size, shape and color. Six of them have exactly the same weight but only one weighs a little bit more. He wants to find this heavier one by using a balance for maximum of two times only. How can he do that?
Answer
You put 3 watermelons in each side of the balance and leave the 7th one outside. If the 2 sides of the balance are in equilibrium, then the watermelon outside the balance is the heavy one. If the 2 sides of the balance are not in equilibrium then the side that goes down has the heavy watermelon in it (By now you have used the balance only once). Now, you take one watermelon out of this “heavy” side and put each of the remaining 2 watermelons on each side of the balance. Again, if there is equilibrium, then the remaining watermelon outside the balance is the heavy one else the side that goes down contains the heavy watermelon.
In this method you searched for the heavy watermelon using “binary search” a faster and easier way to find an item than the traditional “sequential search” . In the later, you have to search each single item and weigh it to see if it is the requested item. In binary search, as in this example, you divide the whole group in two equal groups. You take the “suspected” group and you do another binary searching in it until you find your item. The suspected group in this example is the side of the balance that goes down. The binary search is use d in many search engines in computer programming. For example, It can be this kind of search engines that is used to find for you a file in your computer documents.
7. Towers of Hanoi:
This game /puzzle is an old one. It consists of three towers and rings. The rings are different in size and are located on one of these towers in a way that they ascend from the largest ring in the bottom up to the smallest ring on the top. You need to move these rings to another tower using a spare tower and in a way that you can not place a ring on a smaller ring in any circumstances.
Answer
Try to solve this puzzle with 4,5, or 6 and even more rings. It will become more complex and may require a computer software to solve it when the number of rings becomes large let’s say 64. This software uses a recursive algorithm or function in which solution of n rings is related to the solution of n-1 rings.
That is to say Move (n) depends on Move (n-1). Move (n-1) is basically moving first n-1 rings from the initial tower to the spare tower. Then move the last ring to the target tower. Now Move (n-1) from spare tower to target tower using the initial tower as the spare one.
8. Sorting: Consider a set S of integers {1, 2, 3,…, n} that are not arranged in order. How to implement a computer algorithm to sort these numbers in ascending order?
Answer
To solve this problem, we should know that a programming language allows to have any set of objects in the form of an array. So, an array representing the set of numbers above can be written as:
Array[I] = any element of S given the order I as presented in S, where I = 1 to n. Example if the set S = {5, 1, 4, 3, 2}, then array[1] = 5, array[2] = 1, array[3] = 4, array[4] = 3, and array[5] = 2. Also, a programming language allows to go over arrays by a loop that starts at any element or array[I] and can span the array either up or down. One of these loops, is the "for loop".
Back to our sorting problem, we can compare the top array element to the one below it i.e. array[I] compared to array[I-1]. If array[I - 1] > array[I] then we swap array[I] and array[I-1]. If we start from array[n] down to array[1] and do the swapping then we will place the smallest number in the bottom of the array i.e. array[1] = 1. Thereafter, we do the swap again starting from the top i.e. array[n] and go down until array[2] now placing the next smaller number in array[2]. By doing this swap, we let the smallest number to "sink" and the largest number to "float up" or "bubble".
Procedure bubble-sort
For I = 1 to n-1
For j = n downto i+1
If array[j-1] > array[j] then
swap array[i-1] and array[i]
The number of steps that the program execute is
(n – 1) + (n – 2) + ….+ 1 = n(n – 1)/2 = n˛/2 – n/2
9. The dining philosophers problem:
There are 5 philosophers dining on a round table. As there is only one chopstick common to any 2 philosophers sitting next each other, a philosopher can eat only if both chopsticks on his sides are available. What is the computer algorithm or procedure that allow each philosopher to eat without conflicting with his 2 neighbors?
Answer
The state of a philosopher can be either hungry, eating or thinking. If he is hungry then he has to declare this by saying he is waiting. If both his neighbors are not eating, then he can pick the chopsticks and eats and then he signals that he ate. Then he switches his state to thinking allowing his neighbors to eat and so on.
Let the array state of the 5 philosopher [0, 1, 2, 3, 4] represent the state of each philosopher at a time. A philosopher I can set a state [I] = eating only if his neighbors are not eating i.e. state[(I + 4) mod 5] ≠ eating and state[(I + 1) mod 5] ≠ eating. The term "a mod b" represent the remainder of dividing of integer a by integer b. In our example, the neighbors of philosopher[1] are philosopher[2 mod 5] and philosopher[5 mod 5] which are basically philosophers 2 and 0 respectively.
Array state[I] can have one of the three values (thinking, hungry, or eating). Another array required is the array condition. Array condition[I] can be either signal or wait. As we said before, if a philosopher[I]'s state[I] is "hungry" he declares his condition[I] by "wait", and when he eats i.e. state[I] has just became "eating" he switches his condition[I] to "signal".
The algorithm then becomes as follows:
At an instance dp, a philosopher[I] invokes 2 procedures:
Dp.pickup(I)
{…Eat…}
Dp.putdown(I)
These procedures are as follow:
Dining-philosopher algorithm
Array state [0..4] of (thinking, hungry, eating)
Array condition [0..4] of (signal, wait)
a. Procedure pickup(I)
State[I] = hungry
Test(I) {"test" is another procedure that checks
if the two neighbors are not eating]
If state[I] ≠ eating then condition[I] = wait
b. procedure putdown(I)
state[I] = thinking
Test((I + 4) mod 5)
Test((I + 1) mod 5)
c. procedure Test(I)
if state[(I + 4) mod 5] ≠ eating and
state[I] = hungry and state[(I + 1) mod 5] ≠ eating
then
state[I] = eating
condition[I] = signal