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

[Someone]

x8=s-x1-x2-x3-x4-x5-x6-x7
x16=s-x10-x11-x12-x13-x14-x15-x9
x24=s-x17-x18-x19-x20-x21-x22-x23
x32=s-x25-x26-x27-x28-x29-x30-x31
x40=s-x33-x34-x35-x36-x37-x38-x39
x42=-s-x1-x10+x12+x13+x14+x15-x17-x18-x2+x20+2x21+2x22+x23-x25-x26+x28+2x29+2x30+x31-x33-x34+x36+x37+x38+x39-x41-x9
x43=4s+x1-x10-2x11-2x12-x13-x14-x15-x18-2x19-2x20-2x21-x22-x26-2x27-2x28-2x29-x3-x30-x34-2x35-2x36-x37-x38-x39+x41
x44=s-x1+x14+x15-x17-x18-x19-x20-x25-x26-x27-x28+x38+x39-x4-x41
x45=4s+x1-x11-2x12-2x13-2x14-x15+x17-x19-2x20-3x21-2x22-x23+x25-x27-2x28-3x29-2x30-x31-x35-2x36-2x37-2x38-x39+x41-x5
x46=-s-x1+x11+x12+x18+x19+x20+x21+x26+x27+x28+x29+x35+x36-x41-x6
x47=x1+x10-x14-x15+x17+x18+x19-x21-x22-x23+x25+x26+x27-x29-x30-x31+x33+x34-x38-x39+x41-x7+x9
x48=-6s+x10+2x11+2x12+2x13+2x14+x15+x18+2x19+x2+3x20+3x21+2x22+x23+x26+2x27+3x28+3x29+x3+2x30+x31+x34+2x35+2x36+2x37+2x38+x39+x4-x41+x5+x6+x7
x49=9s/2-x11-2x12-2x13-2x14-x15-x19-2x20-3x21-2x22-x23-x27-2x28-2x29-x3-2x30-x31-x35-x36-x37-x38-x39-x4-x5-x6-x7
x50=-s/2+x1+x10+x11-x13-x14-x15+x17+x18+x19+x2-x21-2x22-x23+x25+x26+x27-x29+x3-x30-x31+x33+x34+x35+x9
x51=-7s/2+2x10+2x11+2x12+x13+x17+2x18+2x19+x2+2x20+x21-x23+x25+2x26+2x27+2x28+x29+x3+x34+x35+x36+x4+x9
x52=-9s/2+x10+2x11+2x12+2x13+x14+x17+2x18+3x19+3x20+3x21+2x22+x23+x26+2x27+2x28+2x29+x3+x30+x35+x36+x37+x4+x5
x53=-7s/2+x11+2x12+2x13+2x14+x15-x17+x19+2x20+2x21+2x22+x23+x27+2x28+2x29+2x30+x31+x36+x37+x38+x4+x5+x6
x54=-s/2-x10-x11+x13+x14+x15-x17-2x18-x19+x21+x22+x23-x25-x26-x27+x29+x30+x31+x37+x38+x39+x5+x6+x7-x9
x55=9s/2-x1-2x10-2x11-2x12-x13-x17-2x18-3x19-x2-2x20-x21-x25-2x26-2x27-2x28-x29-x3-x33-x34-x35-x36-x37-x4-x5-x9
x56=9s/2-x10-2x11-2x12-2x13-x14-x18-2x19-x2-3x20-2x21-x22-x26-2x27-2x28-2x29-x3-x30-x34-x35-x36-x37-x38-x4-x5-x6
x57=-7s/2-x1+x11+2x12+2x13+2x14+x15-x17+x19+2x20+3x21+2x22+x23-x25+x27+2x28+2x29+x3+2x30+x31-x33+x35+x36+x37+x38+x39+x4-x41+x5+x6+x7-x9
x58=5s/2-x10-x11-x12-x18-x19-x2-x20-x21-x26-x27-x28-x29-x3-x30-x34-x35-x36-x37-x38-x39+x41
x59=s/2-x1-x10-x11+x14+x15-x17-x18-x19-x2+x21+x22+x23-x25-x26-x27+x29-x3+x30+x36+x37+x38+x39-x4-x41-x9
x60=9s/2+x1-x10-2x11-3x12-2x13-2x14-x15-x18-2x19-3x20-3x21-2x22-x23+x25-x27-2x28-2x29-x3-x30-x35-2x36-x37-x38-x39-x4+x41-x5
x61=s/2-x1-x13-x25+x35+x36+x38+x39-x4-x41-x5-x6
x62=5s/2+x1+x10-x12-x13-2x14-x15+x17+x18-x20-2x21-2x22-x23+x25-x28-2x29-2x30-x31-x35-x36-x37-2x38-x39+x41-x5-x6-x7+x9
x63=-7s/2+x10+2x11+2x12+x13+x14+x18+2x19+x2+2x20+2x21+x22+x26+x27+2x28+2x29+x3+x30+x35+x36+x37+x38+x4-x41+x5
x64=-5s/2+x1+x10+x11+x12+x13+x17+x18+x19+x2+x20+x25+x26+x27+x3+x33+x34+x4+x41+x5+x6+x9

[Nataly-Mak]

Someone
и вам большое спасибо.

Интересно: формулы получились разные, хотя тип в обеих 36+28 (36 свободных переменных и 28 зависимых при заданной магической константе s).
Можно сравнить: какая формула удобнее для программной реализации.
Я вчера почти полностью проверила формулу, полученную dmd; пока всё правильно получилось (проверяю на известном решении, подставляя значения в формулу).
Вот это своё решение взяла для проверки:

5 7 659 613 619 577 109 43
631 587 37 251 127 67 433 499
103 151 373 397 331 491 283 503
571 487 199 193 233 97 443 409
47 73 563 601 661 643 13 31
523 599 211 173 19 79 607 421
313 181 367 163 541 521 277 269
439 547 223 241 101 157 467 457
S=2632

[Nataly-Mak]

Уф! Завершила проверку первой общей формулы (которую dmd привёл).
Всё правильно.
Можно начинать построение пандиагонального квадрата 8-го порядка из последовательных простых чисел.

Выскажу предположение, что магическая константа такого квадрата не будет в заоблачных высотах, как, например, магическая константа наименьшего пандиагонального квадрата 4-го порядка из последовательных простых чисел. Мне кажется, тут должно быть аналогично пандиагональному квадрату 6-го порядка из последовательных простых (см. A073523).

Приглашаю всех к решению этой интересной задачи.
Здесь, скорее всего, не придётся генерировать огромные простые числа. Однако задача не становится от этого совсем простой. Общая формула квадрата перед вами. 36 свободных переменных! Ну, один элемент можно зафиксировать в пандиагональном квадрате. Остаётся 35 свободных переменных из 63. Эвристики? Оптимизации?
Пока я знаю только одну эвристику - использование шаблона.

У Jarek есть большой опыт построения таких квадратов - он в конкурсе их очень много построил. Но его алгоритм, к сожалению, не был описан подробно и доступно для всех. Он рассказал о нём кратко.

[Nataly-Mak]

Ещё известно свойство решёток Россера в пандиагональном квадрате 8-го порядка.
Это свойство заключается в том, что сумма чисел в каждой из 4-х решёток любого пандиагонального квадрата 8-го порядка (см. иллюстрацию) равна $2S$ ($S$ - магическая константа квадрата). Может быть, пригодится это свойство.
На иллюстрации изображено решение Jarek, найденное на конкурсе.
Три решётки окрашены, одна белая.



На статью Россера ссылку давала не один раз. Если понадобится, могу повторить.

[Nataly-Mak]

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

3 5 5 7 5 7 3 5
5 7 1 7 3 7 3 7
1 3 5 7 1 7 5 3
1 7 1 7 1 1 1 5
7 1 5 7 1 3 3 5
5 5 1 1 3 5 3 1
3 1 3 1 3 5 3 5
7 3 3 3 7 5 3 1

Массив простых чисел показан выше. Магическая константа составляемого квадрата $S=4776$.
Я реализовала формулу Someone, она мне показалась удобнее.

Покажу последовательные приближения к решению (опять у меня калейдоскоп )

(Оффтоп)

419  677  509  599  541  631  643  757 
421  479  617  727  563  743  619  607 
433  547  653  719  401  463  773  787 
809  647  761  751  673  0  0  0 
431  457  397  439  769  739  811  733 
709  0  0  641  0  797  0  0 
0  0  691  0  0  0  499  0 
0  0  0  0  503  0  0  409 
X(64)= 409

419  677  509  599  541  631  643  757 
421  479  641  607  659  727  491  751 
433  547  653  719  401  463  773  787 
809  743  761  647  593  449  0  0 
431  457  397  439  769  739  811  733 
613  0  577  601  0  709  0  0 
0  0  499  0  0  0  691  0 
0  0  0  0  503  0  0  409 
X(43)= 577

419  677  509  599  541  631  643  757 
421  479  641  607  659  727  491  751 
433  547  653  719  401  463  773  787 
809  743  761  647  593  449  0  0 
431  457  397  439  769  739  811  733 
613  0  577  601  0  709  0  0 
0  0  499  521  0  0  691  0 
0  0  0  0  503  0  0  409 
X(52)= 521

419  677  509  599  541  631  643  757 
461  503  769  647  739  487  443  727 
433  547  653  719  401  463  773  787 
641  751  673  479  577  593  0  0 
431  457  397  607  809  467  811  797 
661  0  761  409  0  733  0  0 
0  0  491  617  0  0  659  421 
0  0  0  0  439  0  0  521 
X(56)= 421

419  677  509  599  541  631  643  757 
709  479  577  503  587  751  523  647 
433  547  653  719  401  463  773  787 
769  743  673  727  569  761  0  0 
431  457  397  607  809  563  811  701 
733  0  601  409  0  557  0  0 
0  0  467  521  0  0  683  421 
0  491  0  0  487  0  0  449 
X(58)= 491

419  677  509  599  541  631  643  757 
661  647  641  487  587  751  523  479 
433  547  653  719  401  463  773  787 
673  743  769  439  569  761  0  0 
431  457  397  727  809  563  691  701 
709  0  577  601  0  557  0  0 
0  0  491  521  0  0  659  421 
0  443  739  0  607  0  0  593 
 X(59)= 739

419 677 509 599 541 631 643 757
661 647 641 487 587 751 523 479
433 547 653 719 401 463 773 787
673 743 769 439 569 761 0 0
431 457 397 727 809 563 691 701
709 0 577 601 0 557 0 0
0 0 491 521 0 0 659 421
0 443 739 683 607 0 0 593
X(60)= 683

После каждого решения показан последний вычисленный элемент. С каждым приближением готовых элементов становится на один больше, а "дырок" соответственно на одну меньше.
На момент, соответствующий последнему приближению, задано 35 свободных элементов, вычислено 16 зависимых элементов. Имеем решение с 13 "дырками".
При вычислении следующего зависимого элемента x63 программа надолго задумалась. Все предыдущие неполные решения нашлись быстро (в пределах 10-30 минут).

[Nataly-Mak]

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

419  677  509  599  541  631  643  757 
661  647  641  487  587  751  523  479 
433  547  653  719  401  463  773  787 
673  743  769  439  569  761  409  413* 
431  457  397  727  809  563  691  701 
709  693*  577  601  419*  557  595*  625* 
859*  569*  491  521  843*  413*  659  421 
591*  443  739  683  607  637*  483*  593 
S=4776

Это отпущенные 12 зависимых элементов (они помечены звёздочкой):

X(63)= 483, X(32)= 413, X(42)= 693, X(45)= 419, X(47)= 595, X(48)= 625, 
X(49)= 859, X(50)= 569, X(53)= 843, X(54)= 413, X(57)= 591, X(62)= 637

Элементы записаны в порядке вычисления в программе.

Таким образом, приближение с 12 "дырками" получается шутя.
Существует ли полное решение
Не забудем: здесь квадрат строится по шаблону, что резко ограничивает пространство поиска. Но если строить без шаблона и в лоб, то перебор точно уйдёт в беспредел по времени - не выполнить его и за 100 лет
И по шаблону-то туго с перебором в лоб.

Господа! Что-то я не вижу эвристик

[Nataly-Mak]

В решении задач о магических кубах я использовала такой приём: случайно генерировала два слоя куба. А затем достраивание перебором.
Не попробовать ли этот приём при построении пандиагонального квадрата 8-го порядка?

Беру самый первый потенциальный массив:

S=2016 
79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  
179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  
277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  
389  397  401  409  419  421  431  433  439

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



В массиве осталось 48 чисел.
Вторую решётку какую лучше генерировать: белую, сиреневую? По-моему, обе требуют одинаковых усилий при генерации. Тут уже не всё будет случайно.
Можно уже задействовать и перебор: 12 перебираемых элементов из 48.

[Nataly-Mak]

Вторая решётка (беленькая) составилась быстрее первой:



И полквадрата готово!

Как будут строиться оставшиеся две решётки
В массиве осталось 32 числа. Сколько будет свободных элементов - ещё не посчитала.

[Nataly-Mak]

Поиграла с решётками, очень интересно

При построении третьей решётки получилось 8 свободных элементов, а при построении четвёртой - 7. Всего при построении 3-х решёток (первая генерируется случайным образом) получается 27 перебираемых свободно элементов из 48. Не сильно сократилось количество свободных элементов (с 36 до 27), но уменьшилось количество чисел, среди которых элементы выбираются (с 64 до 48).

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

Уже на построении третьей решётки всё застопоривается на элементе x15 (на иллюстрации записан). Так в этой решётке (сиреневой) не нашлись два элемента: x15 и x63.
Ну, а к построению четвёртой решётки и не приступала; если третья полностью не строится, нет смысла браться за четвёртую.

На иллюстрации вы видите почти готовые три решётки:



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

Ау-у-у-у!.. Кто может подбросить идеи?
Статью Россера что ли почитать снова. Может, ещё там какие-то свойства пандиагональных квадратов 8-го порядка есть.

И Pavlovsky совсем пропал, не хочет больше квадратами заниматься
А без него ну ничего не клеится.

-- Вс сен 14, 2014 13:49:31 --

Ещё одну иллюстрацию покажу, это решение Jarek; первые две решётки в программе заданы искусственно (голубая и белая), они точно такие, как в исходном решении:



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

[Nataly-Mak]

Новый эксперимент:
для потенциального массива

S=4464
359  367  373  379  383  389  397  401  409  419  421  431  433  439  443  449  457  461  
463  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571  577  587  
593  599  601  607  613  617  619  631  641  643  647  653  659  661  673  677  683  691  
701  709  719  727  733  739  743  751  757  761

Запустила программу, сделав выход по найденному правильному элементу x15; минут через 15 элемент был найден (помечен звёздочкой):

577 359 523 383 547 739 593 743
397 0 709 0 677 0 *617 0
557 367 499 643 449 719 479 751
647 0 503 0 439 0 683 0
401 373 661 389 601 659 653 727
433 0 487 0 733 0 443 0
761 379 619 419 587 757 421 521
691 0 463 0 431 0 0 0
S=4464

Последний элемент в этой решётке - x63 - уже вычисляется, он получается равным 575, то есть неправильный, "дырка".
Но три решётки построились шутя, хотя и с одним неправильным элементом.

Сейчас попробую запустить программу на поиск правильного элемента x63.

[Nataly-Mak]

Цитата:

Сейчас попробую запустить программу на поиск правильного элемента x63.

Правильный элемент x63 искался вчера до вечера и сегодня с утра часа два. Но он нашёлся!
Есть три готовых решётки в искомом решении:



Использованные 48 чисел:

359  367  373  379  383  389  397  401  409  419  431  433  443  449  457  479  487  499  503  509  521  523  541  547  557  587  593  599  607  613  617  619  641  653  659  661  673  677  691  709  719  727  733  739  743  751  757  761

Оставшиеся 16 чисел:

421  439  461  463  467  491  563  569  571  577  601  631  643  647  683  701

Оставшиеся 16 чисел удовлетворяют необходимому условию: сумма этих чисел равна $2S$.
Осталось выполнить окончательную проверку, то есть попытаться разместить эти 16 чисел в ячейках последней решётки так, чтобы получился пандиагональный квадрат.
Здесь, конечно, полный перебор. Всего 7 свободно перебираемых элементов из 16. Это выполняется быстро.

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

[Nataly-Mak]

Написала программу достраивания полуфабриката. Программа выполняется несколько секунд.
Вот что удалось достроить из показанного выше полуфабриката:

397 359 479 541 523 743 661 761
727 421 487 461 499 563 659 647
449 457 599 719 389 733 367 751
587 0 443 571 503 0 617 577
641 373 739 379 757 401 521 653
431 0 433 701 593 643 673 0
619 383 677 409 691 557 419 709
613 0 607 683 509 0 547 0
S=4464

7 "дырок", видно их, нулики стоят на месте "дырок".
При заданных трёх решётках это фатальные "дырки", то есть полуфабрикат достроить не удаётся, выполняется полный перебор всех возможных вариантов размещения оставшихся 16 чисел в ячейки четвёртой решётки.
Если бы таких полуфабрикатов было несколько тысяч... однако получать их довольно трудно.

[Nataly-Mak]

Нерешённая проблема

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

На иллюстрации изображено решение Jarek, найденное на конкурсе.

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

Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N
Пока это не так. Можно предположить, что решения для N=8,9 подлежат улучшению.

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

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

Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N

Новая проблема века? Добавлю к этой гипотезе еще одну гипотезу.

Существует $N_0$. такое что для всех $N>N_0$ $p/m=1$.

Это проблема минимизации известных пандиагональных квадратов из простых чисел. Сложная проблема! Главная беда в том, что никто ею не занимается
Jarek по горячим следам, сразу после конкурса, занялся этой задачей для $n=7$. И он её решил, хотя это было непросто. Наименьший пандиагональный квадрат 7-го порядка из различных простых чисел с магической константой $S=733 $ найден.
А дальше решать задачу (для следующих порядков) у Jarek энтузиазма не хватило, увы.
Я в то же время занималась немного решением этой задачи для $n=8$ (мои попытки описаны в теме "Дьявольские магические квадраты из простых чисел"). Использовала уникальный алгоритм, основанный на псевдокомплементарных парах чисел. Этот алгоритм был разработан svb для пандиагональных квадратов порядка $n=6$; я приспособила его для порядка $n=8$, что подробно описано в статье. Хотя в теме есть существенное добавление: получена общая формула пандиагональных квадратов 8-го порядка, составленных из псевдокомплементарных пар чисел.

Во второй цитате вы видите табличку, в которой приведено отношение $p/m$. Поясню.
$p$ - магические константы пандиагональных квадратов из простых чисел; $m$ - магические константы обычных МК из простых чисел.
Pavlovky высказал интересную гипотезу об отношении $p/m$ с ростом порядка квадрата $n$.
Собственно, такую же гипотезу высказывал Jarek в самом начале конкурса.
Итак, для порядка $n=7$ мы уже имеем $p/m=1$ (табличка устарела, её надо исправить).
Вполне возможно, что $N_0=7$ (см. гипотезу Pavlovsky).
И тогда для всех порядков $n>7$ можно найти пандиагональные квадраты из простых чисел такие, что $p/m=1$.

[Nataly-Mak]

Изменила табличку



Данные взяла отсюда:
http://www.azspcs.net/Contest/Pandiagon ... inalReport

а также из последовательности OEIS A164843.

Если вы найдёте лучшие решения, чем приведены в таблице, сразу отправляйте их по указанной ссылке. Только на этом сайте (где проводятся конкурсы Al Zimmermann) обязательна регистрация.
А если вы найдёте минимальное решение для $n=8$ (и для следующих порядков), ещё и в последовательность OEIS A179440 его отправьте.

Отмечу: решение для $n=4$ известно давно (автор тоже известен, забыла вот сейчас фамилию эту иностранную, кажется, Джонсон): решение $для n=5$ принадлежит Pavlovsky; для $n=6$ решение принадлежит Radko Nachev (он как-то нашёл меня в Интернете и прислал мне это решение); и для $n=7$ автор решения Jarek Wroblewski (Jarek).
Кто будет следующим в этой уважаемой компании?

[Nataly-Mak]

Программа нашла ещё один полуфабрикат с тремя готовыми решётками (построение пандиагонального квадрата 8-го порядка из последовательных простых чисел):

587  359  613  379  569  727  479  751 
409  0  643  0  599  0  563  0 
701  383  439  389  719  631  463  739 
449  0  683  0  431  0  503  0 
457  397  367  617  467  757  641  761 
571  0  523  0  659  0  661  0 
743  401  577  419  373  541  733  677 
547  0  619  0  647  0  421  0 
S=4464

Этот полуфабрикат нашёлся довольно быстро - около часа работала программа.
Сейчас проверю, как тут пойдёт достраивание четвёртой решётки. В предыдущем эксперименте получилось 7 фатальных "дырок" в четвёртой решётке.

-- Вт сен 16, 2014 15:43:56 --

То же самое:

587  359  613  379  569  727  479  751 
409  509  643  653  599  487  563  601 
701  383  439  389  719  631  463  739 
449  0  683  691  431  0  503  499 
457  397  367  617  467  757  641  761 
571  0  523  709  659  521  661  0 
743  401  577  419  373  541  733  677 
547  0  619  607  647  0  421  0 
S=4464

Не достраивается полностью четвёртая решётка