Алгоритм поиска пандиагональных квадратов 6-го порядка
Ниже описывается алгоритм поиска пандиагональных магических квадратов шестого порядка. Это одна из вариаций алгоритма, описанного Н.Макаровой. В моей реализации немного изменен порядок вычисления свободных переменных и введены дополнительные ограничения, устраняющие изоморфные варианты.

Решая систему линейных уравнений для пандиагонального квадрата 6-го порядка получаем следующие зависимости для элементов:

m0m1m2m3m4m5
m6m7m8m9m10m11
m12m13m14m15m16m17
m18m19m20m21m22m23
m24m25m26m27m28m29
m30m31m32m33m34m35
S - магическая сумма квадрата

m0 = -m1-m2-m3-m4-m5+S
m1 = -m2-m3-m4-m5+m7+m14+m21+m28+m35
m2 = +m17-m19-2*m20-m21-m25-2*m26-m27+m29-m31-m32-m33+m35+3/2*S
m3 = -m17+m19+m20-m27-m28-m29-m32-m33-m34-m35+7/6*S
m4 = +m17-m19-m20-m21-m22-m26-m27-m28-m33-m34+3/2*S
m5 = -m17+m19+m20+m21-m23+m25+2*m26+m27-m29+m31+m32+m33-m35-5/6*S
m6 = -m7-m8-m9-m10-m11+S
m7 = +m11-m14+m16+m26-m28+m31-m35
m8 = +m19+m20+m21+m25+m26+m27-m29+m31+m32+m33-7/6*S
m9 = +m11+m12-m14-m24+m26+m33-m35
m10 = +m21+m22+m23-m25+m27+m28+m29+m33+m34+m35-7/6*S
m11 = -m19-m20-m21-m25-2*m26-m27-m31-m32-m33+11/6*S
m12 = -m13-m14-m15-m16-m17+S
m13 = +m17-m19-m20+m22+m23-m25-m26+m28+m29-m31+m35
m15 = +m17-m19-2*m20-2*m21-m22-m25-2*m26-2*m27-m28-m33+m35+2*S
m16 = -m17+m19+m20-m22-m23+m25+m26-m28-m29-m34-m35+2/3*S

m14 = -m17-m32-m35+2/3*S
m18 = -m19-m20-m21-m22-m23+S
m24 = -m25-m26-m27-m28-m29+S
m30 = -m31-m32-m33-m34-m35+S

Поиск квадрата производится из массива, содержащего не менее 36-ти чисел. Одно из чисел массива используется как элемент m35 (правый нижний угол квадрата). Для остальных свободных переменных делается перебор из оставшихся чисел массива. Если перебор завершен, и квадрат не найден, значит, не существует квадрата, содержащего элемент m35 и его можно удалить из массива чисел. Из оставшихся чисел выбираем другой элемент и так далее пока есть не менее 36-ти чисел. Т.е. нужно сделать перебор L-35 раз (L - начальный размер массива).

От порядка, в котором выбираются угловые элементы, сильно зависит общее время перебора. Так, для чисел Смита, если брать отсортированный по возрастанию массив чисел, лучше начинать с конца массива. Дело в том, что в этом случае для последних чисел существует меньшее количество шестерок чисел с суммой S. Так что последние числа проверяются очень быстро. Можно на каждом шаге проверять проверять количество шестерок для всех элементов и выбирать элемент с минимальным количеством.

Немного об отклонениях. Идея была предложена svb на форуме dxdy.ru и позволяет отсечь некоторые варианты. Подробнее об отклонениях можно посмотреть на сайте svb. Здесь я приведу только основные соотношения для понимания работы алгоритма. Посмотрим на зависимость:

  m14 = -m17-m32-m35+2/3*S 

ее можно записать как

  m14+m35 = 1/3*S + p 
  m17+m32 = 1/3*S - p 

здесь p - так называемое отклонение от комплементарности . Из-за переноса на торе получаем девять таких отклонений, а условия для диагоналей квадрата дают нам шесть соотношений для этих отклонений.

  p1 + p5 + p9 = 0 
  p3 + p5 + p7 = 0 
  p1 - p6 - p8 = 0 
  p9 - p2 - p4 = 0 
  p3 - p4 - p8 = 0  
  p7 - p2 - p6 = 0 

Посмотрим на примере переход от этих условий к условиям для диагонали квадрата:

  p1 - p6 - p8 = 0 
  S/3 - (m3 + m18) - (m8+m29 - S/3) - (m13 - m34 - S/3) = 0 
  S = m3 + m8 + m13 + m18 + m29 + m34 

Вариант этой схема предложил Pavlovsky на том же форуме. Им же предложены условия нормализации для удаления изоморфных вариантов.

  P11 ≤ P22, P22 ≤ P42, P22 ≤ P31, P42 ≤ P71 

Учитывая, что

  P11 = S/3+p1 
  P12 = S/3-p1 

можно эти условия переписать для отклонений:

  +p1 ≤ -p2 
  -p2 ≤ -p4 
  -p2 ≤ +p3 
  -p4 ≤ +p7 

Кстати, еще одна зависимость m7 = +m11-m14+m16+m26-m28+m31-m35 связывает четыре отклонения и, по-моему, аналогична зависимостям Pavlovsky :

 p5+p9 = -p6-p8

Вернемся к нашему алгоритму. Получим для текущего массива чисел список возможных отклонений. Этот список будет использоваться для проверки вычисленных отклонений.

Такой список можно получить следующим образом. Для текущего массива чисел перебираем все четверки чисел a < b < c < d, с суммой = 2/3*S. Каждая такая четверка дает шесть отклонений.

 (a+b) - S/3
 (c+d) - S/3
 (a+c) - S/3
 (b+d) - S/3
 (a+d) - S/3
 (b+c) - S/3

Все различные отклонения сохраняем в списке.

Еще один момент - устранение изоморфных вариантов. Три поворота дают нам три варианта одного квадрата. Отражение относительно диагонали и три поворота дают еще четыре варианта. Все варианты показаны на рисунке ниже. После каждого поворота/отражения делаем перенос на торе, чтобы выбранный нами элемент m35 оставался в правом нижнем углу.




Очевидный способ отбросить квадраты, полученные отражением относительно диагонали - сравнить два элемента, симметричные относительно нее же. Такое сравнение должно выполняться как можно ближе к началу перебора. У меня это сравнение эдементов m32 и m17. На рисунке это элементы [7] и [r]. Оставим, например, варианты с элементом [7] в нижней строке квадрата (эти четыре квадрата выделены зеленой рамкой).

Еще две пары получены перестановкой столбцов (Посмотрите на нижнюю строку оставшихся квадратов). Отсюда второе условие. Если проверены квадраты с нижней строкой [abcdef], то можно не проверять квадраты с нижней строкой [edcbaf].

Оставшиеся два квадрата (два левых квадрата на рисунке) получены перестановкой строк. Из них тоже можно оставить один (почти всегда). Для этого достаточно сравнить два отклонения. Например, задать условие p3 ≤ -p6 (посмотрите на расположение элементов [x] и [c] в обеих квадратах). (если окажется p3=p6, мы все-таки получим оба квадрата).

Наконец, рассмотрим порядок перебора и вычисления элементов квадрата.

1. Элемент m35 выбран, остальные свободные переменные выбираются из всего списка.

2. Выбираем m31, m32, m33, m34, вычисляем m[30] := -m[31]-m[32]-m[33]-m[34]-m[35]+S. Если строка [m30,m31,m32,m33,m34,m35] (или симметричная ей строка [m34,m33,m32,m31,m30,m35]) уже проверена, пропускаем ее. Если нет, добавляем ее в список проверенных.

3. Выбираем m17. Пропускаем симметричные варианты (m17 > m32). Вычисляем m[14] := -m[17]-m[32]-m[35]+2*S3; и p9 := S3 - (m[17] + m[32]);

4. Выбираем m16. Вычисляем m[13] := -m[16]-m[31]-m[34]+2*S3; и p8 := S3 - (m[16] + m[31]);

5. Выбираем m15. Вычисляем m[12] := -m[15]-m[30]-m[33]+2*S3; и p7 := S3 - (m[15] + m[30]);

6. Выбираем m11 и m26. Здесь мы можем вычислить оставшиеся отклонения

 p6 := S3 - (m[11] + m[26]);
 p1 := p6 + p8;
 p5 := -p1 - p9;
 p3 := -p7 - p5;
 p4 := p3 - p8;
 p2 := p9 - p4; 

для отклонений p3, p6 проверяем условие, устраняющее симметричные варианты (p3 ≤ -p6).

Вычисленные здесь отклонения p6, p1, p5, p3, p4, p2 проверяем по списку возможных отклонений. Если отклонения нет в списке, для него не найдется четверки чисел, и этот вариант можно пропустить.

7. Выбираем m28. Вычисляем m[7] := +m[11]-m[14]+m[16]+m[26]-m[28]+m[31]-m[35]; Вычисленное значение проверяем по отклонению: p5 = (m[7] + m[28]) - S3

8. Выбираем m25. Вычисляем m[10] := S3 - p5 - m[25];

9. Выбираем m29. Вычисляем m[8] := S3 + p6 - m[29];

10. Выбираем m27. Вычисляем:

 m[24] := -m[25]-m[26]-m[27]-m[28]-m[29]+S;
 m[6] := S3 + p4 - m[27];
 m[9] := S3 -p4 - m[24];

11. Выбираем m21. Вычисляем m[0] := S3 + p1 - m[21];

12. Выбираем m20. Вычисляем m[5] := S3 - p3 - m[20];

13. Вычисляем остальные элементы:

 m[19] := -m[11]-m[20]-m[21]-m[25]-2*m[26]-m[27]-m[31]-m[32]-m[33]+11*S6;
 m[23] := -m[17]+m[19]+m[20]+m[21]-m[5]+m[25]+2*m[26]+m[27]-m[29]+m[31]+m[32]+m[33]-m[35]-5*S6;
 m[22] := -m[17]+m[19]+m[20]-m[16]-m[23]+m[25]+m[26]-m[28]-m[29]-m[34]-m[35]+2*S3;
 m[18] := -m[19]-m[20]-m[21]-m[22]-m[23]+S;
 m[4] := +m[17]-m[19]-m[20]-m[21]-m[22]-m[26]-m[27]-m[28]-m[33]-m[34]+3*S div 2;
 m[3] := -m[17]+m[19]+m[20]-m[27]-m[28]-m[29]-m[32]-m[33]-m[34]-m[35]+7*S6;
 m[2] := +m[17]-m[19]-2*m[20]-m[21]-m[25]-2*m[26]-m[27]+m[29]-m[31]-m[32]-m[33]+m[35]+3*S div 2;
 m[1] := -m[0]-m[2]-m[3]-m[4]-m[5]+S; 

Заключение.

Реализация этого алгоритма проверена на константе 5964 для чисел Смита = 4 (mod 9). Время работы на массиве из 36-ти чисел менее 10-ти секунд. Для константы 3912 полная проверка 39-ти чисел заняла 10 минут. К сожалению время проверки очень быстро растет с увеличением количества чисел в массиве. На полном массиве могу пока дать только грубую оценку времени выполнения - 40-50 часов для константы 5964.

comment
Проверил константу 4884 (88 чисел Смита = 4 (mod 9)). Проверка заняла около 40 часов.

Ниже программа для проверки и исходники (Delphi). Проверку можно делать как для произвольного массива из файла, так и просто задавая константу - нужные числа программа выберет сама.
Downloads
Приложение - поиск пандиагональных квадратов 6x6 (test6p.zip) (802.1 Кб, просмотров: 439 )
Исходники (Windows/Delphi) (src6p.zip) (763.1 Кб, просмотров: 442 )

Comments
21.09.2016 01:57 juliadiets.com
 Магический квадрат 4?4, изображённый на гравюре Альбрехта Дюрера « Меланхолия I », считает
 ся самым ранним в европейском искусстве.
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by