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

[Nataly-Mak]

Вот на этом квадрате проверяю:

67 193 71 251 109 239
139 233 113 181 157 107
241 97 191 89 163 149
73 167 131 229 151 179
199 103 227 101 127 173
211 137 197 79 223 83

Из формулы для магической константы выразила элемент a1:

a1 = S/2 - a7 + a4 + a5 + a6 - a2 - a3 - a8 - a9

Вычислила, получилось правильно: a1 = 67.

Расположение элементов в квадрате показано в посте, где приведена система уравнений.
Запрограммировала остальные формулы и вычислила все элементы. Почему-то два элемента не получились: x5 и x12. Остальные все получились.

Получается: x5 = -451, x12 = 5.
Может быть, сама ошиблась, но три раза проверила и перепроверила, вроде правильно формулы записала.
Должно быть: x5 = 233, x12 = 163.

Сейчас буду снова проверять, вручную посчитаю.

[Garik2]

Кажется я понял, наверное. Если посмотреть мои рисунки, то для x5 и x12 в конце плюсики очень нечеткие. В трех местах вертикальные черточки плюсов едва-едва видны и можно спутать с минусом . Поэтому дам формулы:

x5=1/3*a4+4/3*a5+4/3*a6-4/3*a1-1/3*a2-4/3*a3-x21-4/3*a7-1/3*a8-7/3*a9+a11+x22+a10+2*x23+x15

x12=-1/3*a4+2/3*a5+2/3*a6-2/3*a1-2/3*a2-2/3*a3-2/3*a7-2/3*a8-2/3*a9+x22+x23+a11+a12

Теперь наверняка все верно будет. Рисунки подправил. Теперь плюсики видны.

А вообще-то исходник такой:

solve({a1+x1+a2+x2+a3+x3=S,x4+x5+x6+x7+x8+x9=S,
x10+a4+x11+a5+x12+a6=S,x13+x14+x15+x16+x17+x18=S,
a7+x19+a8+x20+a9+x21=S,x22+a10+x23+a11+x24+a12=S,
a1+x4+x10+x13+a7+x22=S,x1+x5+a4+x14+x19+a10=S,
a2+x6+x11+x15+a8+x23=S,x2+x7+a5+x16+x20+a11=S,
a3+x8+x12+x17+a9+x24=S,x3+x9+a6+x18+x21+a12=S,
a1+x5+x11+x16+a9+a12=S,x3+x8+a5+x15+x19+x22=S,
a1+a10+a8+x16+x12+x9=S,x4+x1+x23+x20+x17+a6=S,
x10+x5+a2+a11+a9+x18=S,x13+a4+x6+x2+x24+x21=S,
a7+x14+x11+x7+a3+a12=S,x3+x24+x20+x15+a4+x4=S,
x9+a3+a11+a8+x14+x10=S,a6+x8+x2+x23+x19+x13=S,
x18+x12+x7+a2+a10+a7=S,x21+x17+a5+x6+x1+x22=S},
[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,
x18,x19,x20,x21,x22,x23,x24,S]);

[Nataly-Mak]

Да, я уже сама вывела эти формулы. Просто выразила x5 и x12 через S и другие xi. Сразу обнаружила ошибки в знаках.
Да, действительно, там есть чёрточки, я сейчас присмотрелась. Когда я сделала фотографии (копии), эти чёрточки уже совсем стали не видны. Поэтому я приняла эти плюсы за минусы.
Теперь всё получилось правильно. Спасибо.

Итак, общая формула пандиагонального квадрата 6-го порядка есть. Она получилась типа 16 + 20. В принципе можно попробовать реализовать, но, скорее всего, как говорит maxal, программа будет выполняться очень долго. Хотя возможны и случаи везения. Не является ли именно таким счастливым случаем приведённый квадрат из последовательных простых чисел?

Если же преобразовать формулу с учётом ассоциативности, то для идеального квадрата по идее должна получиться формула типа 8 + 28. Это уже вполне приемлемо для реализации.

[Garik2]

Если у Вас программа есть, то смогу помочь в счете. Достаточно здесь или мне на почту скинуть текст, сказать - какой интерпретатор. Я последний скачаю, установлю и буду на ночь гонять прогу хоть до посинения.

[Nataly-Mak]

Большое спасибо за такое грандиозное предложение!

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

Я буду иметь в виду ваше предложение и когда появится необходимость погонять какую-нибудь программу, я вам напишу.

[Garik2]

Хорошо. Только просьба - чтобы я не думал об изменениях текста. То есть, чтобы нажал Enter, - и пошел спать. А уж результат пусть записывается в файл. Его-то я и отправлю назад почтой для изучения. Вы посмОтрите, поморщитесь, поколдуете, дадите новый вариант проги. И так до полного триумфа.

[Nataly-Mak]

Garik2 в сообщении #344645 писал(а):

Хорошо. Только просьба - чтобы я не думал об изменениях текста.

Это само собой

Да, общая формула пандиагонального квадрата 6-го порядка действительно получилась интересная.

Ею можно пользоваться в случае, если массив состоит точно из 36 чисел и, следовательно, магическая константа известна. Это оптимальный вариант: проверка заданного массива из 36 чисел на возможность составления из чисел этого массива пандиагонального квадрата 6-го порядка.

Далее, она годится и для случая, когда магическая константа задана, но массив состоит из более 36 чисел.

И, наконец, она пригодна и для случая, когда магическая константа неизвестна и массив любого размера. Только в этом случае количество независимых элементов на единицу больше (17).

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

[maxal]

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

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

Потому что каждая из этих формул оптимизирована для эффективного перебора.

[Nataly-Mak]

Пишу программу, реализующую полученную формулу пандиагонального квадрата 6-го порядка.
Пока написала половину. Протестировала на том же самом пандиагональном квадрате из последовательных простых чисел с магической константой 930. В первом этапе у меня 8 независимых элементов - из 36! И программа выполняет этот этап мгновенно.
Осталось ровно половина - ещё 8 свободных элементов. По-моему, моё предположение верное: этот квадрат - счастливый случай. Числа этого массива складываются в пандиагональный квадрат не одним только способом, а очень многими и результат получается быстро.
Однако... допишу программу до конца, посмотрю, что получится.

maxal
как быстро ваша программа выдаёт пандиагональный квадрат из этого набора чисел? (квадрат показан чуть выше, я проверяла на нём общую формулу)

[Nataly-Mak]

У меня прямо настоящий захватывающий детектив! Уже запрограммировала 14 свободных переменных! Результат выдаётся мгновенно! То есть программа вычисляет все зависимые элементы, проверяет их на принадлежность заданному массиву чисел и выдаёт их все.

Осталось всего два вложенных цикла - два свободных элемента.
14 из 36 - это уже немало. И программа моментально это отрабатывает.
Массив такой замечательный - это единственное объяснение происходящего.

Пойду подкреплюсь перед последним шагом

[Nataly-Mak]

Увы, чуда не произошло

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

Итак, общая формула есть, но она мало пригодна для реализации. Нужно искать другой алгоритм построения пандиагонального квадрата 6-го порядка.

И где же 12d3? Он наверняка такой алгоритм может придумать. Да ему и придумывать нечего! У него есть программа построения всех МК 6-го порядка из заданных 36 чисел. Надо немного модифицировать эту программу, чтобы она строила не все, а только пандиагональные квадраты.

А мне вот надо придумывать

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

7 83 61 37 157 139
89 101 13 149 19 113
31 67 73 163 47 103
109 131 43 107 53 41
151 23 127 17 137 29
97 79 167 11 71 59

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

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

Да, ещё такой вопрос ко всем. Берём мы заданный массив из 36 чисел, строим по программе 12d3 все МК 6-го порядка. Их иногда получается очень много, но почти всегда удаётся построить все. Теперь имеем большой массив квадратов. Есть очевидный путь: взять все эти квадраты и проверить их на пандиагональность. Но у меня проблемы с массивом, Бейсик не берёт большие массивы. Как вы думаете, в принципе это реально?

Программа 12d3 у меня есть и она работает. Но она исполняемая, исходника нет, поэтому модифицировать невозможно. Это может сделать только сам 12d3.

[Garik2]

Что значит "программа застряла"? Считает, считает - а конца не видно? Или же зацикливается?

Теперь насчет второго вопроса о проверке на пандиагональность. Если каждый МК состоит всего-то из 36 элементов, то проверять на пандиагональность проще пареной репы. Дайте мне все эти МК - я проверю.

[Nataly-Mak]

Да, она считает, работает. Но в программе 16 вложенных циклов! Это очень много. Конца не видно, как вы правильно заметили.
Зафиксировав значения переменных первых 7 циклов, результат получаю мгновенно.
Сколько придётся программе работать, чтобы отработать все циклы - одному Богу известно.
Конечно, можно попробовать переписать программу на другой язык. Одну из программ мне ice00 переписал на С++ (это была программа построения пандиагонального квдарата 5-го порядка тоже по общей формуле, но там формула типа 8 + 17, то есть всего 8 вложенных циклов). Это намного уменьшило время выполнения программы.
Плюс ко всему у меня компьютер тихоход (уже много раз в этом убеждалась сравнением времени выполнения одних и тех же программ у меня и у других).

Только что увидела насчёт проверки квадратов на пандиагоанльность. Да, проверить квадраты на пандиагональность - это просто. Но квадратов очень много
А что если сделаем так: чтобы не заниматься пересылкой очень больших массивов квадратов, я пришлю вам исполняемую программу, которая строит все МК 6-го порядка из заданного массива, состоящего из 36 чисел и для начала один массив из 36 чисел (эта программа исполняемая). И вы проделаете эти операции: сначала построите все квадарты, а потом их проверите. Так годится?

[Garik2]

16 циклов - это очень много. Можно даже рассчитать, сколько лет комп будет пахать. Надо выяснить, за сколько времени прога проходит, скажем 10 циклов. Если терпимо, то раздать многим участникам блоки циклов, - пусть у каждого крутится свой участок. Главное, чтобы Ваша прога была верной, то есть безошибочной.
Когда у меня подобные комбинаторные задачи, то делаю так. После самого внешнего цикла ставлю оператор print "1";
После начала следующего цикла - оператор print "2"; И так далее. Но не все 16 циклов, а для первых, допустим, 8. И на экране тогда будет видно, как быстро крутятся циклы.

[Nataly-Mak]

Тут есть один нюанс: все циклы не отрабатывают полностью от 1 до 36, из многих циклов мы выходим по невыполнению условия принадлежности полученных значений зависимых переменных заданному массиву чисел.
Поэтому чем больше мы "вылетаем" из циклов, тем быстрее выполнится программа. Вот если ввести в эту же программу массив из 36 смитов, то она может и отработать полностью, например, за часок.
Это уже я много раз наблюдала. Например, та же программа для построения пандиагональных квадратов 5-го порядка для смитов выполняется в разы быстрее, чем для простых чисел.