Logic puzzle solving


download program
look at Delphi source code
download Delphi project

This article describes how to solve logic puzzles by computer.

The problem

5 persons : Mary, William, Peter, Ann and Rose,
5 tasks   : homework, examination, test, scription, paper
5 subject : language, math, geology, history, biology
5 ratings : 3,5,6,7 en 9

The conditions are:
1) The person making the scription had a higher score 
   than the person doing math, but a lower score than Rose.
2) Peter is not the person that did the homework.
   However he had a higher score than Ann, but a lower score than the person 
   doing history.
   Also we know that Peter did not score 4 or 6 points higher than 
   the person doing the examnination.
3) The girl doing the test had a higher score than Mary who did not do language
   but a lower score then the person doing biology.
4) William did geology and had a higher score than the person doing language.
   However his score was lower than the person making the paper.
----------------------------------------------------------------------------
Which task, subject and score belongs to which person?




The attached program finds the solution.
The approach is to generate all possible combinations until one is found
that satisfies all restrictions.

Programming information

--------------------------------
Below is the initial table to start with:
--------------------------------------------------------------
                             column                           |
--------------------------------------------------------------
0           1             2                   3               |
person |   task       |  subject        |   rating  |     row |
--------------------------------------------------------------
mary      homework       language             3     |      0  |
wiliam    examination    math                 5     |      1  |
peter     test           geology              6     |      2  |
ann       scription      history              7     |      3  |
roseie    paper          biology              9     |      4  |
--------------------------------------------------------------

While search for solutions, the persons in column 0 keep their position.
The rows in columns 1..3 however trade position until a good combination is found.

The tasks, subjects, persons and scores are denoted in the program by their 
row postion, so as 0,1,2,3 or 4.
The persons have the row number, as their postion is never changed.

Per column there are 5! = 120 sequences of tasks, subjects and scores.
A sequence is denoted by a number 0..119.
We need 3 of these numbers, which occupy array permNr[1..3].
(permutation is the math name for sequence)
PermNr[2] holds the permutation of column 2.

Above table holds permutation 0 of each column.

The numbers permutNr[1], permutNr[2] and permutNr[3] make a counter.
Each "number" counts 0..119, at 120 the counter overflows and a carry increases the 
next position.
PermutNr[1] being 120 resets itself to zero and increases PermutNr[2], etcetera.
In this way, all possible sequences are generated in an orderly way.

The conversion of a sequnce number to the actual sequence is done in this way:
(say we want to calculate permutation number 88)

   make permutation 0 first which is 0 1 2 3 4
   divide 88 by 24 = 3  (88 div 24 = 3)    note: 24 = 4!
   take the third element out of the row , which is -3-
   the remainder of the division  88/24   = 16   (88 mod 24 = 16)
   Remove the 3 from the row, which now becomes 0 1 2 4 x
   divide by 16, 16 div 6 = 2
   Take the second element from the row, the -2-
   16 mod 6 = 4   note: 6 = 3!
   Remove the 2 from the row, which becomes 0 1 4 x x
   4 div 2 = 2
   Take the second number out of the row, the -4-
   4 mod 2 = 0
   Remove 4 from the row, which becomes 0 1 x x x
   0 div 1 = 0
   Take number 0 from the row, which is the -0-
   The new row now is 1 x x x x
   Take the number left , the -1-
   Sequence number 88 is  3 2 4 0 1

Applying this sequence to the column "task" we get:

   scription
   test
   paper
   homework
   examination

Division by 24, 6, 3 and 1 is because of this reason:
there are 24 permutations of 4 elements. 
So they make a modulo 24 counter.
Therefore, the first 24 permutations will start with number -0-.
Permutations 24..47 will start with number -1- , etcetera.

Number div 24 gives the left most element.
This element must be removed from the list because we may not select it again.
Number mod 24 is de division remainder and with this number we continue.
Now, 4 more number must be selected.
The lowest 3 make a modulo 3! = 6 counter so the leftmost number 
is found by div 6.
remainder = remainder mod 6 is the number to continue with.
Selected numbers are removed.
Finally we add the number left.

To avoid making the same calculation all over again
a table is generated at create time : array permuts[0..4,0..119] of byte
holds 120 permutions (rows) 0f numbers 0,1,2,3,4.