Riddle of the pilgrims

The Riddle of the Pilgrims

The Canterbury Puzzles is a delightful collection of posers based on the exploits of the same group of pilgrims introduced by Geoffrey Chaucer in The Canterbury Tales. The anthology was compiled by the English puzzlist Henry Ernest Dudeney and first published in 1907. All the puzzles are mathematical in nature and many of them may be used to illustrate O.R. techniques. The following riddle, taken from the chapter entitled ‘The Merry Monks of Riddlewell’ is a classical I.P. allocation problem.

One day, when the monks were seated at their repast, the Abbot announced that a messenger had that morning brought news that a number of pilgrims were on the road and would require their hospitality. “You will put them,” he said, “in the square dormitory that has two floors with eight rooms on each floor. There must be eleven persons sleeping on each side of the building, and twice as many on the upper floor as the lower floor. Of course every room must be occupied, and you know my rule that not more than three persons may occupy the same room.” I give a plan of the two floors, from which it will be seen that the sixteen rooms are approached by a well staircase in the centre. After the monks had solved this little problem of accommodation, the pilgrims arrived, when it was found that they were three more in number than was at first stated. This necessitated a reconsideration of the question, but the wily monks succeeded in getting over the new difficulty without breaking the Abbot’s rules. The curious point of this puzzle is to discover the total number of pilgrims.

IP formulation

The monks were required to perform two allocations of pilgrims each fulfilling the Abbot’s requirements and with a difference of three pilgrims in total between each allocation. On their behalf, we therefore define variables as follows

where $n = 2$ (allocations), $f = 2$ (floors), $r = 3$ (rows) and $c = 3$ (columns).

Maximize/minimize the number of pilgrims in the final allocation. This is to demonstrate that the solution to the puzzle is unique.

1. Three more pilgrims in final allocation than in initial allocation

2. Twice as many pilgrims on upper floor than lower floor in both allocations

3. Eleven pilgrims in first and third rows (i.e. front and back sides)

4. Eleven pilgrims in first and third columns (i.e. left and right sides)

5. Each room is atleast oocupied by at least one and no more than three pilgrims

6. No pilgrims allocated to the center cells (i.e. well stair case)

The Python code for solving the puzzle using Google OR-Tools library is given below:

from ortools.linear_solver import pywraplp

def riddle_of_pilgrims():
    n, f, r, c = 2, 2, 3, 3
    solver = pywraplp.Solver.CreateSolver('SCIP')
    x = {(i,j,k,m): solver.IntVar(0, 3, 'x[%i][%i][%i][%i]' % (i,j,k,m)) 
            for m in range(c) for k in range(r)
            for j in range(f) for i in range(n)}

    solver.Add(sum([x[(0,j,k,m)] for j in range(f) 
        for k in range(r) for m in range(c)]) + 3 ==
        sum([x[(1,j,k,m)] for j in range(f) 
        for k in range(r) for m in range(c)]))
       
    for i in range(n):
        solver.Add(2*sum([x[(i,0,k,m)] for k in range(r) for m in range(c)]) ==
            sum([x[(i,1,k,m)] for k in range(r) for m in range(c)]))
        
    for i in range(n):
        for k in set(range(r)) - {1}:
            solver.Add(sum([x[(i,j,k,m)] for j in range(f) for m in range(c)]) == 11)

    for i in range(n):
        for m in set(range(c)) - {1}:
            solver.Add(sum([x[(i,j,k,m)] for j in range(f) for k in range(r)]) == 11)

    for i in range(n):
        for j in range(f):
            for k in set(range(c)):    
                for m in set(range(c)):
                    if (k,m) != (1,1):
                        solver.Add(x[(i,j,k,m)] >= 1)
                        solver.Add(x[(i,j,k,m)] <= 3)

    for i in range(n):
        for j in range(f):
            solver.Add(x[(i,j, 1, 1)] == 0)

    solver.Minimize(sum([x[(1,j,k,m)] for j in range(f) 
                        for k in range(r) for m in range(c)]))

    status = solver.Solve()
    if status == pywraplp.Solver.OPTIMAL:
        return solver.Objective().Value()
    else:
        return -1

print(riddle_of_pilgrims())

Using the code above, we see that the total number of pilgrims is $\textbf{30}$.