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

[Nataly-Mak]

Всё нашла! Фактически моя программа выдаёт точно 3 различных квадрата.
Ещё раз 12 поделить на 2 и ещё раз поделить на 2.

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

1 8 13 12
14 11 2 7
4 5 16 9
15 10 3 6

стандартная перестановка строк даёт такой изоморфный квадрат:

1 8 13 12
15 10 3 6
4 5 16 9
14 11 2 7

Итак, там, где у меня 24 варианта, на самом деле только 3 различных квадрата. Всё правильно

[Pavlovsky]

Моя проверка выдает на самом деле 12 вариантов квадрата. Наименьшее число x1 находится на позиции №1. Второе по наименьшести x2 выше диагонали выходящей из левого верхнего угла. Путем зеркального отражения относительно этой диагонали, можно получить еще 12. Итого 24 разных МК с фиксированным наименьшим элементом x1 на позиции №1.

[maxal]

Pavlovsky в сообщении #312398 писал(а):

Про МК 5х5. Чего то больше неохота ручками выводить общую формулу.

См. post291405.html#p291405

Pavlovsky в сообщении #312398 писал(а):

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

У меня есть программка на PARI/GP, которая находит эффективные формулы магических квадратов. В текущем виде я ее публиковать (и документировать) не решусь, но если интересует такая формула для какого-то конкретного квадрата вплоть до 5-го порядка - могу вычислить. Для квадратов больших порядков текущий алгоритм слишком долго думает, а до дальнейшей оптимизации руки пока никак не дойдут. Впрочем, если ограничений много (например, для как для пандиагональных и/или ассоциативных квадратов), то возможно, что и 6-й порядок потянет.

[Nataly-Mak]

Pavlovsky в сообщении #312453 писал(а):

Моя проверка выдает на самом деле 12 вариантов квадрата. Наименьшее число x1 находится на позиции №1. Второе по наименьшести x2 выше диагонали выходящей из левого верхнего угла. Путем зеркального отражения относительно этой диагонали, можно получить еще 12. Итого 24 разных МК с фиксированным наименьшим элементом x1 на позиции №1.

А на самом деле должно быть только 3 квадрата (различных)
Остальные изоморфны.

-- Пт апр 23, 2010 18:19:59 --

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

У меня есть программка на PARI/GP, которая находит эффективные формулы магических квадратов. В текущем виде я ее публиковать (и документировать) не решусь, но если интересует такая формула для какого-то конкретного квадрата вплоть до 5-го порядка - могу вычислить.

Меня в данный момент интересует программа построения пандиагонального квадрата 5-го порядка из 25 заданных чисел.
Как я уже сказала, программа такая у меня есть (в ней реализована моя формула для пандиагональных квдаратов 5-го порядка, представленная в статье "Общие формулы магических квадратов"), но она очень долго работает. Тестирование программа прошла успешно.
Сейчас она находится в работе у ice00. Если он перепишет её на C++, то, возможно, мне удастся решить эту задачу.

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

[maxal]

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

Меня в данный момент интересует программа построения пандиагонального квадрата 5-го порядка из 25 заданных чисел.

Вот эффективная формула для таких квадратов:

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

Нумерация переменных здесь, как и раньше, в порядке перебора/вычисления значений. Переменные $x_1$, $x_2$, $x_3$, $x_5$, $x_7$, $x_{10}$, $x_{13}$, $x_{18}$ - независимые, остальные - зависимые:

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

[Nataly-Mak]

Да формула у меня тоже есть.
Меня интересует рабочая программа.

У вас формула реализована? Программа уже есть рабочая?

ice00 пишет, что программу переписал и код программы прислал. Осталось отладить её. Думаю, что на C++ программа будет работать намного быстрее, чем на Бейсике.

-- Сб апр 24, 2010 07:53:38 --

Один из тестов для программы построения пандиагонального квадрата 5-го порядка:

7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

Это пандиагональный квадрат из простых чисел (но не наименьший). Я построила его другим методом.

Если ввожу в свою программу этот квадрат, программа возвращает мне его через 10 сек.

ice00 пишет, что у него программа возвращает такой квадрат:

Цитата:

while with the one of square:
{7, 337, 131, 197, 181, 227, 241, 37, 277, 71,
307, 11, 167, 271, 97, 211, 127, 367, 41, 107,
101, 137, 151, 67, 397}
I get:

./a.out
853
7 337 131 4294967295 197
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

KONEC PROGRAMMY

Где-то ошибка.
Никто не может вот так с ходу сказать, в чём может быть причина такой ошибки? Я совсем не знаю C++.
Тем не менее сейчас посмотрю присланный им код программы, может быть, что-нибудь пойму в нём

Если кто-то хочет посмотреть код программы на C++, напишите, выложу.

[Pavlovsky]

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

[Nataly-Mak]

Ошибку в программе ice00 нашла. Как я и предполагала, ошибка в присвоении значений эементам квадрата.
У меня в программе:

A(1,4)=B(4)

в программе у ice00:

A[0][4]=B[3]

а надо написать, наверное, так:

A[0][3]=B[3]

Сейчас напишу ему письмо. Вот такая досадная ошибка приводит к неправильной работе программы.

[Nataly-Mak]

ice00
Программу получила. Огромное спасибо! Ура! Победа!
Мы получили первую программу построения пандиагональных квадратов 5-го порядка из 25 заданных чисел.
Теперь можно только оптимизировать её и получать более совершенные версии.
Протестировала уже программу на том же самом массиве простых чисел:

7 11 37 41 67 71 97 101 107 127 131 137 151 167 181 197 211 227 241 271 277 307 337 367 397

Программа работает до первого найденного квадрата. Всего минутки 3 работала программа и - пандиагональный квадрат найден:

7 41 167 241 397 
197 271 277 37 71 
307 67 101 227 151 
131 107 181 337 97 
211 367 127 11 137

При этом интересно отметить, что найденный квадрат оригинальный, то есть не изоморфен построенному мной раньше другим способом:

7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

Теперь буду проверять по этой программе все потенциальные массивы из простых чисел, из которых существуют обычные магические квадраты 5-го порядка. Авось найдётся и пандиагональный с магической константой меньше 853.

[Nataly-Mak]

Я вспомнила!!!
Долго смотрела на формулу для пандиагонального квадрата 5-го порядка, приведённую maxal'ем. Что-то она мне показалась очень знакомой...

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

x1 = x20 - d + c 
x2 = 65 - x19 - b - x20 + d - x18 - c
x3 = b + x18 - a
x4 = x19 - e + a
x5 = d + x18 - a
x6 = x19 + b - e
x7 = e + x20 - d
x8 = 65 - x19 - b - x20 - x18 
x9 = x20 + a - d
x10 = 65 - x18 - c - x19 - b - x20 + e
x11 = -a + x18 + c
x12 = d - e + x19
x13 = c + x19 - e
x14 = -d + b + x20
x15 = 65 - x18 - c - x19 - b - x20 + a
x16 = x18 + e - a
x17 = 65 - x18 - x19 - x20 - c

(см. статью "Пандиагональные квадраты пятого порядка").

Получена эта формула очень просто. Составлена система 20 уравнений с 20 неизвестными (в этой системе записаны условия магичности и пандиагональности квадрата) и решена в Мапле.
Здесь точно так же 8 независимых переменных и 17 зависимых.
Если теперь заменить 65 на S, то и получим формулу, подобную формуле maxal'а.
Работая сейчас с нетрадиционными квадратами, я совсем забыла об этой формуле 3-х летней давности и вывела другую формулу (иным путём), которая при сравнении с этой формулой проигрывает, так как в ней больше независимых переменных.

Иногда надо перечитывать свои статьи, в них есть много полезного

Теперь займусь реализацией этой старой формулы. Если учесть, что элемент квадрата, стоящий в левой верхней ячейке, можно не варьировать (из-за изоморфизма, связанного с параллельным переносом на торе), то в этой формуле остаётся всего 7 независимых переменных.
Кстати, у меня в статье о классических квадратах этот случай соответствовал знчачению e=1. Он был рассмотрен отдельно.
В моей новой формуле 11 независимых переменных, на 4 больше, чем в старой формуле!
Такое уменьшение количества независимых переменных должно намного улучшить работу программы в смысле времени выполнения.

Вот так выглядит расположение элементов формулы в самом квадрате:

e x1 x2 x3 x4
x5 x6 a x7 x8
x9 x10 x11 x12 b
x13 d x14 x15 x16
x17 x18 x19 c x20

a, b, c, d, e были сразу приняты мной за независимые переменные; x18, x19, x20 были определены как независимые, в результате решения системы уравнений Маплом. Итого получилось 8 независимых переменных. Для остальных 17 переменных Мапл выдал формулы, которые вы видите выше.

[maxal]

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

Здесь точно так же 8 независимых переменных и 17 зависимых.
Если теперь заменить 65 на S, то и получим формулу, подобную формуле maxal'а.

Подобную, да не совсем. В моей формуле очень специальный порядок следования переменных, который позволяет их вычислять/перебирать оптимальнейшим образом. Именно в этом ее заслуга, а вовсе не в том, что в ней 8 независимых и 17 зависимых переменных.

[Nataly-Mak]

maxal
пора от слов об оптимальности ваших формул перейти к получению результатов.

Что-то я не вижу ни магического квадрата 4-го порядка из последовательных смитов, ни пандиагонального квадрата 5-го порядка из простых чисел с магической константой меньше, чем удалось найти мне.

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

[maxal]

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

пора от слов об оптимальности ваших формул перейти к получению результатов.

Вот здесь: post291715.html#p291715 svb практически сравнил вашу и мою формулы для квадратов 5x5 с вполне ожидаемым результатом.

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

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

Реализуйте, что душе угодно. Только не нужно при этом бездоказательно заявлять, что ваша формула аналогична/подобна моей. Я вам здесь уже не раз говорил, в чём именно отличие указанных мной эффективных формул от "аналогичных".

[Nataly-Mak]

Ещё раз подчеркну:
я не сравнивала свою формулу 8+17 с вашей формулой 8+17, а сравнивала свою формулу 8+17 со своей же формулой 11+14!

И аналогия с вашей формулой имеется в том, что и моя, и ваша формула типа 8+17. Этому нужны какие-то доказательства? По-моему, это очевидно всем.

Именно эта аналогия позволила мне вспомнить свою старую формулу.

[Nataly-Mak]

Вчера целый день проверяла программу, сделанную с ice00 по моей формуле 11+14.

Например, массив из смитов, из которого составлен наименьший магический квадрат 5-го порядка (автор 12d3):

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

программа прверила за 28 минут. Ответ однозначный: из данного массива пандиагональный квадрат не существует.
Для массива из последовательных смитов тоже проверила. Программа отработала ещё быстрее и пандиагонального квадрата не составила.

А вот с проверкой массива из последовательных (и из произвольных) простых чисел, из которых складывается наименьший магический квадрат 5-го порядка, дело очень плохо: за 7 часов проверки пока не найден ни один квадрат. Есть подозрение, что результат для этих массивов тоже будет отрицательным, хотя это ещё не факт, а только предположение.

ice00 пишет, что он пытается построить по этой программе классические пандиагональные квадраты. Результат такой же неутешительный: программа работает несколько часов и пока ничего не выдаёт.
А ведь по своей формуле 8+17 я получила все классические пандиагональные квадраты 5-го порядка! И это при том, что программа была написана на Бейсике.
Сейчас немедленно приступаю к реализации этой формулы.

О методике Павловского. Я пока не вникала, как можно найти все перестановки, по которым можно построить пандиагональный квадрат 5-го порядка (хотя бы один) из заданных 25 чисел, если такой квадрат существует. Но уже нашла 6 таких перестановок. Первые две показаны выше. Третья - это классический квадрат. Перестановки я нашла опытным путём. Вот пример ещё одной перестановки:

1 8 12 17 25
14 20 21 7 4
24 3 6 18 13
11 9 19 22 5
15 23 10 2 16

Напомню, что это перестановка из индексов элементов массива чисел, расположенных в порядке возрастания.

maxal
вы можете найти все такие перестановки (аналогично перестановкам для пандиагональных квадратов 4-го порядка, приведённым Павловским)?
Насколько я понимаю, данная методика принципиально отличается от формулы типа 8+17, в которой идёт перебор/вычисление переменных.

Павловский писал, что эта методика позоляет построить пандиагональный квадрат 4-го порядка из заданных 16 чисел мгновенно (если, конечно, он существует). Вот для квадратов 5-го порядка эта методика очень пригодилась бы