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

[maxal]

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

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

Нет, квадратами 7x7 пока не занимался.

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

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

Во-первых, см. выше. Во-вторых, не хамите.

[Nataly-Mak]

Цитата:

Во-вторых, не хамите.

maxal
Попрошу вас выбирать выражения на форуме.
В моих сообщениях нет и намёка на хамство. И вашу фразу я воспринимаю, как оскорбление.

[maxal]

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

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

Проверил. Чуть более эффективная формула существует только в случае $x_{11}=0$ (за счёт того, что $x_{11}$ обрабатывается далеко не первым в общей формуле).

[svb]

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

i j k x1 l x2 m x3 n x3 x4 x5 x6 o x7 x8 x9

у меня была использована:

i j k x1 l m  x2 n x3 x4 x5 x6 o x7 x8 x9

Разница в объемах:12902400 и 14192640.
Теперь пару слов о смысле его формулы. Она сводится к следующему принципу: "не вводи новых независимых переменных, пока имеется такая возможность" - понятно, что и Наталия и я стремились к этому чисто интуитивно.

-- Вт фев 23, 2010 17:57:26 --

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

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

Повороты и обмены строк/столбцов 1-2,4-5 позволяют минимальный элемент среди следующих

X * * * X
* X * X *
* * * * *
* X * X *
X * * * X

перевести в левый верхний угол. Далее, симметрия относительно диагонали, проходящей через левый верхний угол, и обмены строк/столбцов 2-4 позволяют минимальный элемент среди следующих

* X * X *
X * * * *
* * * * *
X * * * *
* * * * *

поставить в верхнюю строку на вторую позицию.

[maxal]

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

Повороты и обмены строк/столбцов 1-2,4-5 позволяют минимальный элемент среди следующих

X * * * X
* X * X *
* * * * *
* X * X *
X * * * X

перевести в левый верхний угол. Далее, симметрия относительно диагонали, проходящей через левый верхний угол, и обмены строк/столбцов 2-4 позволяют минимальный элемент среди следующих

* X * X *
X * * * *
* * * * *
X * * * *
* * * * *

поставить в верхнюю строку на вторую позицию.

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

Но в любом случае выгодно также рассматривать отдельно следующие 4 случая, соответствующие положению нуля:

0 * * * *   * 0 * * *   * * 0 * *   * * * * *
* * * * *   * * * * *   * * * * *   * * * * *
* * * * *   * * * * *   * * * * *   * * 0 * *
* * * * *   * * * * *   * * * * *   * * * * *
* * * * *   * * * * *   * * * * *   * * * * *

В первом случае дополнительно возможны транспозиция и перестановка строк/столбцов 2,4.
В втором случае - одновременное отражение относительно вертикальной оси и перестановка перестановка строк/столбцов 2,4, а также одновременное отражение относительно горизонтальной оси и перестановка перестановка строк/столбцов 1,5.
В третьем случае - отражение относительно вертикальной оси и перестановка строк/столбцов 2,4.
В четвертом - повороты, отражения и перестановка строк/столбцов 2,4 и 1,5.
Эти преобразования не изменяют положения нуля, но позволяют избавится от дальнейшей симметрии.

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

[svb]

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

Вычислил самую эффективную формулу для случая, когда нам дано ровно 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}$,

Так как моя программа легко переделывается под любые схемы расчета, то попробовал ее модифицировать под эту схему.
Время получения всех 880 квадратов:
- исходная программа - 1.59 сек
- модифицированная программа - 1.53 сек
К сожалению, надежность этих цифр невысока при работе по виндовозом (для исходной программы часто выпадала цифра 1.53).
При запуске из того же FAR при нераспахнутом окне (после нажатия alt+enter) данные следующие:
- исходная программа - 0.05 сек
- модифицированная программа - 0.00 сек

-- Вт фев 23, 2010 20:46:02 --

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

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

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

   i  j  k  x1
   o  m  n  x7
   x8 x4 x3 x9
   l  x5 x6 x2

i j k x1 l x2 m x3 n x4 x5 x6 o x7 x8 x9

а дальше идет цикл по l, которая должна быть больше этого элемента. Ничего страшного, поставил l=x1+1,..,16. Могут быть и плюсы.

Цитата:

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

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

[svb]

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

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

Схема расчета, которая использовалась в программе mag5x5

   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 }

Схема расчета после модификации программы mag5x5

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

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

Испытывались два набора смитов, из первого набора генерировался 1 квадрат, из второго 2.
Времена работы для первого набора:
213.73 сек
97.08 сек k=2.20
Времена работы для второго набора:
298.90 сек
120.87 сек k=2.47

[maxal]

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

Испытывались два набора смитов, из первого набора генерировался 1 квадрат, из второго 2.
Времена работы для первого набора:
213.73 сек
97.08 сек k=2.20
Времена работы для второго набора:
298.90 сек
120.87 сек k=2.47

Теоретическая оценка эффективности этих схем дает отношение ~ 2.7, что довольно хорошо согласуется с отношениями времени расчёта для этих двух примеров.

[Nataly-Mak]

Найден магический квадрат 7-го порядка из последовательных смитов с магической константой 5551:

778  861  319 1284  517 1086  706
588  636  648  913  985 1219  562
355  526  922  645  627  895 1581
729  728  576  654 1376  825  663
483 1282  382  915 1165  634  690
1507  852 1255  762  346  438  391
1111  666 1449  378  535  454  958

Квадрат построен из следующих последовательных смитов:
319, 346, ..., 1507, 1581.

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

[Nataly-Mak]

И сразу же получен магический квадрат 7-го порядка из произвольных смитов:

825   94  729  690  438  382  562
778   85  654  202  913  634  454
378  958  663  861   22  483  355
517  922    4  346  391  645  895
58  274  728  666  526  762  706
588  852   27  319 1165  648  121
576  535  915  636  265  166  627

Магическая константа квадрата равна 3720.

Точно так же нет гарантии, что это наименьший квадрат. Теоретическая минимальная константа для квадрата порядка 7 равна 3719. Но для такой константы у меня никак не формируется даже набор из 7 строк, от которого начинается весь мой алгоритм.
Поскольку мой алгоритм не реализован полностью и не даёт полной гарантии, что из данного массива квадрат не строится, нельзя утверждать, что квадрат с магической константой 3719 не существует.

[Nataly-Mak]

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

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

Теперь новый алгоритм на примере квадратов 5-го порядка (проще рассказывать).
Берём массив cмитов, из которого 12d3 построил наименьший магический квадрат:

4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 382, 391, 454, 517, 526, 535, 576, 648, 706, 729

Генерируем все оригинальные наборы по 5 чисел, сумма которых равна магической константе квадрата 1636. Этот этап выполняется очень быстро (особенно для квадратов из смитов). В данном примере сгенерировано 216 оригинальных наборов (напомню: оригинальным набором я называю такой набор, в котором числа следуют в порядке возрастания).

Теперь из всех наборов надо выбрать все пары наборов, имеющих один общий элемент. Это будут две диагонали будущего квадрата.
Например, выбираем два таких оригинальных набора (я сделал это просто по известному квадрату, а вообще, конечно, надо написать программу выбора всех пар оригинальных наборов):

85, 121, 346, 355, 729
94, 166, 346, 382, 648

Размещаем эти наборы на месте диагоналей будущего квадрата:

85 X X X 94
X 121 X 166 X
X X 346 X X
X 382 X 355 X
648 X X X 729

Заготовка готова. Но из неё надо получить все варианты. Для этого надо переставить все числа в обеих диагоналях, за исключением центрального элемента, этот элемент остаётся всегда на своём месте. Вариантов заготовки получается 24*24=576. Это небольшое количество вариантов.

И, наконец, на последнем этапе каждый из 576 вариантов заготовки проверяется на возможность достраивания до магического квадрата. Достраивание выполняется практически мгновенно (даже на Бейсике). Здесь для оставшихся 16 свободных чисел работает формула 7+9 (7 независимых переменных и 9 зависимых переменных).
Я написала программу, которая по двум введённым диагоналям делает все варианты и достраивает их. При этом не делала никаких отсечений, программа выдаёт все квадраты. Для данного примера программа выдала 16 квадратов (работала несколько минут). Это значит, что оригинальных квадратов будет 4 (я не считаю эквивалентными квадраты, получающиеся друг из друга М-преобразованиями).
Один квадрат был выложен здесь его автором 12d3.
Второй квадрат я получила по программе, представленной svb (в программе реализована общая формула 14+11). Вот этот квадрат:

85 58 391 454 648
274 729 517 94 22
535 202 346 27 526
576 382 4 355 319
166 265 378 706 121

Кстати, программа svb выдаёт только один этот квадрат, то есть в этой программе три остальные квадрата, получаемые из данного М-преобразованиями, считаются эквивалентными и отбрасываются.
Так же, видимо, считал и 12d3.

Среди 16 квадратов, полученных по моей программе, есть ещё два (кроме двух указанных), входящие в группу эквивалентности относительно М-преобразований. Остальные 12 квадратов эквивалентны этим четырём квадратам относительно основных преобразований.

Теперь применительно к квадратам 7-го порядка. Сначала тоже генерируем из чисел данного массива все оригинальные наборы по 7 чисел.
Для массива из последовательных смитов 319, 346, …, 1507, 1581 генерируется 50417 оригинальных наборов
(программу генерации оригинальных наборов прислал мне svb).
Я проверила по этой программе 20 потенциальных массивов. Для данного массива количество оригинальных наборов самое большое.

Из всех оригинальных наборов надо теперь выбрать четыре набора, такие, что у них один общий элемент. Понятно, что надо выбрать все такие четвёрки наборов.
Эти 4 набора размещаем в будущем квадрате так: центральная строка, центральный столбец, две диагонали. Оригинальная заготовка готова.

Я сгенерировала заготовку случайным образом. Было сделано всего две попытки, и вторая попытка увенчалась успехом (элемент везения!). Вот сгенерированная мной заготовка:

778   X   X  1284   X  X   706
X   636   X   913   X  1219   X
X   X   922   645   627   X  X
729  728  576  654 1376  825  663
X  X   382   915  1165   X   X
X   852  X   762   X   438   X
1111   X  X   378   X   X   958

У нас осталось 24 свободных числа. Достраивание происходит очень быстро. Работает формула 13+11 (13 независимых переменных и 11 зависимых).

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

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

Точно так же я построила и магический квадрат 7-го порядка из произвольных смитов (причём с первой попытки). Ну, надо же, наконец, быть удаче после 5 месяцев напряжённой работы.

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

[Nataly-Mak]

Почта принесла письмо от ice00, в котором ещё один результат - наименьший магический квадрат 9-го порядка из произвольных смитов.

483 27 645 1255 1908 2067 355 1219 778 
94 346 636 762 861 1284 1376 1642 1736 
985 454 202 1282 576 728 1962 1921 627 
1633 1881 666 1449 852 382 588 895 391 
958 1626 1755 690 1894 825 319 22 648 
517 1842 166 634 922 1952 1776 663 265 
1858 1822 1086 378 438 915 4 729 1507 
1935 85 1903 1581 1165 58 562 535 913 
274 654 1678 706 121 526 1795 1111 1872

YUPPY!!!!!!!!!!!!!!!!!
ORDER=9 MAGIC=8737

Квадрат получен тем же способом, каким были получены квадраты 10-го порядка, но немного улучшенным. Улучшение состояло в том, что я попросила ice00 сделать в его программе обработки полумагических квадратов перестановку всех строк с одновременной перестановкой всех столбцов.

У меня есть программа, присланная ice00, в которой заложена только перестановка всех строк. Для квадратов порядка 10 этого оказалось достаточно, а для квадратов порядков 7 - 9 нет.

Вчера я отправила ice00 2096 полумагических квадратов порядка 9, найденных по моей программе, и попросила его проверить их указанным методом (перестановки строк и столбцов). Только перестановкой строк я их сама проверила, магический квадрат не был получен.
И вот результат!
Получено 12 магических квадратов, но при беглом просмотре я увидела среди них только два оригинальных.

Теперь попробуем таким же способом получить магический квадрат 9-го порядка из последовательных смитов.
А затем займёмся квадратами порядка 8.

Наше сотрудничество с ice00 даёт результаты.

[Nataly-Mak]

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

58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111, 1165

Это самый первый потенциальный массив. Он даёт магическую константу 4167. Вот какая получилась заготовка:

355  X  X  627  X  X  778
X  636  X  346  X  535  X
X  X  690  645  274  X  X
762 654 985 391 121 526 728
X  X  588  634  915  X  X
X  895  X  438  X  517  X
706  X  X  1086  X  X  663

Вела заготовку в программу достраивания. Увы! Чуда не произошло, квадрат не достроился до магического.

Но это, конечно, ещё абсолютно ничего не значит.
Кстати, из данного массива генерируется 41294 оригинальных наборов по 7 чисел.

Впрочем, мы имеем ещё один в некотором роде вероятностный алгоритм:
1 этап: случайная генерация заготовки;
2 этап: достраивание заготовки до квадрата.

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

Вот почему особую ценность представляют те алгоритмы, которые дают возможность полной проверки и получения однозначного ответа.
Такие программы уже есть для магических квадратов порядков 3 - 6. А вот для квадратов порядка 7 мне такая программа пока неизвестна.

Только такая программа позволит решить вопрос с пропущенными потенциальными массивами. Ну, или вдруг так же сильно повезёт, и квадраты из этих массивов построятся одним из вероятностных алгоритмов.

Есть ещё путь: построить много полумагических квадратов и обработать их по программе перестановки строк и столбцов. Но загвоздка в том, что из этих массивов у меня не строятся полумагические квадраты. Даже наборы из 7 строк никак не генерируются. Вот почему я с самого начала отвергла эти массивы.
У меня большое подозрение, что из этих массивов магических квадратов вообще не существует. Но... это ещё надо доказать.

[Nataly-Mak]

В OEIS появилась новая последовательность A173981

Это последовательность из магических констант магических квадратов 4-го порядка из последовательных простых чисел.
В последовательность включены мои квадраты (первые пять квадратов; первый из них – наименьший - уже давно известен) и квадраты, выложенные здесь 12d3.

Сейчас я готовлю аналогичную последовательность для квадратов 5-го порядка.
Собственно, она у меня уже давно готова, но вот статью в OEIS пока не написала.

Тут хочу отметить, что теперь имею возможность строить магические квадраты 5-го порядка по своей программе (которая приведена в статье “Общие формулы магических квадратов” и была переведена svb на Паскаль).

svb прислал мне компилируемый Бейсик. Работает примерно раз в 20 быстрее моего QBASICа (интерпретируемого).

Сегодня, наконец, немного отвлеклась от квадратов из смитов и опробовала свою программу для квадратов 5-го порядка на компилируемом Бейсике. В программе сделан выход на конец сразу после первого найденного магического квадрата.
Ввела в программу первый массив из последовательных простых чисел, из которого составляется магический квадрат 5-го порядка:

 13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113

Программа работала 2 минуты и квадрат построен! Вот он:

13  17  61  113  109 
107  59  97  19  31 
103  53  79  37  41 
67  83  47  73  43 
23  101  29  71  89

Замечательный результат! Наконец-то я хоть немного повысила производительность построения квадратов по своим программам.
Теперь можно снять условие “до первого квадрата” и построить ВСЕ магические квадраты из данного массива чисел.

О преимуществе данного алгоритма перед вероятностным алгоритмом я уже говорила.

svb, спасибо вам большое за реальную помощь!

Кстати, полумагические квадраты 9-го порядка я тоже строю сейчас в новом Бейсике. Вчера настроила 1197 полумагических квадратов с константой 9179 и сейчас отправила их ice00 для проверки. Полумагические квадраты с константой 9179 строятся хуже, чем с константой 8737. Поэтому вероятность получения магического квадрата с данной константой меньше, чем с константой 8737. Возможно, из первой порции полумагических квадратов магический квадрат не будет найден и придётся строить ещё много-много полумагических квадратов, чтобы найти среди них единственную жемчужину.

И пока ничего не придумано для построения магических квадратов 8-го порядка из смитов.

К сожалению, путь построения полумагических квадратов с последующей перестановкой в них строк и столбцов для квадратов 8-го порядка не будет работать, по той причине, что полумагические квадраты строятся очень плохо. Но всё равно надо пробовать и этот путь (для каждого нового полумагического квадрата).
Я уже для двух полумагических квадратов попробовала.
Но программа, присланная мне ice00, делает только перестановку строк. Тогда я прежде делаю по своей программе перестановку столбцов, получаю 40320 полумагических квадратов. Ввожу их все в программу ice00 и жду результат. Программа работает 2,5 часа (вариантов огромное количество: 40320*40320).
Из двух проверенных полумагических квадратов магический квадрат не получен.
По-хорошему эту программу надо оптимизировать, о чём я уже попросила ice00.

[Nataly-Mak]

Есть!!

ice00 прислал результаты проверки. Жемчужина найдена. Из 1197 полумагических квадратов получен всего один магический квадрат 9-го порядка с магической константой 9179:

648 27 1581 454 1678 1872 355 526 2038 
94 1736 378 778 1966 1952 922 690 663 
1086 861 1633 1626 728 729 636 1822 58 
1219 1842 913 762 627 825 1449 1376 166 
576 1282 1908 634 645 274 1962 391 1507 
895 346 1881 2067 202 588 1903 915 382 
985 1795 85 1255 958 562 121 1642 1776 
1921 438 265 1284 1858 483 1165 1111 654 
1755 852 535 319 517 1894 666 706 1935

Это наименьший квадрат из последовательных смитов.

ice00, спасибо! Ура! Мы его нашли

Итак, остались квадраты 8-го порядка в обеих группах. Думаю, что вместе с ice00 мы их найдём.

Кроме того, не найден ещё квадрат 4-го порядка из последовательных смитов (если я не пропустила этот удивительный момент ).

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