| Главная | Эксперименты | Утилиты | Компоненты | Что почитать | Контакты |
|
Решая систему линейных уравнений для пандиагонального квадрата 6-го порядка получаем следующие зависимости для элементов:
|
От порядка, в котором выбираются угловые элементы, сильно зависит общее время перебора. Так, для чисел Смита, если брать отсортированный по возрастанию массив чисел, лучше начинать с конца массива. Дело в том, что в этом случае для последних чисел существует меньшее количество шестерок чисел с суммой 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 часов.
|