AI & ES Famous Problems

Water Jug Problem
This is an old chestnut, one I'm sure you will recognise! You have two jugs, one of which holds 5 pints and the other of which holds 3 pints, and an endless supply of water. Your task is to get 4 pints of water in the 5 pint jug - but you have no way of measuring 4 pints directly! You can't put "roughly" 4 pints in and hope for the best.
Solution
The way to do it is to fill the jugs to their capacity (the only accurate measurements that you know) and to transfer water between the jugs. For instance, if the 5 pint jug were full and the 3 pint jug were empty, then filling the 3 pint 
jug from the 5 pint jug would leave exactly 2 pints in the 5 pint jug. In fact, here are the t
hings that you can do:
1.     Fill the 5 pint jug from the tap
2.     Fill the 3 pint jug from the tap
3.     Empty the 5 pint jug down the drain
4.     Empty the 3 pint jug down the drain
5.     Pour as much of the contents of the 5 pint jug into the 3 pint jug as will fit (what I term "filling" the 3 pint jug - even though it may not end up full).
6.     Filling the 5 pint jug from the 3 pint j
ug in a similar manner.
The contents of the jugs are shown as numbers in column B and C and also graphically in columns E to I (for the 5 pint jug) and K to M (for the 3 pint jug). The initial contents of the jugs are given in cells B4 and C4 and all the values below them in the column are calculated from these initial values and the commands entered in column A.
The calculations are done as a series of nested IF statements, as shown in the screen dump above. Basically, these test to see if 1 or 2 has been entered in the column A cell, in which case the value should be 5 or 3 (depending on which jug it is), or whether 3 or 4 has been entered, in which case the appropriate jug contents is set to 0.
The difficulty comes with options 5 and 6. These pour as much of the contents of one jug into the other as will fit. This requires quite a lot of temporary working out, which is done in columns P to S. Columns P and Q give the contents of the jugs assuming that the 3 pint jug is being filled from 5 pint jug, and columns R and S give the contents of the jugs assuming that the 5 pint jug is being filled from the 3 pint jug. Columns P and R give the contents of the 5 pint jug in each case, columns Q and S give the contents of the 3 pint jug.
The cells in columns E to M have had borders put round them to indicate the different sized jugs. The text colour of the cells has been set to blue and they contain formulae which display $$$ (the closest representation for water I could think of!) when the appropriate values appear in the corresponding cells in columns B and C.
Finally, there is a formula copied down column N which displays the message "Well done! You have solved the puzzle!" if it detects that the value in the corresponding cell of column B is 4 (i.e. you have succeeded in getting 4 pints in the 5 pint jug).
 YOU CAN DOWNLOAD THIS SPREADSHEET FROM THE LINK AS GIVEN BELOW.
8 Queen Problem
The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard, where solutions exist only for n = 1 and n ≥ 4.
Solution for 8 queen problem
    The problem can be quite computationally expensive as there are 4,426,165,368 (64×63×...×58×57/8!, where the "!" stands for Factorial) possible arrangements, but only 92 solutions. It is possible to use shortcuts that reduce computational requirements or rules of thumb that avoids brute force computational techniques. For example, just by applying a simple rule that constrains each queen to a single column (or row), though still considered brute force, it is possible to reduce the number of possibilities to just 16,777,216 (8^8) possible combinations, which is computationally manageable for n=8, but would be intractable for problems of n=1,000,000. Extremely interesting advancements for this and other toy problems is the development and application of heuristics (rules of thumb) that yield solutions to the n queens puzzle at an astounding fraction of the computational requirements. This heuristic solves nqueens for any n n ≥ 4 or n = 1:
1.     Divide n by 12. Remember the remainder (n is 8 for the eight queens puzzle).
2.     Write a list of the even numbers from 2 to n in order.
3.     If the remainder is 3 or 9, move 2 to the end of the list.
4.     Append the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
5.     If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
6.     If the remainder is 3 or 9, move 1 and 3 to the end of the list.
7.     Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.
For n = 8 this results in the solution shown above. A few more examples follow.
  • 14 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 queens (remainder 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 queens (remainder 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
  
The Travelling and Salesman problem
Introduction
Caveat This has been very much an occasional hobby over recent years, and I have not had the time to keep abreast of the literature. Some of what I say might be out of date.
The Travelling Salesman Problem (TSP) is a deceptively simple combinatorial problem. It can be stated very simply:
n-city tourA salesman spends his time visiting n cities (or nodes) cyclically. In one tour he visits each city just once, and finishes up where he started. In what order should he visit them to minimize the distance travelled?
Many TSP's are symmetric - that is, for any two cities A and B, the distance from A to B is the same as that from B to A. In this case you will get exactly the same tour length if you reverse the order in which they are visited - so there is no need to distinguish between a tour and its reverse, and you can leave off the arrows on the tour diagram.
If there are only 2 cities then the problem is trivial, since only one tour is possible. For the symmetric case a 3 city TSP is also trivial. If all links are present then there are (n-1)! different tours for an n city asymmetric TSP. To see why this is so, pick any city as the first - then there are n-1 choices for the second city visited, n-2 choices for the third, and so on. For the symmetric case there are half as many distinct solutions - (n-1)!/2 for an n city TSP. In either case the number of solutions becomes extremely large for large n, so that an exhaustive search is intractable. 
The problem has some direct importance, since quite a lot of practical applications can be put in this form. It also has a theoretical importance in complexity theory, since the TSP is one of the class of "NP Complete" combinatorial problems. NP Complete problems have intractable in the sense that no one has found any really efficient way of solving them for large n. They are also known to be more or less equivalent to each other; if you knew how to solve one kind of NP Complete problem you could solve the lot.
The holy grail is to find a solution algorithm that gives an optimal solution in a time that has apolynomial variation with the size n of the problem. If you could find a method whose solution time varies like a quadratic expression, for example, then doubling n multiplies the solution time by 4 for large n. The best that people have been able to do, however, is to solve it in a time that varies exponentially with n. Such algorithms run out of puff at a certain level of n, more or less independently of computing power. If computation varies as 2^n, say, then a thousand-fold increase in computing power will only allow you to add another 10 nodes. So an algorithm that peters out at 50 cites now will probably never get you to 100 nodes, whatever happens to hardware technology.
Alternatively there are algorithms that seem to come up with a good solution quite quickly, but you cannot say just how far it is from being optimal.
Getting the feel of it
Recently I have been experimenting with some ideas that I had back in 1970. The graphic capability and speed of a PC (compared to the IBM 1130 I used in 1970) makes it a good tool for visualizing what is going on. The result is a small DOS program that you might like to play with. What it does is to generate a sequence of symmetric travelling salesman problems, and then solve them using two different algorithms. The nodes are placed at random positions on a rectangular grid and I simply use the straight line distances between them. The virtue of doing it this way is that the problems are easy to generate and easy to visualize. As each problem is generated, the nodes are displayed graphically on the screen, so you if you like can try your hand at guessing where the shortest tour might go.
The first algorithm looks for a true optimum tour by doing a truncated search of the entire solution space - known as the Branch and Bound technique. It reaches an initial tour very quickly, and then continues to search, finding better tours and/or establishing that no shorter tour exists. As each tour is found it is drawn on the screen, and details are entered in a file calledtsp.log. This algorithm is quite fast up to about 25 nodes, but becomes painfully slow beyond 40.
The good news is that you can truncate the search at any time by hitting any key. You can also set a % bound margin; setting this to 10 means that you wind up with a tour whose length is within 10% of the shortest - but you get there rather more quickly than if you insist on a true optimum (margin=0). If you like you can set the margin at 100, so it gives up immediately after finding the solution.
The second algorithm  starts from a random tour and seeks to improve it using an algorithm base on dynamic programming. When no further improvement is obtainable the tour is displayed and details are logged. The process is repeated using 5 different random starting points. You will see that the algorithm is fast for problems with up to 100 nodes (the limit of the program). It often finds the true optimum tour and, when it doesn't, gets within a couple of percent of the shortest length. Because the first algorithm runs out of puff above 40 nodes, however, it is hard to say how well it sustains its performance for really large problems.
8-puzzle Problem
         8 puzzle is a simple game which consists of eigth sliding tiles, numbered by digits from 1 to 8, placed in a 3x3 squared board of nine cells. One of the cells is always empty, and any adjacent (horizontally and vertically) tile can be moved into the empty cell. The objective of the game is to start from an initial configuration and end up in a configuration which the tiles are placed in ascending number order.
a screen shot of 8 puzzle solution finder and you can download it from this link
Missionaries and Cannibals Problem
   In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board.
    
Trip number
Starting bank
Travel
Ending bank
(start)
Aa Bb Cc
1
Bb Cc
Aa →
2
Bb Cc
← A
A
3
A B C
bc →
A
4
A B C
← a
b c
5
Aa
BC →
b c
6
Aa
← Bb
Cc
7
a b
AB →
Cc
8
a b
← c
A B C
9
b
a c →
A B C
10
b
← B
Aa Cc
11
Bb →
Aa Cc
(finish)
Aa Bb Cc
 In the jealous husbands problem, the missionaries and cannibals become three married couples, with the constraint that no woman can be in the presence of another man unless her husband is also present. Under this constraint, there cannot be both women and men present on a bank with women outnumbering men, since if there were, some woman would be husbandless. Therefore, upon changing women to cannibals and men to missionaries, any solution to the jealous husbands problem will also become a solution to the missionaries and cannibals problem
The Tower of Hanoi
The Tower of Hanoi or Towers of Hanoi (also known as The Towers of Benares) is amathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the pegs and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.
Most toy versions of the puzzle have 8 disks. The game seems impossible to many novices, yet is solvable with a simple algorithm.
Solution:
Simple solution
The following solution is a simple solution for the toy puzzle.
Alternate moves between the smallest piece and a non- smallest piece. When moving the smallest piece, always move it in the same direction (either to the left or to the right, but be consistent). If there is no tower in the chosen direction, move it to the opposite end. When the turn is to move the non-smallest piece, there is only one legal move.
Recursive solution
As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting peg f (f=from) onto a destination peg t (t=to), r being the remaining third peg and assuming  (). First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg f to peg t, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from peg f to peg t. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from peg f to another peg, preferably to peg t. The only situation that allows this move is when all smaller h-1 disks are on peg r. Hence, first all h-1 smaller disks must go from f to r. Subsequently move the largest disk and finally move the h-1 smaller disks from peg r to peg t. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 disks from one peg to another one, first from f to r and subsequently from r to t, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h-1 problem to h-2, h-3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows. Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h-1 the largest one.
The following is a procedure for moving a tower of h disks from a peg f onto a peg t, with r being the remaining third peg:
Step 1: If h>1 then first use this procedure to move the h-1 smaller disks from peg f to peg r.
Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg f to peg t.
Step 3: If h>1 then again use this procedure to move the h-1 smaller disks from peg r to peg t.
The monkey and Bananas Problem
Problem
A monkey is in a room. Suspended from the ceiling is a bunch of bananas, beyond the monkey's reach. In the corner of the room is a box. How can the monkey get the bananas?
Solution: 
The solution is that the monkey must push the box under the bananas, then stand on the box, and then grab the bananas. However, figuring this out requires a planning algorithm.
In other variants of the problem, the bananas are in a chest and the monkey first has to open the chest using a key.
 Cryptarithmetic
Cryptarithmetic is the science and art of creating and solving cryptarithms.
A cryptarithm is a genre of mathematical puzzle in which the digits are replaced by letters of the alphabet or other symbols.
The invention of Cryptarithmetic has been ascribed to ancient China. This art was originally known as letter arithmetic or verbal arithmetic. In India, during the Middle Ages, were developed the arithmetical restorations or "skeletons" a type of cryptarithms in which most or all of the digits have been replaced by asterisks.
In 1864 the first cryptarithm appeared in the USA, in American Agriculturist.
The word cryptarithmetic ("cryptarithmie" in French) was introduced by M. Vatriquant, writing under the pseudonym Minos, in the May 1931 issue of Sphinx, a Belgian magazine of recreational mathematics published in French from 1931 to 1939.
A type of alphabetic addition puzzle termed "doubly-true" was introduced in 1945 by Alan Wayne. It is made up of "number words" that, when read, also form a valid sum.
In 1955, J. A. H. Hunter coined the word alphametic to designate a cryptarithm whose letters form sensible words or phrases.
The world's best known alphametic puzzle is undoubtedly SEND + MORE = MONEY. It was created by H. E. Dudeney and first published in the July 1924 issue of Strand Magazine associated with the story of a kidnapper's ransom demand.
Modernization by introducing innovations such as computers and the Internet is making quite an impact on cryptarithmetic. If you are interested in knowing more about this revolution read the article Will cryptarithmetic survive innovation?
HOW TO SOLVE A PUZZLE
Rewrite the problem, expanding the interlinear space to make room for trial numbers that will be written under the letters.
For example, the puzzle SEND + MORE = MONEY, after solving, will appear like this:
            S E N D
            9 5 6 7
          + M O R E
            1 0 8 5
          ---------
          M O N E Y
          1 0 6 5 2
•         Each letter or symbol represents only one digit throughout the problem;
•         When letters are replaced by their digits, the resultant arithmetical operation must be correct;
•         The numerical base, unless specifically stated, is 10;
•         Numbers must not begin with a zero;
•         There must be only one solution to the problem.
Ease the analysis of subtractions by reading them as upside-down additions. Remember that you can check a subtraction by adding the difference and the subtracter to get the subtrahend: it's the same thing. This subtraction:
     
          C O U N T
            - C O I N
               ---------
             S N U B
must be read from the bottom to the top and from the right to the left, as if it were this series of additions:
       
        B + N = T + C1
        U + I = N + C2
        N + O = U + C3
        S + C = O + C4
C1, C2, C3 and C4 are the carry-overs of "0" or "1" that are to be added to the next column to the left.
A good hint to find zero or 9 is to look for columns containing two or three identical letters.
Look at these additions:
     * * * A           * * * B
  + * * * A       + * * * A
        -------                 -------
      * * * A          * * * B
The columns A+A=A and B+A=B indicate that A=zero. In math this is called the "additive identity property of zero"; it says that you add "0" to anything and it doesn't change, therefore it stays the same.
Now look at those same additions in the body of the cryptarithm:
    * A * *           * B * *
 + * A * *        + * A * *
     -------              -------
    * A * *           * B * *
In these cases, we may have A=zero or A=9. It depends whether or not "carry 1" is received from the previous column. In other words, the "9" mimics zero every time it gets a carry-over of "1".
Look for left hand digits. If single, they are probably "1".
Take the world's most famous cryptarithm:
           S E N D
        + M O R E
         ---------
         M O N E Y
"M" can only equal 1, because it is the "carry 1" from the column S+M=O (+10). In other words, every time an addition of "n" digits gives a total of "n+1" digits, the left hand digit of the total must be "1".
In this Madachy's subtraction problem, "C" stands for the digit "1":
         C O U N T
          - C O I N
         ---------
           S N U B
           S E N D
       +   M O R E
       ------------
         M O N E Y
We see at once that M in the total must be 1since the total of the column SM cannot reach as high as 20Now if M in this column is replaced by 1, how can we make this column total as much as 10 to provide the 1 carried over to the left below? Only by making S very large: 9 or 8. In either case the letter O must stand for zero: the summation of SM could produce only 10 or 11,but we cannot use 1 for letter O as we have already used it for M.
If letter O is zero, then in column EO we cannot reach a total as high as 10so that there will be no 1 to carry over from this column to SM. Hence S must positively be 9.
Since the summation EO gives N, and letter O is zero, N must be 1 greater than E and the column NR must total over 10. To put it into an equation: E + 1 = N
From the NR column we can derive the equation: N + R + (+ 1) = E + 10
We have to insert the expression (+ 1) because we don’t know yet whether 1 is carried over from column DE. But we do know that 1 has to be carried over from column NR to EO.
Subtract the first equation from the second: R + (+1) = 9
We cannot let R equal 9, since we already have S equal to 9. Therefore we will have to make R equal to 8; hence we know that 1 has to be carried over from column DE.
Column DE must total at least 12since Y cannot be 1 or zero. What values can we give D and E to reach this total? We have already used 9 and 8 elsewhere. The only digits left that are high enough are 7, 6 and 7, 5. But remember that one of these has to be E, and N is 1 greater than E. Hence E must be 5, N must be 6, while D is 7. Then Y turns out to be 2and the puzzle is completely solved.
            
                E A T
       +   T H A T
       ------------
         A P P L E
Since every four-digit number is less than 10,000 and every three-digit number is less than 1,000, the sum of two such numbers is necessarily less than 11,000. This sum, though, is a five-digit number, hence is greater than 10,000. Consequently, A must be 1 and P must be 0. Further, we can conclude that T = 9. Otherwise, we would be adding a number less than 1,000 to one less than 9,000, leaving us short of the requisite total. The units column then produces E = 8 while generating a carryover of 1 into the tens column. Together with the previously found value of A, we learn from the tens column that L = 3. Finally, the hundreds column yields the equation E + H = P + 10, where the "10" is required to accommodate the needed carryover into the thousands column. When the values of E and P are substituted into this relationship, we get 8 + H = 10, from which it follows that H = 2. Therefore, the unique solution of the puzzle turns out to be
819 + 9219 = 10038.
3. J. A. H. Hunter
                 N O
             G U N
         +     N O
         ----------
           H U N T
Obviously H = 1.
From the NUNN column we must have "carry 1," so G = 9, U = zero.
Since we have "carry" zero or 1 or 2 from the ONOT column, correspondingly we have N + U = 10 or 9 or 8. But duplication is not allowed, so N = 8 with "carry 2" from ONOT.
Hence, O + O = T + 20 - 8 = T + 12. Testing for T = 2, 4 or 6, we find only T = 2 acceptable, O = 7.
So we have 87 + 908 + 87 = 1082.
Conclusion
To solve all type of AI & ES Problem use your mind with using the tricks and rules. Once surely you can solve it.
Who solve these problem own, is intelligent and he/she has sharp mind.
  

No comments: