Метод точных ортогональных покрытий массива

Форум для обсуждения вопросов математики

Модератор: Admin

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Метод точных ортогональных покрытий массива

Сообщение omega » Вс июн 28, 2015 12:00 am

Здравствуйте, уважаемые форумчане!

Сейчас тружусь над методом точных ортогональных покрытий массива. Метод применяется для построения ассоциативных и пандиагональных магических квадратов.

Мне удалось блестяще применить метод к построению ассоциативных квадратов из простых чисел. Построила этим методом ассоциативные квадраты из простых чисел до порядка 16 включительно
(см. https://oeis.org/A188537).

А теперь хочу попробовать этот метод применительно к построению идеальных квадратов 9-го порядка.

Сначала дам необходимые определения:

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

Определение 2. Цепочка называется нормализованной, если числа в ней расположены в порядке возрастания.

Теперь пусть задан массив, состоящий из 81 простого числа:

Код: Выделить всё

11 23 29 59 89 101 113 131 173 179 191 263 281 311 383 389 449 479 509 569 593 641 653 659 683 719
743 773 809 821 911 1013 1103 1109 1151 1163 1223 1229 1283 1289 1361 1433 1439 1493 1499 1559 1571
1613 1619 1709 1811 1901 1913 1949 1979 2003 2039 2063 2069 2081 2129 2153 2213 2243 2273 2333 2339
2411 2441 2459 2531 2543 2549 2591 2609 2621 2633 2663 2693 2699 2711

Будем рассматривать ассоциативный магический квадрат 9-го порядка, который мы хотим составить из чисел заданного массива.

Определение 3. Точным покрытием массива, состоящего из 81 чисел, называется набор из 9 цепочек таких, что они составлены из чисел данного массива и ни в каких двух цепочках нет одинаковых чисел.

Понятно, что точное покрытие как бы “покрывает” заданный массив, используя все числа массива.

Определение 4. Два точных покрытия массива называются ортогональными, если каждая цепочка первого покрытия имеет точно один общий элемент с каждой цепочкой второго покрытия.

Очевидно, что из пары точных ортогональных покрытий всегда можно построить полумагический квадрат.
А вот магический квадрат не из любой пары точных ортогональных покрытий можно построить.
В случае с ассоциативным квадратом всё проще. В нём суммы в главных диагоналях получаются автоматически (из-за свойства ассоциативности).

Покажу, как метод работает при построении ассоциативного квадрата 9-го порядка из чисел заданного массива.

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

Код: Выделить всё

1289 2213 2039 1163 1571 311 1283 1811 569
383 2243 1619 2693 2063 593 773 653 1229
2003 1499 641 1979 821 809 89 1709 2699
131 263 1613 173 2333 2531 2441 2663 101
11 113 179 449 1361 2273 2543 2609 2711
2621 59 281 191 389 2549 1109 2459 2591
23 1013 2633 1913 1901 743 2081 1223 719
1493 2069 1949 2129 659 29 1103 479 2339
2153 911 1439 2411 1151 1559 683 509 1433

Это цепочки-строки. Генерируется такое покрытие в данном примере мгновенно
(замечу, что цепочки-строки генерируются так, что выполняется свойство ассоциативности будущего квадрата).

Второй этап – получение цепочек-столбцов. Здесь это делается так: переставляем числа в строках до тех пор, пока не получим нужные суммы в столбцах. Этот этап иногда буксует, но, в конце концов, выполняется, если ассоциативный квадрат существует.

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

И вот готовый ассоциативный квадрат 9-го порядка из чисел заданного массива (кстати, минимальный из различных простых чисел):

Код: Выделить всё

1283 311 1811 2213 1571 569 2039 1163 1289
773 653 2243 1619 2063 593 2693 383 1229
1979 1499 2699 641 821 89 809 2003 1709
1613 2531 101 131 2333 2441 2663 263 173
113 179 2711 449 1361 2273 11 2543 2609
2549 2459 59 281 389 2591 2621 191 1109
1013 719 1913 2633 1901 2081 23 1223 743
1493 2339 29 2129 659 1103 479 2069 1949
1433 1559 683 2153 1151 509 911 2411 1439

K=2722, S=12249

Это, собственно, и есть второе точное покрытие массива (цепочки-столбцы) ортогональное первому точному покрытию.
Как видите, тут всё очень хорошо работает.

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

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

Далее, вот мы, предположим, нашли 4 точных попарно ортогональных покрытия массива.
Теперь будет нужен точный алгоритм проверки этого комплекта на возможность построения из него идеального квадрата. Как быстро проверить?

Это вводная часть. Всё ли понятно?

Тема на форуме dxdy.ru
http://dxdy.ru/topic98397.html

Там уже много написано по теме. Кто заинтересуется, милости прошу. Отвечать, спрашивать можно и там, и тут.

С определениями по магическим квадратам можно познакомиться в Википедии.

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Вс июн 28, 2015 10:09 am

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

Это первое точное покрытие из известного ассоциативного квадрата (цепочки-строки):

Код: Выделить всё

1289 2213 2039 1163 1571 311 1283 1811 569
383 2243 1619 2693 2063 593 773 653 1229
2003 1499 641 1979 821 809 89 1709 2699
131 263 1613 173 2333 2531 2441 2663 101
11 113 179 449 1361 2273 2543 2609 2711
2621 59 281 191 389 2549 1109 2459 2591
23 1013 2633 1913 1901 743 2081 1223 719
1493 2069 1949 2129 659 29 1103 479 2339
2153 911 1439 2411 1151 1559 683 509 1433


Это оно же с нормализованными цепочками:

Код: Выделить всё

311 569 1163 1283 1289 1571 1811 2039 2213
383 593 653 773 1229 1619 2063 2243 2693
89 641 809 821 1499 1709 1979 2003 2699
101 131 173 263 1613 2333 2441 2531 2663
11 113 179 449 1361 2273 2543 2609 2711
59 191 281 389 1109 2459 2549 2591 2621
23 719 743 1013 1223 1901 1913 2081 2633
29 479 659 1103 1493 1949 2069 2129 2339
509 683 911 1151 1433 1439 1559 2153 2411


Написала программку, которая находит по заданному точному покрытию второе точное покрытие ортогональное заданному.
Приведу несколько вторых покрытий, найденных программой:

Код: Выделить всё

#1
113  773  1013  1283  1433  1493  1613  1979  2549
2609  1949  1709  1439  1289  1229  1109  743  173

179  311  653  719  1499  1559  2339  2459  2531
2543  2411  2069  2003  1223  1163  383  263  191

29  59  101  683  1811  1913  2243  2699  2711
2693  2663  2621  2039  911  809  479  23  11

89  389  593  659  1571  2081  2153  2273  2441
2633  2333  2129  2063  1151  641  569  449  281

#2
113  773  1013  1283  1433  1493  1613  1979  2549
2609  1949  1709  1439  1289  1229  1109  743  173

179  311  653  719  1499  1559  2339  2459  2531
2543  2411  2069  2003  1223  1163  383  263  191

29  59  101  683  1811  1913  2243  2699  2711
2693  2663  2621  2039  911  809  479  23  11

89  449  569  1103  1151  1901  2063  2333  2591
2633  2273  2153  1619  1571  821  659  389  131

 #3
113  773  1013  1283  1433  1493  1613  1979  2549
2609  1949  1709  1439  1289  1229  1109  743  173

179  311  653  719  1499  1559  2339  2459  2531
2543  2411  2069  2003  1223  1163  383  263  191

29  59  101  683  1811  1913  2243  2699  2711
2693  2663  2621  2039  911  809  479  23  11

89  509  569  593  1103  2081  2273  2441  2591
2633  2213  2153  2129  1619  641  449  281  131

#4
113  773  1013  1283  1433  1493  1613  1979  2549
2609  1949  1709  1439  1289  1229  1109  743  173

179  311  653  719  1499  1559  2339  2459  2531
2543  2411  2069  2003  1223  1163  383  263  191

29  59  101  683  1811  1913  2243  2699  2711
2693  2663  2621  2039  911  809  479  23  11

131  281  449  641  1619  2129  2153  2213  2633
2591  2441  2273  2081  1103  593  569  509  89

#5
113  773  1013  1283  1433  1493  1613  1979  2549
2609  1949  1709  1439  1289  1229  1109  743  173

179  311  653  719  1499  1559  2339  2459  2531
2543  2411  2069  2003  1223  1163  383  263  191

29  59  101  683  1811  1913  2243  2699  2711
2693  2663  2621  2039  911  809  479  23  11

131  389  659  821  1571  1619  2153  2273  2633
2591  2333  2063  1901  1151  1103  569  449  89

Все варианты я даже и не нашла, так как программа выполняется очень долго.
В каждом покрытии вы видите 8 цепочек. Оставшиеся 9 чисел массива дают цепочку, содержащую центральный элемент – число 1361.

Итак, первый шаг выполнен: по заданному точному покрытию найдено второе точное покрытие ортогональное первому.

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