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

[Nataly-Mak]

Mathusic в сообщении #256143 писал(а):

Nataly, не могли бы Вы привести общие алгебраические формулы для квадратов порядков $4$ и $5$?

Начну с квадрата порядка 4.
Интересно, что квадрат 4-го порядка тоже может быть построен из 16 чисел, которые складываются в такие арифметические прогрессии «вдоль» и «поперёк», как и для квадрата 3-го порядка:

a a+b a+2b a+3b
a+c a+c+b a+c+2b a+c+3b
a+2c a+2c+b a+2c+2b a+2c+3b
a+3c a+3c+b a+3c+2b a+3c+3b

Но в отличие от квадратов 3-го порядка для квадратов порядка 4 это условие не является необходимым, оно только достаточное. То есть магический квадрат 4-го порядка может быть составлен и из таких 16 чисел, которые не складываются в показанные прогрессии.
В книге Ю. В. Чебракова «Магические квадраты. Теория чисел, алгебра, комбинаторный анализ» (С.-Петербург, 1995) приведена общая алгебраическая формула магического квадрата 4-го порядка, но как её понимать, я не разобралась (очень уж всё как-то замороченно написано аж на 6 листах (стр. 218 – 233)). Формула эта выглядит так:

A+c B+b C+d D+a
D+d C+a B+c A+b
B+a A+d D+b C+c
C+b D+c A+a B+d

У Чебракова есть ещё одна книга о магических квадратах, которая выложена в Сети. Книга называется «Теория магических матриц». Может быть, там тоже есть эта формула, и желающие могут в ней разобраться.
Когда я составляла программу для построения нетрадиционных магических квадратов 4-го порядка, глянула на эту формулу, разбираться в ней не захотелось, и составила программу по-своему. Кстати, моя программа выложена в этой ветке. Программа очень быстро проверяет построение магического квадрата из заданного массива, состоящего точно из 16 чисел. В программу надо ввести только этот массив, и она сразу даст однозначный ответ: существует или нет магический квадрат из данного массива. Как я уже говорила, проверила по этой программе 800 первых кандидатов в магические квадраты из последовательных смитов. Не помню, в каком виде я выложила здесь программу. Но при проверке 800 различных массивов я, конечно, вводила в программу уже не один массив, а сразу порцию из 200 массивов, и программа проверяла их все сразу. Даже на Бейсике 200 массивов программа проверяет за несколько минут (примерно 20-30 минут). Если переписать программу на нормальный язык, можно с её помощью проверить много кандидатов в магический квадрат 4-го порядка из последовательных смитов. Да и массив смитов у меня сгенерирован только до 100000.
Если кто-то будет проверять квадраты 4-го порядка из последовательных смитов, можно начинать сразу с 801-го кандидата.
Общая алгебраическая формула квадрата 5-го порядка приведена в указанной выше книге Ю. В. Чебракова на стр. 296-299. В этой формуле я разобралась, но очень много переписывать. Суть её такова: в квадрате 5х5, который вы видите ниже, все ai – свободно задаваемые элементы, а все xi – зависимые элементы, которые полностью определяются свободными элементами, то есть вычисляются через них.

x7 x6 x10 x5 x3
x8 a7 x9 a9 x4
a11 a12 a13 a14 x2
a16 a17 a18 a19 x1
a21 a22 a23 a24 a25

Когда я работала с квадратами 5-го порядка из смитов, посмотрела на эту формулу и подумала, что вряд ли она может дать быстрый результат. По сути дела, по этой формуле надо выполнить лобовой перебор 15 элементов из 25. Конечно, это значительно меньше комбинаций, чем если перебрать 25 элементов из 25, но всё равно очень много. Поэтому данная формула кажется мне совершенно бесполезной.
Далее автор книги пишет, что аналогичная общая алгебраическая формула может быть составлена для магического квадрата любого порядка (стр. 295). Это понятно.

[dezdlisa]

Цитата:

В книге Ю. В. Чебракова «Магические квадраты. Теория чисел, алгебра, комбинаторный анализ» (С.-Петербург, 1995) приведена общая алгебраическая формула магического квадрата 4-го порядка, но как её понимать, я не разобралась.

Nataly, не могли бы вы дать ссылочку на эту книгу, если есть, или выложить свой экземпляр. Хочу попробовать разобраться. Теория магических матриц у меня есть. Останется только вникнуть в суть формул, может не так уж все и безнадежно с этими формулами для создания быстродействующего алгоритма.
Кстати, просьба к программистам данного форума, не могли бы вы занятся вопросом переписи программ Nataly, чтоб сделать из них хотябы экзешники. Q-Basic на седьмой винде не пашет, и вообще такие программы должны иметь свое "тело", а не являться всего лишь набором символов.
Заранее благодарен, надеюсь найдутся люди, которые займутся этим всерьез. Ведь материал действительно ценный, только нужно сделать его вседоступным без использования интерпритаторов.

[Nataly-Mak]

Указанная книга Ю. В. Чебракова у меня имеется в бумажном виде. Есть ли она в Сети, не знаю. Попробуйте поискать.

[shwedka]

http://chebrakov.narod.ru/

[Mathusic]

shwedka в сообщении #256238 писал(а):

http://chebrakov.narod.ru/

Спасибо, Shwedka, но это не та книга. "Та" книга - Ю. В. Чебракова «Магические квадраты. Теория чисел, алгебра, комбинаторный анализ» (С.-Петербург, 1995)

[Nataly-Mak]

Сейчас проверила по своей программе первые 10 кандидатов в магические квадраты 5-го порядка из последовательных смитов. Моя программа не даёт гарантированного ответа на все 100%, но где-то на 99,9% ответ правильный. Ошибка возможна, но маловероятна. Для всех 10 кандидатов ответ отрицательный - магический квадрат не найден. Более того: не найден даже ни один полумагический квадрат. Понятно, почему и программы ice00 для этих кандидатов ничего не нашли. Скорее всего, таких магических квадратов не существует. Проверять следующих кандидатов можно, но уже как-то не хочется. Нет результатов и - нет вдохновения.
Кроме того, меня сейчас постигла страшная неудача: я очень подробно описала свой новый алгоритм построения магического квадрата 6-го порядка, но пока я его описывала, провайдер вырубил мне Интернет, я, конечно, этого не заметила и нажала на кнопку "Предпросмотр", в результате у меня всё пропало. Это чёрт знает что такое! Писать всё второй раз совсем не хочется. Может быть, выложить краткое описание, которое я послала ice00 (он ведь меня прекрасно понял, несмотря на незнание русского языка)? А потом я вот думаю: а нужно ли это вообще кому-нибудь здесь? Например, два участника отказались заняться реализацией этого алгоритма.
Если у ice00 не получится, значит, алгоритм не пригоден для реализации. Хотя, как я уже говорила, поэтапно я его реализовала на Бейсике, и всё прекрасно работает. Но чтобы получить результат, надо всё это объединить в одну общую программу и выполнить в полном объёме. Мне это не по силам.

[Mathusic]

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

Сейчас проверила по своей программе первые 10 кандидатов в магические квадраты 5-го порядка из последовательных смитов. Моя программа не даёт гарантированного ответа на все 100%, но где-то на 99,9% ответ правильный. Ошибка возможна, но маловероятна. Для всех 10 кандидатов ответ отрицательный - магический квадрат не найден. Более того: не найден даже ни один полумагический квадрат. Понятно, почему и программы ice00 для этих кандидатов ничего не нашли. Скорее всего, таких магических квадратов не существует. Проверять следующих кандидатов можно, но уже как-то не хочется. Нет результатов и - нет вдохновения.
Кроме того, меня сейчас постигла страшная неудача: я очень подробно описала свой новый алгоритм построения магического квадрата 6-го порядка, но пока я его описывала, провайдер вырубил мне Интернет, я, конечно, этого не заметила и нажала на кнопку "Предпросмотр", в результате у меня всё пропало. Это чёрт знает что такое! Писать всё второй раз совсем не хочется. Может быть, выложить краткое описание, которое я послала ice00 (он ведь меня прекрасно понял, несмотря на незнание русского языка)? А потом я вот думаю: а нужно ли это вообще кому-нибудь здесь? Например, два участника отказались заняться реализацией этого алгоритма.
Если у ice00 не получится, значит, алгоритм не пригоден для реализации. Хотя, как я уже говорила, поэтапно я его реализовала на Бейсике, и всё прекрасно работает. Но чтобы получить результат, надо всё это объединить в одну общую программу и выполнить в полном объёме. Мне это не по силам.

Выкладывайте, Nataly! Может быть кто-нибудь заинтересуется.

[dezdlisa]

Цитата:

http://chebrakov.narod.ru/

Да, спасибо, но у меня эта книга есть. Это теория магических матриц.
Попробую поискать конечно еще, но первая попытка не увенчалась успехом, сноски есть на эту книгу, но самой книги нет.

-- Чт окт 29, 2009 18:30:13 --

Цитата:

А потом я вот думаю: а нужно ли это вообще кому-нибудь здесь?

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

[Mathusic]

Уважаемые участники!
Хотелось бы узнать какие диапозоны уже проверены на минимальные квадраты порядка $3,4,5,6$ из последовательных смитов?

[ice00]

Цитата:

Может быть, выложить краткое описание, которое я послала ice00 (он ведь меня прекрасно понял, несмотря на незнание русского языка)? А потом я вот думаю: а нужно ли это вообще кому-нибудь здесь? Например, два участника отказались заняться реализацией этого алгоритма.
Если у ice00 не получится, значит, алгоритм не пригоден для реализации.

As I'm a programmer from the age of 9, I know that all can be implemented, it is only question of cost and time. There is no cost for me as this is a for fun research , so it is only question of time. So it need me a lot of (free) time to implement the Natalia idea, but if you divide the algorithm in parts and implement them one by one, it is no different that implement any program I every day code for work.

Regarding the Natalia algorithm that is focused onto order 6, I will code instead somethig parametric (like the other programs) and only the part that need to be specific for order 6 will be code as Natalia describe (it is the last part of algorithm).
But at that time all before that point will be already implemented and maybe I could have find a way to have even that part extended to any order..

[Nataly-Mak]

Спасибо, ice00! Вы вселили в меня надежду, что алгоритм может быть реализован и, возможно, даст результаты. Кстати, точно такой же алгоритм можно применить для построения магических квадратов 5-го порядка из смитов; в этом случае всё будет гораздо проще, особенно для этапа преобразования наборов из 3-х строк, так как количество комбинаций будет значительно меньше.
Я тестировала все свои отдельные программы для каждого этапа с помощью исходного массива, из которого мной построен квадрат 6-го порядка из смитов (этот квадрат здесь показан). Программа каждого этапа работает и выдаёт ожидаемые результаты. Это даёт мне надежду, что и вся программа в целом будет работать. Когда она будет у вас полностью готова, вы тоже можете протестировать её с помощью этого массива смитов. Она должна будет составить известный магический квадрат из данного массива. Понятно, что эту программу можно останавливать в тот момент, как она найдёт первый квадрат.
Скажите, как вы оцениваете примерное быстродействие готовой программы для квадрата порядка 6, составленной по данному алгоритму?
Один технический момент, который я не указала в письме: желательно, чтобы программа проверяла не один массив, а сразу несколько массивов, потому что, конечно, придётся проверять много разных массивов. Тот массив, который я написала вам в письме, даёт магическую константу 2787; я выбрала его, потому что из данного массива у меня составляется очень много полумагических квадратов, есть надежда, что будет получен магический квадрат. Хотя, конечно, этого может и не произойти.
Ещё раз спасибо. Я буду ждать и надеяться на самый лучший исход дела

[Nataly-Mak]

Представляю свой алгоритм в том виде, как я описла его для ice00.
"Мы будем брать массив из 36 чисел. Значит, магическая константа нам тоже известна.
Первый этап: образуем все наборы по 4 строки так, что сумма чисел в строках равна магической константе квадрата. Такие наборы мы можем сделать все. Так?
Для примера возьмём такой массив смитов:

562, 690, 483, 27, 391, 634, 852, 378, 438, 382, 202, 535, 121, 517, 274, 166, 1255, 454, 22, 94, 85, 1165, 526, 895, 576, 346, 778, 728, 355, 4, 654, 762, 729, 319, 58, 265

Магическая константа равна 2787 (как я уже говорила, у меня очень много полумагических квадратов получается с такой магической константой; есть вероятность получить магический квадрат).
Тогда пример набора из четырёх строк такой:

4 346 355 576 728 778
22 85 94 526 895 1165
27 391 483 562 634 690
121 166 274 454 517 1255

Сколько будет таких наборов строк, я не могу сказать, но их будет конечное множество, и количество их не очень велико, вполне реально их все получить. Понятно, что все числа в таком наборе должны быть различные.
Заметьте, что числа в каждой строке следуют в порядке возрастания.
На следующем этапе берётся такой набор из четырёх строк (как показан выше) и из него получаются все варианты. Для получения вариантов можно применить много способов, самый простой: переставить все строки и столбцы в этом наборе строк. Вариантов, полученных таким способом, будет 17280. Это не очень много вариантов. Другой способ: перестановка всех чисел в строках и перестановка строк. Этот способ даст намного больше вариантов, но это выгодно. Можно попробовать оба способа.
На следующем этапе обрабатывается каждый набор строк, полученный на предыдущем этапе.
Теперь у нас остались свободными 12 чисел массива, которые мы должны разместить в двух строках квадрата. Достаточно варьировать всего три переменные; варьируются элементы I, J, K.

4 346 355 576 728 778
22 85 94 526 895 1165
27 391 483 562 634 690
121 166 274 454 517 1255
X   X   K   X   X   X
I   X   X   X   X   J

Все остальные элементы (Х) вычисляются в зависимости от значений I, J, K. Остаётся проверить, будут ли принадлежать все эти вычисленные элементы массиву из 12 чисел (за вычетом элементов I, J, K). Варьируемые переменные I, J, K пробегают весь массив из 12 чисел".

Теперь покажу результаты теста для массива смитов:

22, 94, 346, 382, 562, 778, 1822, 1966, 2326, 2362, 2578, 2902, 20362, 20506, 20542, 20974, 21226, 21262, 681817, 682177, 682393, 682609, 682681, 682897, 1446106, 1446142, 1446178, 1446538, 1446574, 1446934, 3003898, 3004186, 3004402, 3004618, 3004654, 3004762

Из данного массива программа генерирует всего 833 строки, содержащие по 6 чисел, так, что сумма чисел в каждой строке равна магической константе квадрата - $5156763$. На первом этапе среди всех наборов из 4-х строк должен быть получен такой набор:

346 2902 20542 682177 1446142 3004654
382 1822 21226 682897 1446538 3003898
562 1966 21262 682393 1446178 3004402
778 2326 20506 681817 1446574 3004762

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

 1822 21226 682897 1446538 3003898 382
3004762 681817 778 2326 1446574 20506
1446142 2902 3004654 20542 346 682177
21262 1446178 1966 562 682393 3004402

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

1822 21226 682897 1446538 3003898 382
3004762 681817 778 2326 1446574 20506
1446142 2902 3004654 20542 346 682177
21262 1446178 1966 562 682393 3004402
94 3004618 1446106 682609 20974 2362
682681 22 20362 3004186 2578 1446934

Всё срабатывает абсолютно чётко!
Для меня в реализации этого алгоритма самым сложным и невыполнимым на Бейсике является второй этап – преобразование всех наборов из 4-х строк. Первый и третий этапы выполняются элементарно.

-- Пт окт 30, 2009 08:49:05 --

И вот результаты тестирования алгоритма для квадрата Бодигрима порядка 5 из смитов.
Массив смитов, из которого построен квадрат:

 4, 22, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 382, 391, 454, 483, 517, 526, 562, 634, 645, 663, 762, 825

Из данного массива программа генерирует всего 236 строк, состоящих из 5 чисел, так что сумма чисел в каждой строке равна магической константе квадрата - $1831$.
Вот начало файла, куда программа записывает все эти строки:

 4  22  346  634  825 
 4  22  454  526  825 
 4  22  517  526  762 
 4  22  526  634  645 
 4  58  382  562  825 
 4  85  346  634  762 
 4  85  355  562  825 
 4  85  391  526  825 
 4  85  454  526  762 
 4  85  517  562  663 
 4  94  274  634  825 
 4  94  346  562  825 
 4  94  382  526  825 
 4  94  391  517  825 
 4  94  454  517  762 
 4  94  454  634  645 
 4  94  526  562  645 
 4  121  319  562  825 
 4  121  355  526  825 
 4  121  382  562  762 
 4  121  517  526  663 
 4  166  202  634  825
. . . . . . . . . . . . . . . . . 

Среди всех наборов из 3-х строк, составляемых на первом этапе, должен быть получен такой набор:

4 166 265 634 762
85 346 355 382 663
94 121 454 517 645

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

 4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94

Совершенно очевидно, что такой вариант получается из первоначального набора только перестановкой чисел в строках, строки в этом случае не переставлены.
Переходим к последнему этапу. Для квадрата 5-го порядка остаются свободными 10 чисел, и варьировать надо всего два элемента - I, J:

 4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94
X    X    X    X    X  
I    X    X    X    J

Понятно, что если мы придём к последнему этапу с показанным набором из 3-х строк, магический квадрат обязательно будет построен, вот такой:

 4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94 
526 483 58 202 562 
274 319 22 391 825

Следует отметить, что данный алгоритм идеально подходит для проверки кандидатов в магические квадраты порядков 5 и 6 из последовательных смитов. Для квадратов из произвольных смитов сложность в том, что мы не знаем, из какого массива будет составлен магический квадрат и поэтому нам придётся проверять много разных массивов.

Уважаемые участники! Большая просьба: напишите, как поняли алгоритм, как оцениваете его эффективность и возможности для реализации. Спасибо.

[ice00]

Цитата:

Tell me, how do you estimate the approximate speed of the final program for the square of the order of 6, compiled by the algorithm?

I don't know this actually, but usually a compiled program is 10 or more time faster of a interpreted language.

[Mathusic]

Я пропустил. Какова верхняя оценка для константы квадрата порядка $6$ из произвольных смитов?

[Nataly-Mak]

Вы запускаете программу поиска наименьшего квадрата 6-го порядка из произвольных смитов? Алгоритмом не поделитесь?
Минимальная константа квадрата 6-го порядка из произвольных смитов находится на отрезке [2460, 5156763]. Для квадрата данного порядка из последовательных смитов минимальная константа >=3873.