Al-Maghribî’s Mecca Problem Meets Sudoku – The Statement and Solution of the Mecca Problem

What does an old riddle of a seventeenth century mathematician, Ali bin Veli Ibn Hamza al-Cezâirî (d. 1614), commonly known as Ibn Hamza Al-Maghribî, have to do with Sudoku, a modern-day popular Japanese puzzle that is a staple of our daily newspapers? Before we give an answer, let us first describe the old riddle.

Ibn Hamza was born in Algiers – in fact, the title Al Maghribî (the one from the west) seems to be given to him because of his Algerian origins. Towards the end of the sixteenth century he moved to Istanbul, then the capital of the Ottoman Empire, to complete his education and most likely stayed there until his death. He was an algebraist who also made important contributions to probability, hydrodynamics, mechanics, medicine, and geology.

The only written work Ibn Hamza left behind was a treatise called Tuhfetu'l – Âdâd lizevil Rüşd ve's – Sedad (The Ornament of Numbers). This was a 500-page book written in Ottoman Turkish containing some elementary theorems of Euclid and solutions of various Diophantine problems, and even some form of logarithms (Djebbar 2003). It comprised an introduction, four sections, and an appendix. The first section was on the properties of integers and the four basic operations on integers. The second section was devoted to developing rules of computations with rational and irrational numbers and methods of finding square, cube, and fourth roots. The third section dealt with approximate solutions of equations by various techniques such as the method of proportions or the regula falsi method (see Note). The fourth section presented some theorems of elementary geometry, and some formulas to calculate the areas of triangles, rectangles, circles, and volumes of regular solids. The Appendix – more or less the most original part of the book – contained several fascinating problems, including the one we are about to discuss, which the author solved using some peculiar methods.

The problem we are interested in can be stated as follows:

A landowner who has 81 trees, gets every year 1 unit of fruit from the first tree, 2 units from the second tree, … , and 81 units from the eighty-first tree. How should he divide these trees among 9 inheritors so that each inheritor gets 9 trees and an equal amount of yearly produce?

In his book, Ibn Hamza referred to this problem as the “Mecca problem,” possibly because it was suggested to him by an amateur Indian mathematician, Molla Mohammed, on the way to Mecca circa 1590 (Dilgan 1957).

Since the 81 trees will yield a total of \(1+\cdots+81=\frac{81\cdot82}{2}=3321\) units per year, each inheritor should get \(\frac{3321}{9}=369\) units of fruit per year. Thus, the problem is equivalent to solving a 9 x 81 indeterminate system of equations, where each variable is a unique integer between 1 and 81:

where \(x_{ij}\) stands for the number of units of fruit produced annually by the \(j\)th tree inherited by the \(i\)th heir, subject to the condition \(x_{ij}\not=x_{i^{\prime}j^{\prime}}\) for \(i\not=i^{\prime}\) or \(j\not=j^{\prime}.\)

Here is Al-Maghribî’s rather elegant original solution (Dilgan 1957): Number the trees 1, … , 81 according to the amount they yield, and place these numbers in a 9 x 9 table in the following way: Put 1 in the (1,1) position, then continue to the right along the first row, placing the numbers 2, 3, … , 9 in consecutive cells. Now move to cell (2,2) and put the next number, 10, in this position. Continue to the right along the second row, placing the numbers 11, … , 17 in the cells. Place the next integer, 18, in cell (2,1). Then start at cell (3,3) with the integer 19 and continue to the right by placing successive integers to fill up the remaining cells in the third row. Fill in the first two positions of this row with integers 26 and 27. Continue in this fashion to obtain the following table:

Table 1

Note that the sum of each column is equal to 369. Thus, a solution to the problem is that the first inheritor gets trees numbered 1, 18, 26, 34, … , 74; the second inheritor gets the trees numbered 2, 10, … , 75; … ; and the ninth inheritor gets the trees numbered 9, 17, 25, … , 73.

We notice that along with the column sums being 369, the secondary diagonal sum is also 369. However, this table is not a magic square: the numbers in the rows (except for the fifth row) and along the main diagonal do not add up to 369. Strictly speaking, it is not a Latin square either, for although we have an \(n\times n\) matrix where no entry occurs twice in any row or column, these entries do not satisfy the condition \(1\le x_{ij}\le n.\) Nor could it possibly be a completed Sudoku puzzle for the same reason: it contains entries other than 1 through 9.

However, there is a simpler way of perceiving the table representing Al Maghribî’s solution, a way that involves Latin squares. Let us subtract 0 from each entry of the first row of Table 1, 9 from each entry of the second row, 18 from each entry of the third row, and so on, until we subtract 72 from each entry of the last row. That is, let us construct a table with entries \(y_{ij}\) defined by the equation \[y_{ij} = x_{ij} - 9(i-1)\] for \(1\le i\le 9\) and \(1\le j\le 9,\) as depicted below:

Table 2

We note that Table 2 consists of nine rows and nine columns of permutations of the first nine integers, a property that any finished Sudoku puzzle shares. Although Table 2 is not a solution to a Sudoku puzzle (why not?), it is a 9 x 9 Latin square. Moreover, if we start with any other 9 x 9 Latin square with entries 1 through 9 – in particular, any completed Sudoku puzzle – and add 0 to each entry of the first row, 9 to each entry of the second row, 18 to each entry of the third row, … , and 72 to each entry of the ninth row, we would obtain a different solution to Al-Maghribî’s problem. Try it next time you complete a Sudoku puzzle!

This gives us a multitude of solutions to the original problem, namely 5524751496156892842531225600 solutions – the number of different 9 x 9 Latin squares (Bammel and Rothstein 1975) – assuming inheritors are distinct.

_______________________________________

Note. In the third section of Tuhfetu'l – Âdâd lizevil Rüşd ve's – Sedad, Ibn Hamza also described some algebraic manipulations such as al-jabr, a word which originally referred to mending a broken bone and which can be best translated as “restoration or reunion of broken parts” – that is, combining like terms on one side of an equation – and al-muqabala, which literally means a “face-off” and can be better translated as “confrontation” or “reduction” – that is, reducing terms appearing on both sides of an equation to a single term on one side of the equation. These ideas, of course, originated in the Hisab al-jabr w'âl muqabala of al-Khwarizmi (780–circa 850). It is likely that Ibn Hamza actually learned them from more contemporary works. Back to top