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

[Nataly-Mak]

Да-а-а-а... с базой всех цепочек дело совсем плохо. Моя программа затрудняется даже все их посчитать, ждала минут 20, не дождалась результата.

Вывела первые 10 цепочек, 100000-ую и 200000-ую цепочки (с симметричными им):

11  23  29  59  1811  2531  2543  2609  2633 
2711  2699  2693  2663  911  191  179  113  89 

11  23  29  59  1811  2543  2549  2591  2633 
2711  2699  2693  2663  911  179  173  131  89 

11  23  29  59  1901  2441  2531  2621  2633 
2711  2699  2693  2663  821  281  191  101  89 

11  23  29  59  1901  2441  2543  2609  2633 
2711  2699  2693  2663  821  281  179  113  89 

11  23  29  59  1901  2459  2543  2591  2633 
2711  2699  2693  2663  821  263  179  131  89 

11  23  29  59  1913  2411  2549  2621  2633 
2711  2699  2693  2663  809  311  173  101  89 

11  23  29  59  1913  2441  2531  2609  2633 
2711  2699  2693  2663  809  281  191  113  89 

11  23  29  59  1913  2441  2543  2609  2621 
2711  2699  2693  2663  809  281  179  113  101 

11  23  29  59  1913  2441  2549  2591  2633 
2711  2699  2693  2663  809  281  173  131  89 

11  23  29  59  1913  2459  2531  2591  2633 
2711  2699  2693  2663  809  263  191  131  89
. . . . . . . . . 
11  23  101  1151  1439  2063  2339  2459  2663 
2711  2699  2621  1571  1283  659  383  263  59 
. . . . . . . . .
11  23  179  509  1559  2333  2441  2531  2663 
2711  2699  2543  2213  1163  389  281  191  59
. . . . . . . . .

В общем, база цепочек будет огромная и работать с ней я не смогу.

Можно попытаться получить комплект из 4-х точных попарно ортогональных покрытий массива, используя случайную генерацию первого точного покрытия.

[Nataly-Mak]

Если моя программа не врёт, это 500000-ая цепочка (и симметричная ей):

V= 500000 
11  23  509  911  1229  2273  2333  2411  2549 
2711  2699  2213  1811  1493  449  389  311  173 

Ну, это ещё быстро считается - примерно минута.

Цепочек действительно будет очень много. Так сколько же "много" - десятки миллионов, сотни миллионов, миллиарды
Кто-нибудь может быстро посчитать?

-- Пт июн 26, 2015 12:30:11 --

Миллионная цепочка (и симметричная ей):

V= 1000000 
11  29  131  1163  1493  1901  2273  2549  2699 
2711  2693  2591  1559  1229  821  449  173  23

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

-- Пт июн 26, 2015 12:40:56 --

Трёхмиллионная цепочка нашлась за 7 минут:

V= 3000000 
11  89  509  1103  1289  2039  2243  2273  2693 
2711  2633  2213  1619  1433  683  479  449  29

-- Пт июн 26, 2015 13:12:53 --

Обалдеть! Посчитала все цепочки, начинающиеся с первого числа массива - 11, их оказалось 13144018.

Так, ладно, беру самую первую цепочку (с симметричной):

11  23  29  59  1811  2531  2543  2609  2633 
2711  2699  2693  2663  911  191  179  113  89 

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

[Nataly-Mak]

Вторая пара цепочек:

101  131  173  263  2153  2243  2333  2411  2441 
2621  2591  2549  2459  569  479  389  311  281

третья пара цепочек:

383  449  509  653  1979  2003  2063  2081  2129 
2339  2273  2213  2069  743  719  659  641  593

четвёртая пара цепочек:

683  773  1013  1163  1571  1613  1619  1901  1913 
2039  1949  1709  1559  1151  1109  1103  821  809

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

1223  1229  1283  1289  1433  1439  1493  1499 

Итак, мы получили первое точное покрытие массива (цепочки-строки):

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

Методика чёткая и абсолютно прозрачная.

Теперь для этого точного покрытия массива надо найти ортогональное покрытие (цепочки-столбцы).
Эти два покрытия должны дать ассоциативный квадрат, если, конечно, второе покрытие найдётся.

[Nataly-Mak]

Очень трудно дело продвигается
Написала программу поиска второго точного покрытия ортогонального заданному точному покрытию.
Для того покрытия, что приведено в предыдущем посте, программа долго ничего не выдаёт.

Тогда тестирую. Беру в качестве первого точного покрытия это (цепочки-строки из известного ассоциативного квадрата):

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

Ввожу его в программу и ищу второе точное покрытие ортогональное данному.
Если начинать с нуля, программа опять же очень долго ничего не выдаёт. Тогда искусственно задаю параметры циклов так, что первые три пары цепочек выдаются, как в известном решении (во втором покрытии).
Для четвёртой пары цепочек циклы все проходятся естественным образом. И программа выдаёт 8 вторых точных покрытий:

(Оффтоп)

#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 

#6
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 

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

#7
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 

281  449  641  659  1619  1901  2153  2213  2333 
2441  2273  2081  2063  1103  821  569  509  389 

#8
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 

389  509  569  821  1103  2063  2081  2273  2441 
2333  2213  2153  1901  1619  659  641  449  281

Известное решение здесь #4.
Можно проверить, соответствует ли каждой паре точных ортогональных покрытий ассоциативный квадрат. По идее должен соответствовать (если программа не врёт).

Итак, программа поиска второго точного покрытия ортогонального заданному первому работает, но... очень долго.
Теперь можно делать программу поиска третьего точного покрытия ортогонального двум заданным точным ортогональным покрытиям.
Однако такое примитивное решение задачи по кусочкам вряд ли поможет решить задачу. Нужна полная программа, которая будет "брать" всю задачу, а не отдельные её куски.

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

Я не осиливаю её решить

[Nataly-Mak]

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

Можно проверить, соответствует ли каждой паре точных ортогональных покрытий ассоциативный квадрат. По идее должен соответствовать (если программа не врёт).

Проверила. Да, всё получается!

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

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

Это второе точное покрытие (цепочки-столбцы), ортогональное данному; найдено программой, выведено под #1 (см. выше):

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

По этим двум точным ортогональным покрытиям строю вручную ассоциативный квадрат, очень легко строится!

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

$K=2722$, $S=12249$

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

[Nataly-Mak]

Всё-таки продолжаю...
Пытаюсь выполнить третий шаг: по двум заданным точным ортогональным покрытиям найти третье точное покрытие ортогональное каждому из двух заданных.

Первое точное покрытие:

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

Второе точное покрытие:

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

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

11  29  1013  1163  1439  1499  2063  2441  2591 
2711  2693  1709  1559  1283  1223  659  281  131 

23  59  89  1229  1433  2129  2213  2531  2543 
2699  2663  2633  1493  1289  593  509  191  179 

Отсалось найти ещё две пары цепочек.

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

[Nataly-Mak]

Три пары цепочек тоже быстро нашлись:

11  29  1013  1163  1439  1499  2063  2441  2591 
2711  2693  1709  1559  1283  1223  659  281  131 

23  59  89  1229  1433  2129  2213  2531  2543 
2699  2663  2633  1493  1289  593  509  191  179 

113  173  389  641  1901  2039  2243  2339  2411 
2609  2549  2333  2081  821  683  479  383  311

А на четвёртой паре программа надолго задумалась. Вот уже около часа думает.
Возможные исходы экперимента: или найдёт четвёртую пару, или выполнит полный перебор и не найдёт, или прерву, если будет очень долго.
Ещё часок подожду.

[Nataly-Mak]

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

По этим двум точным ортогональным покрытиям строю вручную ассоциативный квадрат, очень легко строится!

Пока программа думает, я тоже думаю

Вот о чём: можно написать программку, которая будет строить по двум точным ортогональным покрытиям ассоциативный квадрат. Это должна быть простая программка. Ведь вручную всё делается так просто! Процедура очень занятная
Попробуйте! Правда, очень занимательно. Главное - успех всегда обеспечен!
И программка должна быть красивая.
Кто готов написать красивую программку?

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

[Nataly-Mak]

Всё, прервала. Больше не хватило терпения ждать. Почти 8 часов работала программа. Нет третьего покрытия!

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

[Nataly-Mak]

Итак, тест.

Массив чисел:

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

Первое точное покрытие:

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

Второе точное покрытие:

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

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

(Оффтоп)

#1
11  179  1013  1283  1493  1811  2063  2153  2243 
2711  2543  1709  1439  1229  911  659  569  479 

23  89  131  1559  1883  1949  2003  2201  2411 
2699  2633  2591  1163  839  773  719  521  311 

29  263  383  1499  1613  2039  2081  2129  2213 
2693  2459  2339  1223  1109  683  641  593  509 

59  101  389  743  1289  2069  2441  2549  2609 
2663  2621  2333  1979  1433  653  281  173  113 

#2
11  179  1013  1283  1493  1811  2063  2153  2243 
2711  2543  1709  1439  1229  911  659  569  479 

23  89  131  1559  1883  1949  2003  2201  2411 
2699  2633  2591  1163  839  773  719  521  311 

29  263  383  1499  1613  2039  2081  2129  2213 
2693  2459  2339  1223  1109  683  641  593  509 

113  173  281  653  1433  1979  2333  2621  2663 
2609  2549  2441  2069  1289  743  389  101  59 

#3
11  179  1013  1283  1493  1811  2063  2153  2243 
2711  2543  1709  1439  1229  911  659  569  479 

23  89  131  1559  1883  1949  2003  2201  2411 
2699  2633  2591  1163  839  773  719  521  311 

59  101  389  743  1289  2069  2441  2549  2609 
2663  2621  2333  1979  1433  653  281  173  113 

509  593  641  683  1109  1223  2339  2459  2693 
2213  2129  2081  2039  1613  1499  383  263  29 

#4
11  179  1013  1283  1493  1811  2063  2153  2243 
2711  2543  1709  1439  1229  911  659  569  479 

23  89  131  1559  1883  1949  2003  2201  2411 
2699  2633  2591  1163  839  773  719  521  311 

113  173  281  653  1433  1979  2333  2621  2663 
2609  2549  2441  2069  1289  743  389  101  59 

509  593  641  683  1109  1223  2339  2459  2693 
2213  2129  2081  2039  1613  1499  383  263  29

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

[Nataly-Mak]

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

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

[Nataly-Mak]

Не нашла нового (не эквивалентного) четвёртого покрытия. Полный перебор, конечно, не выполнила, потому что очень долго.
Увы, пока нет ничего нового.

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

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

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

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

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

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

Если смотреть на известное решение:

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

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

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

Необходимо написать процедуру проверки комплекта из 4-х точных попарно ортогональных покрытий массива на предмет составления идеального квадрата. Иначе даже если мы получим такой комплект для искомого минимального решения с магической константой $S=12249$, нам нечем будет его проверить.

Всё. Остались сплошные тупики

-- Пн июн 29, 2015 10:06:11 --

Посмотрела вторые покрытия (приведённые выше).
Вот это точно не эквивалентно известному второму покрытию:

#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

Попробую ввести в программу известное первое, приведённое второе и поискать третье покрытие.

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

[Nataly-Mak]

Для вторых покрытий #1, #2 не нашла третье покрытие. Крутила программу несколько часов, полный перебор не выполнила. Три пары цепочек находятся в обоих случаях очень быстро, на четвёртой паре всё застревает.

У меня такое подозрение, что комплектов из 4-х точных попарно ортогональных покрытий заданного массива (для минимального квадрата 9-го порядка из различных простых чисел) будет мало, если они вообще существуют.

[whitefox]

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

В самом деле, для данной пары точных ортогональный покрытий существует всего 192 магических ассоциативных квадрата с точностью до изоморфизма. Каждому из них соответствует 192 магических ассоциативных квадратов с точностью до поворотов и осевой симметрии. Всего получается $192^2=36\ 864$ варианта. Если для данной пары точных покрытий существует идеальный квадрат, то он совпадёт с одним из указанных вариантов (с точностью до поворота и осевой симметрии).

Алгоритм такой:

1. по данной паре точных ортогональных покрытий строим ассоциативный магический квадрат;
2. применяем к этому квадрату преобразования подобные М-преобразованиям магических квадратов, за тем исключением, что они действуют только на строки, оставляя столбцы на месте (таких преобразований 384, но с учётом симметрии остаётся 192, все полученные квадраты будут существенно различными магическими ассоциативными квадратами);
3. к каждому квадрату, полученному не предыдущем шаге, применяем М-преобразования (коих тоже 384, но с учётом симметрии остаётся 192, и все полученные квадраты будут магическими и ассоциативными);
4. каждый квадрат, полученный на предыдущем шаге, проверяем на пандиагональность (достаточно проверить четыре прямых и четыре обратных ломаных диагонали), если проверка успешна, то идеальный квадрат получен, а вместе с ним и четвёрка точных покрытий попарно ортогональных друг другу.

Алгоритм потребует выполнения порядка 3 миллионов арифметических операций (с точность до умножения на константу, полагаю, не больше 100).

[Nataly-Mak]

whitefox в сообщении #1032357 писал(а):

В самом деле, для данной пары точных ортогональный покрытий существует всего 192 магических ассоциативных квадрата с точностью до изоморфизма.

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

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

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