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

[svb]

Пока Зиммерман исправляет ошибки Jarek Wroblewski выложил свой квадрат порядка 28 с объемом 219822:

1 5 259 659 257 713 712 282 256 283 657 255 656 284 726 725 254 285 654 253 286 55 673 674 471 645 7 3 
9 640 664 25 717 26 27 716 715 714 28 668 29 744 30 31 730 743 50 681 680 679 51 52 678 206 646 11 
265 665 355 722 496 618 71 484 95 121 721 400 774 418 130 176 293 541 749 479 106 175 389 148 230 682 43 644 
663 14 724 356 313 513 75 189 198 449 213 775 87 478 539 139 326 60 451 750 461 566 141 442 638 477 677 276 
266 720 164 572 354 226 491 171 512 117 776 247 244 503 435 85 629 406 144 634 751 592 462 125 134 514 44 672 
711 15 565 116 100 357 579 112 637 777 108 469 433 546 80 559 525 468 526 227 146 752 368 557 328 212 46 671 
710 16 153 174 222 119 353 627 778 64 297 456 544 474 178 473 410 563 515 331 403 387 753 402 569 304 45 670 
709 17 70 325 168 509 445 779 166 366 401 83 92 482 129 338 408 492 585 529 369 298 424 754 582 519 676 275 
267 719 156 103 455 531 780 391 358 537 76 142 367 309 522 245 320 437 632 386 545 497 224 123 755 161 675 277 
264 718 444 600 508 781 196 553 65 352 488 344 624 104 216 551 98 616 370 294 233 101 416 490 109 756 47 652 
662 18 723 417 782 310 564 606 420 483 359 518 548 246 475 58 628 385 571 69 149 223 335 235 86 113 733 274 
263 669 218 783 127 429 581 77 399 136 88 351 602 538 636 635 371 220 74 570 99 633 543 498 502 173 48 727 
661 19 784 407 179 184 195 609 393 495 203 567 360 576 394 384 388 137 625 154 523 229 489 485 219 314 738 279 
268 748 597 307 505 615 441 315 583 562 194 542 446 350 372 588 316 443 120 162 89 102 560 317 110 329 737 272 
729 20 521 177 232 340 128 411 152 122 334 241 605 383 361 412 578 202 619 73 611 549 589 587 432 568 736 278 
262 746 68 580 242 187 558 183 398 601 594 182 373 296 460 349 332 556 205 419 614 323 547 586 207 114 735 273 
269 745 458 131 111 78 337 610 532 612 622 382 59 365 554 448 362 613 82 574 172 493 466 126 145 630 734 280 
261 747 158 465 598 221 459 214 524 167 374 608 533 409 319 330 595 348 181 428 305 453 584 199 61 765 33 651 
660 21 773 536 561 94 345 165 204 381 621 528 447 211 500 135 452 342 363 301 396 527 185 225 764 306 666 281 
270 694 517 772 392 431 312 240 375 190 617 151 91 324 333 520 231 215 511 347 540 238 97 763 413 707 49 650 
260 693 105 405 771 550 295 380 302 336 311 620 234 133 427 197 516 150 90 607 364 425 762 486 67 530 703 271 
53 692 300 163 631 770 376 191 157 552 414 415 555 422 626 590 339 507 79 188 147 761 430 308 436 132 702 54 
683 22 397 423 535 379 769 155 421 494 322 454 390 217 510 623 107 200 591 186 760 341 346 593 237 115 24 696 
684 23 228 118 377 575 303 768 327 534 487 573 438 472 457 599 464 439 143 759 604 138 160 72 395 124 32 697 
480 691 209 378 440 504 140 501 767 81 201 159 404 210 467 577 57 169 758 193 426 470 93 596 639 180 701 499 
648 258 695 299 192 208 481 321 318 766 463 96 63 506 84 236 239 757 343 708 450 243 170 434 603 706 62 641 
10 649 38 690 39 37 689 688 687 40 732 36 742 741 740 739 731 41 667 35 705 42 34 13 704 66 643 12 
2 6 647 287 686 685 288 252 251 658 289 728 250 249 290 248 291 655 292 653 56 698 699 700 476 642 8 4 

[svb]

Мой вольный перевод письма Jarek Wroblewski:

Цитата:

Для тех, кто заинтересовался подходом парня, не достигшим 50-ой позиции, предлагается моя история: -)

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

1. Я предположил, что имеется центральное озеро, которое является квадратом с обрезанными углами. Такой угол имеет один параметр - размер. Следовательно озеро имеет 4 параметра - а именно 4 угловых размера.

2. Для каждого углового размера я рассмотрел несколько версий системы заполнения водоемов.

3. По данным 4 угловым размерам и соответствующим 4 проектам систем углов водоема, я установил набор правил для вычисления общего объема воды квадрата прежде, чем конкретный квадрат быдет создан.

4. Поэтому имелось много возможных проектов квадрата, но я мог вычислять их объем.

5. Затем я стал создавать квадрат, использующий самый лучший проект из тех, которые я нашел, с помощью набора правил конструирования.

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

7. Я воспользовался скриптом Mathematica, но часто требовалось мое вмешательство или решение для частного квадрата. Al доброжелательно обеспечил интерактивный подсчет очков, который допускал проверку, был ли счет, который я предсказывал, правильным (я не имел своего собственного счетчика, и не испытывал желание писать его: -).

8. Из-за человеческого фактора всего процесса, я не могу убедиться, что получил самые лучшие результаты, которые могли бы быть получены этим методом - я мог легко пропустить кое-что. Например, я был 2 в топе при N = 15 и 1 при N = 16.

9. Фактически я всегда нахожу самые большие N наиболее захватывающими, так что я реально заботился относительно N = 28, где я получил 219822:

[svb]

Здесь можно посмотреть рекордные квадраты конкурса Retaining Water.

[svb]

Теперь слово победителю:

Цитата:

From: "walter.trump"
Date: Mon Jun 14, 2010 3:31 pm
Subject: Удачливый победитель walter.trump


Гонка была очень очень плотной. И я был очень удачлив, найдя самый лучший результат для порядка 9 за один день до конца соревнования. Hermann Jurksch проделал большую работу.

До июня я не думал, что смогу настигнуть его.

В принципе я использовал метод, который Jarek описал в своем письме. Но очевидно мой набор различных водоемов не был исчерпывающим. Поэтому я пропустил несколько единиц воды для больших порядков (а именно, 52 для порядка 28). Но в отличие от Jarek я применил этот метод для всех порядков > 9.
Более детально (начиная с любых comination озер и водоемов):

1. Заполняем ячейки барьера озера самыми большими числами. Из этих чисел самые маленькие используем для ячеек барьера на краях. Насколько это возможно барьеры озера не должны использовать ячейки на краях квадрата.

2. Ячейки барьеров водоема заполняем самыми большими остающимися числами. Большие водоемы заполняем первыми.

3. Используем числа 1, 2, 3 и 4 для углов.

4. Заполняем некоторые промежутки на краях, чтобы сохранить некоторую воду в одиночных ячейках.

5. Пусть n - порядок квадрата. Если ячейки (2; 2), (n-1; 2), (2; n-1) и (n-1; n-1) еще не заполнены, то помещаем в них самые большие из оставшихся числел.

6. Заполняем пустые ячейки краев числами так, чтобы сумма чисел в каждом краю была бы магической.

7. Делаем то же самое для строк и столбцов, соседних с крайними.

8. Заполняем остающиеся числа в пустые ячейки беспорядочно. Эти все ячейки должны представлять воду.

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

10. Используем массив чисел для описания состояния каждой ячейки. То же самое состояние обозначает, что числа могут обмениваться без разрушения магичности строки или столбца.

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

12. Обмениваем числа для получения волшебных строк, но не используем чисел диагоналей.

13. Теперь обмениваем числа только внутри строк и пытаемся получить волшебные столбцы.

14. Если квадрат - не магический, то смешиваем водяные числа и идем к п.11.

В результате вы находите новое решение.

Метод работает лучше для более высоких порядков. Но его можно применить даже для порядка 6. В этом случае он выполняется ужасно. Но он помогает находить подходящие формы воды. Я использовал backtracking алгоритмы для создания магических квадратов с заданной формой воды.

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

Методы Hermann Jurksch и Hugo Pfoertner были намного более успешными.

Walter

[Pavlovsky]

Интересная получилась картина. Большие МК все строили примерно по одинаковому алгоритму! Победил тот кто смог найти наиболее оптимальную структуру водоемов. Интересно, а как строили победители маленькие МК?

[Nataly-Mak]

Лучшие квадраты порядков 9 и 7 показаны наглядно на форуме Портала ЕН.

[Nataly-Mak]

Представляю наглядно МК 8-го порядка. На картинке первым показан наш квадрат (автор malk, участник форума Портала ЕН, член нашей команды), ёмкость квадрата 686 л. Вторым показан один из лучших квадратов конкурса, ёмкость 797 л.



В обоих квадратах есть два больших водоёма и микроводоёмы. В квадрате с конкурса количество микроводоёмов больше, чем в нашем квадрате, засчёт чего он и выиграл. По двум большим водоёмам ёмкости квадратов примерно одинаковы: 648 л и 673 л. В нашем квадрате всего один микроводоём, что добавляет 38 л. В квадрате с конкурса 4 микроводоёма, что добавляет 124 л.

[Pavlovsky]

Есть еще один дефект у первого квадрата. Сумма чисел в углах квадрата должна быть минимально возможной. Начиная с МК порядка 10 появляется возможность в углы поставить минимально возможные числа 1,2,3,4.
Сумма в углах первого квдрата равна 80. Сумма в углах второго квадрата равна 30. Только на этом было проиграно 50л воды!

-- Сб июн 19, 2010 10:51:39 --

Еще в первом квадрате нерационально построен самый большой водоем. На водоем площадью 14 клеток потребовалось 16 клеток границы, с самой нижней точкой границы 49.
Во втором квадрате на водоем площадью 15 клеток потребовалось 13 клеток границы, с самой нижней точкой границы 52. На этом было потеряно как минимум 3*14=42л воды.

[Nataly-Mak]

Однако предлагаю вернуться к нетрадиционным пандиагональным квадратам 8-го порядка из произвольных натуральных чисел, из простых чисел и из чисел Смита.
Я здесь уже привела один пример построения такого квдарата из произвольных натуральных чисел. Квадрат строится из чисел 8 арифметических прогрессий длины 8, удовлетворяющих определённым условиям. Примитивный квадрат из этих чисел составляется. Таким образом, примитивный квадрат превращается в пандиагональный в данном конкретном примере.

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

Pavlovsky, maxal, svb, какие у вас есть соображения по этому вопросу?
Что по этому поводу говорится в статье Россера? Я всё ещё никак не доберусь до её изучения.

P.S. Можно ли найти 8 арифметических прогрессий длины 8 (с одинаковой разностью), удовлетворяющих указанным условиям, из простых чисел и из чисел Смита? Если удастся, тогда можно построить частные примеры пандиагональных квадратов 8-го порядка из простых чисел и из смитов. В данный момент не имею ни одного примера таких квадратов.

[Pavlovsky]

Для построения пандиагональных МК 8х8 можно воспользоваться теоремой 2.4 (Россер).
То есть надо построить 4 пандиагональных МК 4х4, состоящих из разных простых чисел с одинаковой магической суммой. Из них легко собирается пандиагональный МК 8х8.

[Nataly-Mak]

Pavlovsky
Не поняла, о какой теореме В статье Россера идёт речь. Просмотрела статью бегло. Нашла только одну похожую теорему:

Цитата:

Теорема 2.4. d. s чётного порядка допускает L(2).

Эта теорема?
Но я пока в ней ничего не поняла. Что значит "допускает L(2)"?
Пыталась посмотреть предшествующие определения, но ничего не дошло.

Вы пишете, что из четырёх пандиагональных квадратов 4х4 с одинаковой магической константой легко составить пандиагональный квадрат 8х8.
У меня это легко не получается. Если просто записать 4 пандиагональных квадрата 4х4 в каждом квадранте квадрата 8х8, то квадрат 8х8 получится магическим, но не пандиагональным. Как сделать его пандиагональным?
Вот пример, взяла 4 классических пандиагональных квадрата и составила из них квадрат 8х8:

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

Очевидно, что такой составной квадрат не является пандиагональным.
Как же составить пандиагональный квадрат 8х8 из четырёх пандиаглнальных квадратов 4х4?

[Nataly-Mak]

Кажется, я нашла схему построения пандиагональных квадратов порядка $n=4m$. Это теорема 5.5.
Вот что у меня получилось для классического пандиагонального квадрата 8-го порядка:

примитивный квадрат

1 2 3 4 8 7 6 5
9 10 11 12 16 15 14 13
17 18 19 20 24 23 22 21
25 26 27 28 32 31 30 29
57 58 59 60 64 63 62 61
49 50 51 52 56 55 54 53
41 42 43 44 48 47 46 45
33 34 35 36 40 39 38 37

пандиагональный квадрат, полученный из этого примитивного квадрата с помощью преобразования A(i,j) = B(2i-j,-3i+2j)

24 30 57 51 48 38 1 11
61 50 44 39 5 10 20 31
43 40 6 9 19 32 62 49
7 13 18 28 63 53 42 36
17 27 64 54 41 35 8 14
60 55 45 34 4 15 21 26
46 33 3 16 22 25 59 56 
2 12 23 29 58 52 47 37

Итак, с классическим пандиагональным квадратом всё ясно.
Представим примитивный квадрат в таком виде:

a  b  c  d  e  f  g  h
i  .  .  .  .  .  .  .
j  .  .  .  .  .  .  .
k .  .  .  .  .  .  .
l  .  .  .  .  .  .  .
m  .  .  .  .  .  .  .
n  .  .  .  .  .  .  .
p  .  .  .  .  .  .  .

В приведённом примитивном квадрате выполняются следующие условия:
a+e=b+f=c+g=d+h
a+l=i+m=j+n=k+p

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

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

[Nataly-Mak]

Для нетрадиционного пандиагонального квадрата 8-го порядка, составленного из произвольных натуральных чисел, всё получилось по представленной выше схеме.
Выбрала произвольно натуральные числа $a,b,c,d,e,f,g,h,i,j,k,l,m,n,p$, удовлетворяющие указанным условиям. Далее достроила примитивный квадрат по правилам его построения:

3 5 7 11 17 15 13 9
8 10 12 16 22 20 18 14
10 12 14 18 24 22 20 16
12 14 16 20 26 24 22 18
23 25 27 31 37 35 33 29
18 20 22 26 32 30 28 24
16 18 20 24 30 28 26 22
14 16 18 22 28 26 24 20

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

Применяю к этому примитивному квадрату преобразование B(2i-j,-3i+2j)=A(i,j) и получаю следующий пандиагональный квадрат:

24 22 23 22 30 24 3 12
29 20 24 26 9 10 18 24
20 28 13 8 14 26 33 18
15 14 12 20 35 24 18 22
10 16 37 28 16 18 17 18
31 30 22 16 11 20 16 14
26 14 7 22 20 12 27 32
5 16 22 18 25 26 28 20

В преобразовании A(i,j) - элементы примитивного квадрата, B(i,j) - элементы пандиагонального квадрата.

Напомню, что схема работает для любого порядка $n=4m$ (так написано в Теореме 5.5).

Итак, дело за примитивным квадратом 8х8 из простых чисел и из смитов. Трудно ли будет найти примитивный квадрат, удовлетворяющий указанным условиям?

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

P.S. Как я поняла, существование примитивного квадрата, обладающего указанным свойством, является необходимым и достаточным условием для построения пандиагонального квадрата с помощью указанного преобразования.
Правильно поняла?

[Nataly-Mak]

Показываю работу описанный схемы для классического пандиагонального МК 12-го порядка ($n = 4m$, $m = 3$).

Примитивный квадрат:

1 2 3 4 5 6 12 11 10 9 8 7
13 14 15 16 17 18 24 23 22 21 20 19
25 26 27 28 29 30 36 35 34 33 32 31
37 38 39 40 41 42 48 47 46 45 44 43
49 50 51 52 53 54 60 59 58 57 56 55
61 62 63 64 65 66 72 71 70 69 68 67
133 134 135 136 137 138 144 143 142 141 140 139
121 122 123 124 125 126 132 131 130 129 128 127
109 110 111 112 113 114 120 119 118 117 116 115
97 98 99 100 101 102 108 107 106 105 104 103
85 86 87 88 89 90 96 95 94 93 92 91
73 74 75 76 77 78 84 83 82 81 80 79

Пандиагональный квадрат:

29 48 58 68 133 123 113 108 94 80 1 15
59 69 139 122 112 102 95 81 7 14 28 42
140 121 111 101 96 82 8 13 27 41 60 70
110 100 90 83 9 19 26 40 54 71 141 127
89 84 10 20 25 39 53 72 142 128 109 99
11 21 31 38 52 66 143 129 115 98 88 78
32 37 51 65 144 130 116 97 87 77 12 22
50 64 138 131 117 103 86 76 6 23 33 43
137 132 118 104 85 75 5 24 34 44 49 63
119 105 91 74 4 18 35 45 55 62 136 126
92 73 3 17 36 46 56 61 135 125 120 106
2 16 30 47 57 67 134 124 114 107 93 79

А далее в теореме 5.5 рассматривается случай построения пандиагональных квадратов порядков $n = 3m$, $m$ - нечётно, $m >=3$.
То есть прямо переходим к построению пандиагонального квадрата 9-го порядка.
Сейчас попробую разобраться.

svb
очень большое вам спасибо за перевод статьи Россера. Раньше я и нос в неё боялась совать. Сколько она у меня пролежала без дела!

-- Вс июн 20, 2010 09:11:15 --

Однако, вспомнила, что у меня есть две статьи, посвящённые построению классических идеальных квадратов из обратимых квадратов:
http://www.klassikpoez/narod.ru/obratid.htm для квадратов нечётных порядков
http://www.klassikpoez.narod.ru/obratid1.htm для квадратов порядков $n=4k$, $k>=2$.

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

В статье Россера строятся пандиагональные квадраты, а в моих статьях строятся квадраты, являющиеся одновременно пандиагональными и ассоциативными (то есть - идеальными).

Вот пример для идеального МК 8-го порядка. Берём самый простой обратимый квадрат (в таком квадрате числа записаны в естественном порядке) и применяем к нему матричное преобразование, приведённое в указанной выше статье (вторая ссылка). Получаем следующий идеальный квадрат:

1 32 41 56 49 48 25 8
63 34 23 10 15 18 39 58
4 29 44 53 52 45 28 5
62 35 22 11 14 19 38 59
6 27 46 51 54 43 30 3
60 37 20 13 12 21 36 61
7 26 47 50 55 42 31 2
57 40 17 16 9 24 33 64

Но вот будет ли работать мой метод для нетрадиционных идеальных квадратов? А почему нет? Сейчас попробую.

[Nataly-Mak]

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

Значит, это годится только для построения классических идеальных квадратов.