Магические квадраты

[Nataly-Mak]

Цитата:

Вот несколько квадратиков. В теге offtop, чтобы много места не занимали.

Здорово!

svb
Спасибо за проверку. Однако почему у нас такая большая разница во времени выполнения программы?
Я тем временем проверила следующий потенциальный массив: 227, ..., 367.
Проверяла по программе mak5. Квадратов тоже не нашлось. Время выполнения 7549.67 сек.
Таким образом, получается, что для квадратов 5-го порядка из последовательных простых чисел мы тоже имеем разрыв.

maxal
Итак, ваша формула имеет $8$ независимых переменных, а моя только $7$!
В остальном ваш алгоритм ничем не отличается от моего. Но поскольку у вас больше независимых переменных на 1, то имею основание утверждать, что мой алгоритм эффективнее вашего.
В моём алгоритме точно так же зависимые переменные вычисляются по порядку и как только есть все необходимые для их вычисления свободные переменные. И как только обнаружится, что вычисленные зависимые переменные не попадают в заданный массив чисел, вложенный цикл прерывается. Всё это я уже объясняла.

Программа, которую прислал мне svb (а я предполагаю, что он реализовал именно мою формулу для квадратов 4х4 так же, как и для квадратов 5х5) проверяет один массив мизерную долю секунды. Я проверяла по этой программе сразу сотни массивов, это занимало 2-3 секунды. Ничего эффективнее я и желать не могу.

Для квадратов 4х4 главная сложность не в проверке массивов, а в нахождении их. Поскольку числа запредельные, массивы найти очень сложно (для меня).

Более того: программа svb составлена так, что и не надо находить потенциальные наборы по 16 чисел. Достаточно ввести в программу достаточно большой массив смитов (или простых чисел) и программа сама проверит все потенциальные наборы по 16 чисел, имеющиеся во введённом массиве чисел. Правда, при этом она проверяет все потенциальные наборы, удовлетворяющие условию: сумма всех чисел набора кратна 4.

[maxal]

Nataly-Mak в сообщении #291310 писал(а):

Итак, ваша формула имеет $8$ независимых переменных, а моя только $7$!

Это потому, что я не ограничивал длину массива чисел (он может содержать больше 16 чисел). Если массив сожержит ровно 16 чисел, то можно считать, что значение $x_{10}$ тоже становится зависимым $x_{10} = S - x_1 - x_2 - x_5$, где $S$ - сумма данных 16-ти чисел, делённая на 4.

Nataly-Mak в сообщении #291310 писал(а):

В остальном ваш алгоритм ничем не отличается от моего.

Отличается. Тут важно, какие именно переменные выбраны независимыми, а какие - зависимыми, и в каком порядке происходит их перебор/вычисление. Разный выбор независимых переменных и порядка их вычисления даст разную производительность. Как я уже сказал, мой алгоритм в этом смысле гарантированно оптимальный (для произвольных массивов). Надо будет еще проверить это утверждение для случая ровно 16-ти чисел.

[Nataly-Mak]

Цитата:

Отличается. Тут важно какие именно переменные выбраны независимыми, а какие - зависимыми, и в каком порядке происходит их перебор/вычисление. Разный выбор независимых переменных и порядка их вычисления даст разную производительность. Как я уже сказал, мой алгоритм в этом смысле гарантированно оптимальный. Надо будет еще проверить это для случая ровно 16 чисел.

Нет, ну это уже немножко смешно.

Вы же, надеюсь, понимаете, что это не принципиальное отличие?
Это уже оптимизация по сути одного и того же алгоритма.
Согласна, что от выбора свободных и зависимых переменных зависит эффективность. Но вы уверены в том, что в моей программе сделано именно совсем не оптимальное распределение между свободными и зависимыми переменными? Вы ведь программу мою не смотрели (в чём я абсолютно уверена), а видели только формулу. Как же вы можете выдавать заключение о том, чего пока ещё не разбирали?
(А вы уже категорично заявили, что моя формула не является оптимальной для вычислений).

Конечно, я не могу утверждать, что мой выбор свободных переменных на 100% оптимальный. Но svb, реализуя мою формулу, сделал свой выбор (о чём он говорил, подробно анализируя мою формулу для квадрата 5х5), а третий человек сделает другой выбор. И, наверное, каждый будет считать, что сделал оптимальный выбор

Кстати сказать, я сама уже сделала одну оптимизацию программы для квадратов 4х4, переписав первоначальный вариант программы. И эта оптимизация касалась как раз порядка перебора свободных переменных и вычисления зависимых пременных. Время выполнения программы явно уменьшилось. Здесь недавно выложена последняя версия программы.

-- Пн фев 22, 2010 23:03:55 --

12d3
как я поняла, вы выложили квадраты 4х4 из последовательных простых чисел.
Если я буду делать заявку в OEIS на эту последовательность, мне нужны количества оригинальных квадратов для каждой магической константы. Пожалуйста, укажите эти количества (начиная с вашего квадрата № 5, для первых 4 квадратов у меня всё есть).

[maxal]

Nataly-Mak в сообщении #291321 писал(а):

Вы же, надеюсь, понимаете, что это не принципиальное отличие?

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

Вычислил самую эффективную формулу для случая, когда нам дано ровно 16 чисел, и поэтому известна магическая константа $S$. Выглядит эта формула так:

$$\begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ x_{13} & x_7 & x_9 & x_{14} \\ x_{15} & x_{10} & x_8 & x_{16} \\ x_5 & x_{11} & x_{12} & x_6 \end{bmatrix} $$

Независимыми переменными здесь являются $x_1$, $x_2$, $x_3$, $x_5$, $x_7$, $x_9$, $x_{13}$, зависимыми:

$$\begin{cases} x_4 = S - x_1 - x_2 - x_3 \\ x_6 = x_2 + x_3 - x_5\\ x_8 = x_4 + x_5 - x_7\\ x_{10} = x_1 + x_6 - x_9\\ x_{11} = -x_2 + x_8 + x_9\\ x_{12} = -x_3 + x_7 + x_{10}\\ x_{14} = S - x_7 - x_9 - x_{13}\\ x_{15} = S - x_1 - x_5 - x_{13}\\ x_{16} = x_7 + x_9 - x_{15} \end{cases}$$

-- Mon Feb 22, 2010 14:45:43 --

Nataly-Mak в сообщении #291321 писал(а):

Но вы уверены в том, что в моей программе сделано именно совсем не оптимальное распределение между свободными и зависимыми переменными? Вы ведь программу мою не смотрели (в чём я абсолютно уверена), а видели только формулу. Как же вы можете выдавать заключение о том, чего пока ещё не разбирали?

Я говорил про формулу, приведенную в вашей статье. Уже по тому, как именно в ней переменные зависят друг от друга, можно сказать, насколько эффективной она является. Программная реализация тут несущественна для анализа.

[Nataly-Mak]

Цитата:

Я говорил про формулу, приведенную в вашей статье. Уже по тому, как именно в ней переменные зависят друг от друга, можно сказать, насколько оптимальной она является. Программная реализация тут несущественна для анализа.

Совершенно неверное утверждение! Как же программная реализация может быть несущественна? Это что-то новое! Ведь именно в программной реализации выбирается порядок перебора свободных переменных и порядок вычисления зависимых переменных. От этого будут зависеть все влоржения циклов, а отсюда и время выполнения будет меняться.

Я же вам сказала, что сама уже один раз оптимизировала свою программу именно таким образом.

А формула-то у нас одна и та же! В формуле 7 свободных переменных и 9 зависимых (если говорить о массиве из 16 чисел). Это определяет суть алгоритма. А дальше уже идёт его реализация. И реализовать одну и ту же формулу можно по-разному. И от этого будет очень много зависеть.

В формуле, которая приведена в моей статье, переменные пронумерованы в произвольном порядке (учтён только порядок вычисления тех зависимых переменных, которые зависят не только от свободных переменных, но и от зависимых тоже). При программной реализации нумерация может быть совсем другой. Разве это непонятно?

О том же самом говорил svb, если вы читали его анализ моей формулы для квадратов 5х5 (в чём я тоже здорово сомневаюсь).

[maxal]

Эффективности можно оценить так. Пусть мы вычисляем элементы последовательно:

$$x_1,\ x_2, \dots, x_{n^2},$$

где каждый элемент является либо независимым, либо зависимым от предшествующих (вычисленных) элементов, $n$ - размер стороны квадрата.

Положим $m_i$ равным количеству независимых элементов среди первых $i$ элементов вышеуказанной последовательности. Понятно, что $m_1=1$, $m_{n^2}=k$ - общему количеству независимых элементов, промежуточные значения $m_i$ не убывают. Эффективность метода ветвей и границ напрямую связана со скоростью роста последовательности $m_i$, а именно мы хотим, чтобы она росла как можно медленнее.

Количественная оценка сложности такова: если скачки в $m_i$ происходят на индексах $j_1, j_2, \dots, j_k$ (другими словами, $x_{j_1}$, $x_{j_2}$, ..., $x_{j_k}$ являются независимыми), то сложность только перебора (без учёта отсечений) оценивается величиной:

$$(n^2 + 1 - j_1)(n^2 + 1 - j_2)\cdots(n^2+1-j_k).$$

Мы хотим, чтобы $j_i$ были как можно больше, т.е. скачки в росте $m_i$ были смещены как можно больше к хвосту этой последовательности.

Например, для формулы, которую я привел выше, последовательность $m_i$ выглядит так:

1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7

а для формулы из статьи Nataly-Mak так:

1, 2, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7

что соответсвуют оценкам сложности перебора 12902400 и 39916800. То есть, приведенная мной формула, дает ускорение как минимум в три раза (но на самом деле даже больше, в виду наличия отсечений).

-- Mon Feb 22, 2010 15:16:12 --

Nataly-Mak в сообщении #291366 писал(а):

А формула-то у нас одна и та же!

Я вам повторяю - формулы существенно разные, с существенно разной эффективностью. То, что они решают одну и ту же задачу по похожему принципу, не делает их одинаковыми.

-- Mon Feb 22, 2010 15:19:08 --

Nataly-Mak в сообщении #291366 писал(а):

В формуле, которая приведена в моей статье, переменные пронумерованы в произвольном порядке (учтён только порядок вычисления тех зависимых переменных, которые зависят не только от свободных переменных, но и от зависимых тоже). При программной реализации нумерация может быть совсем другой. Разве это непонятно?

Если хотите, чтобы я проанализировал вашу формулу, приведите нумерацию в соответствие с программной реализацией.

[Nataly-Mak]

maxal
вы чего сейчас доказываете-то?

Разве я вам не сказала, что в программе у меня совсем другой порядок, чем нумерация в формуле, приведённой в статье?

Может быть, вы для начала посмотрите всё-таки мою программную реализацию? А потом уже будете копья ломать, даказывая, что ваша формула намного эффективнее.

Я вот сейчас спать очень хочу (у нас 23.19 по Москве). Завтра я вам выложу мою программную реализацию и мою формулу.

Хотя, впрочем, зачем?
По-моему, и так всё предельно ясно.
А программа уже выложена. Кому интересно, пусть посмотрят.

[maxal]

Nataly-Mak в сообщении #291379 писал(а):

Разве я вам не сказала, что в программе у меня совсем другой порядок, чем нумерация в формуле, приведённой в статье?

Я начал писать свое сообщение, когда вашего с этой информацией еще не было.

Nataly-Mak в сообщении #291379 писал(а):

Может быть, вы для начала посмотрите всё-таки мою программную реализацию?

У меня нет времени разбирать вашу программу. Опишите её алгоритм здесь (хотя так, как сделал я выше).

-- Mon Feb 22, 2010 15:27:47 --

Nataly-Mak в сообщении #291379 писал(а):

вы чего сейчас доказываете-то?

Я не доказываю, а рассказываю заинтересованным лицам, как именно в данной задаче оценивается эффективность перебора.

[12d3]

Nataly-Mak в сообщении #291321 писал(а):

Пожалуйста, укажите эти количества

Это все, которые есть. То бишь по одному на каждую константу.

[maxal]

svb в сообщении #289039 писал(а):

Понятно, что это можно организовать разными способами. У Наталии последовательно вычисляются элементы квадрата с индексами x1,x2,x3,x4,x5,x6, а далее элементы 21,22,23,24,25 (это не числа, а обозначения элементов квадрата). Насколько оптимально это сделано у Наталии? Вопрос, вообще говоря, открыт.

Закроем этот вопрос.

Вот самая эффективная формула этого класса для квадратов $5\times 5$. Квадрат представляется в виде:

$$\begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ x_{20} & x_6 & x_{18} & x_{10} & x_{21} \\ x_{22} & x_7 & x_{11} & x_{15} & x_{23} \\ x_{24} & x_8 & x_{19} & x_{13} & x_{25} \\ x_{12} & x_9 & x_{16} & x_{17} & x_{14} \end{bmatrix} $$

где $x_1$, $x_2$, $x_3$, $x_4$, $x_6$, $x_7$, $x_8$, $x_{10}$, $x_{11}$, $x_{13}$, $x_{15}$, $x_{18}$, $x_{20}$, $x_{22}$ - независимые переменные, остальные зависимые:

$$\begin{cases} x_5 = S - x_1 - x_2 - x_3 - x_4\\ x_9 = S - x_2 - x_6 - x_7 - x_8\\ x_{12} = S - x_5 - x_8 - x_{10} - x_{11}\\ x_{14} = S - x_1 - x_6 - x_{11} - x_{13}\\ x_{16} = -x_3 - 2x_5 + 2x_6 + x_7 - 2x_{12} + 2x_{13} + x_{15}\\ x_{17} = S - x_4 - x_{10} - x_{13} - x_{15}\\ x_{19} = S - x_3 - x_{11} - x_{16} - x_{18}\\ x_{21} = S - x_6 - x_{10} - x_{18} - x_{20}\\ x_{23} = S - x_7 - x_{11} - x_{15} - x_{22}\\ x_{24} = S - x_1 - x_{12} - x_{20} - x_{22}\\ x_{25} = S - x_5 - x_{14} - x_{21} - x_{23} \end{cases}$$

В остальном алгоритм такой же, как описанный тут: post291286.html#p291286
Дальнейшие оптимизации возможны, например, за счёт учета нуля (поворотами и выворачиваниями квадрата можно добиться, что нулевой элемент будет одним из $x_1, x_2, x_3$ или $x_{11}$) и симметрий.

P. S. Было бы интересно, если кто-нибудь сравнил практическое время расчёта по различным формулам.

[svb]

maxal в сообщении #291405 писал(а):

Вот самая эффективная формула этого класса для квадратов $5\times 5$. Квадрат представляется в виде:

$$\begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ x_{20} & x_6 & x_{18} & x_{10} & x_{21} \\ x_{22} & x_7 & x_{11} & x_{15} & x_{23} \\ x_{24} & x_8 & x_{19} & x_{13} & x_{25} \\ x_{12} & x_9 & x_{16} & x_{17} & x_{14} \end{bmatrix} $$

где $x_1$, $x_2$, $x_3$, $x_4$, $x_6$, $x_7$, $x_8$, $x_{10}$, $x_{11}$, $x_{13}$, $x_{15}$, $x_{18}$, $x_{20}$, $x_{22}$ - независимые переменные, остальные зависимые:

$$\begin{cases} x_5 = S - x_1 - x_2 - x_3 - x_4\\ x_9 = S - x_2 - x_6 - x_7 - x_8\\ x_{12} = S - x_5 - x_8 - x_{10} - x_{11}\\ x_{14} = S - x_1 - x_6 - x_{11} - x_{13}\\ x_{16} = -x_3 - 2x_5 + 2x_6 + x_7 - 2x_{12} + 2x_{13} + x_{15}\\ x_{17} = S - x_4 - x_{10} - x_{13} - x_{15}\\ x_{19} = S - x_3 - x_{11} - x_{16} - x_{18}\\ x_{21} = S - x_6 - x_{10} - x_{18} - x_{20}\\ x_{23} = S - x_7 - x_{11} - x_{15} - x_{22}\\ x_{24} = S - x_1 - x_{12} - x_{20} - x_{22}\\ x_{25} = S - x_5 - x_{14} - x_{21} - x_{23} \end{cases}$$

В остальном алгоритм такой же, как описанный тут: post291286.html#p291286
Дальнейшие оптимизации возможны, например, за счёт учета нуля (поворотами и выворачиваниями квадрата можно добиться, что нулевой элемент будет одним из $x_1, x_2, x_3$ или $x_{11}$) и симметрий.

P. S. Было бы интересно, если кто-нибудь сравнил практическое время расчёта по различным формулам.

Из комментария в тексте программы

   i  k  x1 l  j
   r  x3 x4 n  s
   x6 y2 x2 y1 x5
   u  o  y4 q  t
   m  y3 y5 v  p

i j k l x1 m n o x2 p q x3 r s x4 t x5 u x6 v y1 y2 y3 y4 y5 }

xi и yi - вычисляемые

Для тестирования я попробовал один набор из смитов, из которого получался 1 квадрат.
Время 214.12 s
Мне нужно было убедиться, что если не отсекать изоморфные квадраты, то программа выдаст 32 квадрата. После небольшой коррекции запустил программу.
Время 10443.84 s

Понятно, что отсекать нужно, но когда? Например, почему я поставил вторую переменную j в угол.
Выбранные мной условия неизоморфности такие i<(j,p,m,n,q,o,x3), k<(l,u,r) - естественно, что при таких условиях циклы идут j:i+1..25 .. l:k+1..25 и т.п.
Наибольшие потери времени идут при выборе очередного свободного индекса, например для l мало начинать с k+1, необходимо проверить не совпадает ли он с ранее выбранными. Для этого достаточно было ввести специальный массив меток - у меня 0 - свободно, 1 - занято. Писать длинные условия, как сделано у Наталии, не очень хотелось, плюс хотелось универсальности и сокращения проверок. Для вычисляемых значений необходимо найти индекс - вот здесь наибольшие потери. Линейный поиск я заменил на нормальный, делением пополам. Но для этого нужен отсортированный массив, что я и сделал на входе быстрой сортировкой.

Теперь простенький пример. Пусть имеются 3 индекса перебора i, j, k , которые могут принимать значения 1..16. Причем i и k независимы друг от друга, а для i и j существует соотношение i<j.
И все индексы должны быть разными.
Как правильно организовать циклы:
i, j, k или
i, k, j ?
По большому счету эти варианты эквиваленты, но возможен и более детальный анализ, на который, кстати, влияют емкости дальнейшего перебора для разных сочетаний индексов. Практика использования программы показала, насколько чувствительно время полного перебора к исходному набору. Задержки могут быть в начале, как в последнем примере с простыми числами, бывает и наоборот, хотя, конечно к концу скорость возрастает. Неравномерность бросается в глаза, когда смотришь на изменение индексов.

[maxal]

maxal в сообщении #291405 писал(а):

где $x_1$, $x_2$, $x_3$, $x_4$, $x_6$, $x_7$, $x_8$, $x_{10}$, $x_{11}$, $x_{13}$, $x_{15}$, $x_{18}$, $x_{20}$, $x_{22}$, остальные зависимые

svb в сообщении #291419 писал(а):

i j k l x1 m n o x2 p q x3 r s x4 t x5 u x6 v y1 y2 y3 y4 y5 }

xi и yi - вычисляемые

Вплоть до 13-го элемента (по порядку вычисления) эффективность та же, но дальше у меня следует зависимый (вычисляемый) элемент $x_{14}$, а у вас независимый s. Соответственно, начиная с этого места, мои формулы будут работать более эффективно.

-- Mon Feb 22, 2010 20:59:06 --

svb в сообщении #291419 писал(а):

Выбранные мной условия неизоморфности

Сформулируйте, какие именно квадраты, вы считаете изоморфными.

Кстати, в любом случае полезно потребовать наличия нулевого элемента, причем, как я уже указывал ранее, поворотами и выворотами квадрата его можно привести на одну из позиций $x_1, x_2, x_3$ или $x_{11}$ (в моей нумерации). А для такого квадрата (кроме, разве что, последнего случая) количество изоморфных квадратов резко сокращается.

Я попробую на досуге также получить самые эффективные формулы для каждого из случаев $x_1=0$, $x_2=0$, $x_3=0$ и $x_{11}=0$ - вполне возможно, что тут еще что-то можно будет выиграть в производительности.

[Nataly-Mak]

maxal
Вернёмся немного назад
Когда я спросила вас, как у вас дела с проверкой смитов на предмет построения магического квадрата 4х4 из последовательнох смитов, вы ответили, что проверили смиты до 10^{12} и с помощью различных эвристик нашли в этом интервале всего 28 потенциальных массивов (то есть наборов по 16 последовательных смитов), из которых может быть составлен магический квадрат. Но "окончательный диагноз" вы ещё не поставили, потому что не нашли достаточно эффективную процедуру проверки найденных массив на предмет построения магического квадрата.

Далее я предложила вам свою процедуру проверки и проверила выложенные вами потенциальные массивы всего за 2 минуты. И как ни крути, моя процедура проверки основана на той самой формуле 7+9.

В ответ на это вы написали:

Цитата:

Но выборка 7 значение параметров из 16 - это 16*15*14*13*12*11*10 вариантов. Вероятно, их можно уменьшить в десяток раз с учётом поворотов/симметрий квадрата, но все равно остается более вариантов. Вы уверены, что вы учитываете все варианты и что ваша программа гарантированно найдёт магический квадрат, если он существует?

Так? Этот этап вы помните?
То есть вы сомневались в правильной работе этой самой формулы 7+9.

Теперь вы "открыли" эту же самую формулу и утверждаете, что это самый эффективный алгоритм и самая оптимальная формула.

Интересно, не правда ли?

Для меня, например, построение магических квадратов 4-го порядка давно пройденный этап. И если бы последовательные числа Смита, из которых составится магический квадрат, не были астрономическими, я давно нашла бы этот квадрат (или его нашёл бы, например, tolstopuz, который давным-давно проверил смиты до миллиарда на предмет построения магического квадрата 4-го порядка из последовательных смитов).

Далее, для меня пройденный этап и построение магических квадратов 5-го порядка. Я давно написала свою статью "Общие формулы магических квадратов", в которой представлены общие формулы и схемы для построения магических квадратов порядков 4 - 7 (статья в 3-х частях).
На основании моей формулы для квадратов 5х5 svb сделал превосходную программу для построения таких квадратов (можно сколько угодно её оптимизировать, но суть алгоритма от этого не изменится!)

Я не писала в своей статье и здесь не утверждаю, что моя программная реализация формул 7+9 и 14+11 для квадратов 4-го и 5-го порядков соответственно является самой оптимальной. Более того, я вполне согласна с анализом моей программы, который дал svb. Заметьте: он делал анализ именно программной реализации, а не самой формулы. Потому что он хорошо понимает, что программную реализацию одной и той же формулы можно выполнить по-разному.
Я здесь задавала вопрос: реально ли выполнение программы, составленной по формуле 14+11? Мне никто не ответил, пока не пришёл svb и не показал готовой программой, что это вполне реально.

А вы сейчас пришли и заявили: "закроем этот вопрос. Вот самая эффективная формула для квадратов 5-го порядка". И, наверное, демонстрируете ту же самую формулу 14+11 (даже не стала смотреть вашу формулу; ещё раз повторю - для меня это давно пройденный этап и потому мне это совсем неинтересно).

А вот мне кажется, что самая эффективная формула для квадратов 5х5 у 12d3. Потому что он уже получил наименьший магический квадрат из последовательных смитов А это является доказательством того, что его алгоритм самый лучший.
Более того, он уже давно реализовал свой алгоритм для квадратов порядка 6, и по его программе я построила квадраты данного порядка и из последовательных, и из произвольных смитов.
Может быть, вы и этот результат перечеркнёте и представите нам самую эффективную формулу для построения квадратов 6-го порядка? Интересно было бы посмотреть!
А ещё интереснее, если вы представите самую эффективную формулу для построения квадрата 7-го порядка. Вот это мне действительно очень интересно, потому что квадрат 7-го порядка ещё не найден ни из последовательных, ни из произвольных смитов.

И вряд ли здесь будет работать аналогичная формула, основанная на переборе $m$ свободных переменных и (n^2 - m) зависимых переменных.
Потому что даже при всех возможных оптимизациях здесь количество вариантов перебора будет действительно огромным, и выполнить такую программу за реальное время вряд ли получится.

Далее, замечу, что и для 4-5 и для 6-9 порядков есть ещё не один алгоритм, кроме предложенного вами. Об одном из таких алгоритмов я уже сказала - это алгоритм 12d3.
У меня есть ещё два алгоритма (кроме вашей самой эффективной формулы).
Один из них я разработала ещё 17 лет назад и применила не так давно для построения магических квадратов из простых чисел. Если вы помните, первым таким квадратом у меня был квадрат 6-го порядка. Далее по этому же алгоритму я построила магические квадраты порядков 7 - 15. Это всё было до того, как пришёл ice00 и представил свои программы. Насколько я понимаю, у него такой же алгоритм, как и в моих программах. Можно назвать этот алгоритм вероятностным. Он основан на случайной генерации набора из $n$ строк. Этот алгоритм прекрасно работает для построения квадратов из простых чисел и для квадратов из смитов больших порядков (начиная с порядка 11). А вот для квадратов из смитов порядков 4 - 10 этот алгоритм не работает по той простой причине, что вероятность построения такого квадрата из заданного массива смитов очень мала.

Наконец, я предложила третий алгоритм (когда ещё не были найдены квадраты 6-го порядка). Этот алгоритм очень подробно изложен здесь конкретно для порядка 6. Но понятно, что его можно применить для всех порядков 4 - 9.
Я здесь просила всех дать оценку эффективности этого алгоритма и возможности его реализации. Вы почему-то скромно промолчали (как главный специалист по самым эффективным алгоритмам). Высказался только ice00 и ещё одн товарищ. ice00 сказал, что этот алгоритм можно реализовать не только для порядка 6, но и для порядков 7 - 9, и взялся это сделать. Однако задачу не осилил

Не знаю, как для порядков 8-9, а для порядка 7, как мне кажется, алгоритм вполне можно реализовать. И уж тем более для порядков 4 - 6!
И как знать, может быть, этот алгоритм будет намного эффективнее вашей "самой эффективной формулы".

Теперь вы, надеюсь, поняли, что построение нетрадиционных магических квадратов порядков 7 - 9 отнюдь не является "глупой и пустой головоломкой"? (как вы изволили мне заметить на мою просьбу предложить эту непростую задачу студентам, изучающим программирование).

Резюме:

1. лучшим доказательством вашей "самой эффективной формулы" будет готовый наименьший магический квадрат 4-го порядка из последовательных смитов;
2. с самой эффективной формулой для квадратов порядка 5 вы немножко опоздали: квадрат уже найден 12d3 (причём он нашёл оба квадрата: и из произвольных, и из последовательных смитов);
3. будет очень интересно посмотреть, какую самую эффективную формулу вы предложите для квадрата порядка 7.

[maxal]

Nataly-Mak в сообщении #291426 писал(а):

Так? Этот этап вы помните?
То есть вы сомневались в правильной работе этой самой формулы 7+9.

Не всякая формула типа "7+9" является корректной. Я сомневался именно в корректности вашей конкретной формулы и ее реализации, а не в том, что такая формула существует.

Nataly-Mak в сообщении #291426 писал(а):

Теперь вы "открыли" эту же самую формулу и утверждаете, что это самый эффективный алгоритм и самая оптимальная формула.

Повторяю вам в третий раз: это не та же самая формула. Да, это формула типа "7+9", но она отличная от вашей, и гарантированно является самой эффективной из всех формул такого типа. Про эффективность - см. post291373.html#p291373

Nataly-Mak в сообщении #291426 писал(а):

На основании моей формулы для квадратов 5х5 svb сделал превосходную программу для построения таких квадратов.

Я показал выше, что эту "превосходную программу" можно сделать еще превосходнее, если использовать в ней другую формулу.

Nataly-Mak в сообщении #291426 писал(а):

А вот мне кажется, что самая эффективная формула для квадратов 5х5 у 12d3. Потому что он уже получил наименьший магический квадрат из последовательных смитов! А это является доказательством того, что его алгоритм самый лучший.

Не говорите ерунды. Никакой вычислительный результат не является доказательством оптимальности алгоритма. Вам бы учебники почитать о том, что такое сложность алгоритма, и как она оценивается.

[Nataly-Mak]

Вы не ответили на самый главный вопрос: самая эффективная формула для построения магического квадрата 7-го порядка из смитов у вас есть?

А учебники я немного читала 40 лет назад (кстати, имею красный диплом об окончании мех-мата СГУ). Правда, многое уже забыла. Однако это не мешает мне разрабатывать различные алгоритмы, реализовывать их и получать по программам оригинальные магические квадраты (см. A164843, A073502, A073520, A170928).

Оценить сложность моего нового алгоритма для построения квадратов порядков 6 - 7 из смитов я просила вас (не только здесь, на форуме, но и в ЛС), но вы этого почему-то не сделали. Видимо, ещё не смогли оценить

-- Вт фев 23, 2010 08:37:02 --

12d3
Ого! Вот какие оригинальные квадратики - все в единственном экземпляре. Это великолепные результаты. Спасибо!

Обязательно отправлю в OEIS заявку на эту последовательность (вы бы мне свои фамилию и имя написали по-английски, хотя бы в ЛС ).