§3. Классические алгоритмы построения магических квадратов нечетного порядка

Индийский (сиамский) метод

Правила построения магических квадратов произвольного нечетного порядка n=2m+1:

1. Числа от 1 до поочередно вписываются в клетки основного квадрата.

2. Если некоторое правило требует вписать данное число в клетку, лежащую вне основного квадрата, то вместо этого рассматриваемое число вписывается в эквивалентную клетку основного квадрата.

3. Число 1 вписывается в среднюю клетку верхнего ряда.

4. Если число z вписано в клетку (x; y), то следующее число z+1 вписывается в клетку (x+1; y+1).

5. Если клетка (x+1; y+1) уже занята некоторым числом, то число z+1 вписывается в клетку (x; y-1).

Рассмотрим такой магический квадрат третьего порядка (рис.3.1). Число 1 вписано на основании правил 1 и 3, число 2- на основании правил 4 и 2, число 3- на основании правил 4 и 2, число 4- на основании правил 5 и 2, число 6- на основании правила 4, число 7- на основании правил 5 и 2, число 8-на основании правил 4 и 2, число 9- на основании правил 4 и 2.

Рис. 3.1. Построение магического квадрата индийским методом

Метод Москопула (метод коня)

Алгоритм последовательного заполнения клеток основного квадрата числами от 1 до :

1. Числа от 1 до поочередно вписываются в клетки основного квадрата.

2. Если некоторое правило требует вписать данное число в клетку, лежащую вне основного квадрата, то вместо этого рассматриваемое число вписывается в эквивалентную клетку основного квадрата.

3. Если n0 (mod 3), то начальная клетка, в которую вписывается число 1, выбирается произвольно; если же n?0 (mod 3), то за эту клетку принимается средняя клетка нижнего горизонтального ряда.

4. Если некоторое число z вписано в клетку (x;y), то число z+1 вписывается в клетку (x+1;y+2) при условии, что эта клетка еще свободна от чисел. магический квадрат линейный четный

5. Если клетка (x+1;y+2) уже занята некоторым числом, то число z+1вписывается в клетку (x;y+4).

Рассмотрим магический квадрат пятого порядка, построенный по данному методу (рис.3.2).

Рис. 3.2. Построение магического квадрата методом Москопула

Метод альфила

Правила построения магического квадрата:

1. Числа от 1 до поочередно вписываются в клетки основного квадрата.

2. Если некоторое правило требует вписать данное число в клетку, лежащую вне основного квадрата, то вместо этого рассматриваемое число вписывается в эквивалентную клетку основного квадрата.

3. Число 1 вписывается в клетку (0;1).

4. Если число z вписано в клетку (x;y), то число z+1 вписывается в клетку (x+2;y+2)при условии, что эта клетка еще свободна от чисел.

5. Если клетка (x+2;y+2) уже занята, то число z+1 вписывается в клетку (x+1;y+3).

Пример построения магического квадрата пятого порядка (рис.3.3).

Рис. 3.3. Построение магического квадрата по методу альфила

Метод Баше (метод террас)

Для построения магического квадрата следует выбрать на плоскости n соседних диагональных рядов, содержащих по n клеток и таких, что средняя клетка каждого ряда принадлежит нисходящей диагонали основного квадрата. Клетки левого верхнего ряда заполняются снизу вверх числами . Клетки p-го ряда, где , заполняются числами (p1)n+1, (p1)n+2, , pn (для n=9 рис.3.4).

Рис. 3.4. Заполнение магического квадрата по методу Баше

Заполненные таким образом клетки частью расположены внутри основного квадрата, частью- вне его, причем внешние клетки образуют по бокам основного квадрата четыре совершенно одинаковых выступа или террасы. Перенеся клетки террас в основной квадрат, заполним весь основной квадрат числами от 1 до (рис.3.5) [2].

Рис. 3.5. Магический квадрат по методу Баше