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

[Nataly-Mak]

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

[whitefox]

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

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

Это все возможные типы покрытий. Теперь нужно рассмотреть какие из них могут быть ортогональны друг другу.

[Nataly-Mak]

Ну, это только вы можете рассмотреть.
У меня на это мозгов не хватает

[whitefox]

Ну у Вас же есть программа которая для известного точного покрытия находит ортогональное. Здесь всё тоже самое только проще.

[Nataly-Mak]

У меня программа тупо находит к данному покрытию ортогональное.
А в ваших типах ещё разобраться надо

[Nataly-Mak]

Мысли вслух...
всего шаблонов 6814416. Если есть 16 симметрий, то не эквивалентных шаблонов 425901.
Каждому шаблону теоретически соответствует идеальный квадрат, а значит, комплект из 4-х точных попарно ортогональных покрытий. Следовательно, всего будет 425901 типов таких комплектов.

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

[whitefox]

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

[Nataly-Mak]

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

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

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

#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

#2
1 3 3 3 3 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 3 4 4 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 3 3 3 3 3 4
1 1 1 1 3 3 3 3 3
1 3 3 3 3 4 4 4 4

#3
1 1 3 3 3 3 3 3 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 1 1 3 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 4 4 4 4 4 4

#4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4

Задача
найти реальный(е) комплект(ы) попарно ортогональных покрытий по приведённой модели (массив реальных чисел приведён выше, см. стартовый пост).

Данная модель покрытий соответствует реальному решению с $S=12249$ с дырками (то есть не все элементы в решении принадлежат заданному массиву).

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

[Nataly-Mak]

Найти реальное точное покрытие, соответствующее этому шаблону,

#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

просто. Таких покрытий будет очень много.
Например, возьмём решение с дырками, из которого получена модель комплекта из 4-х покрытий:

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

$K=2722$, $S=12249$
Заменим неправильные комплементарные пары (431,2291) и (1019,1703) на правильные пары соответственно - (641,2081) и (1619,1103). И нужное реальное покрытие готово.

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

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

[whitefox]

Вместо шаблонов точных покрытий можно взять шаблон квадрата. И постараться так назначить свободные переменные, чтобы десять из них были единицами, а троек и четвёрок было поровну (это обеспечит минимум вариантов для перебора). Тогда только для проверки одного этого шаблона потребуется проверить около $3{,}9\cdot10^{29}$ вариантов.

[Nataly-Mak]

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

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

Это я уже проходила. Было написано несколько программ по различным шаблонам (из вычетов по разным модулям).
Более того, в начале этой темы я показала, как можно "посадить" квадрат на 4 центральные цепочки; для этого была получена альтернативная общая формула идеального квадрата 9-го порядка. Увы! Это тоже не дало результатов.
Именно поэтому решила прибегнуть к поиску комплектов из 4-х точных попарно ортогональных покрытий массива.

Цитата:

Тогда только для проверки одного этого шаблона потребуется проверить около $3,9 \cdot 10^{29}$ вариантов.

Совсем немножко

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

[Nataly-Mak]

Уф! Что-то у меня сегодня программа не сразу получилась. А всё потому, что лень было писать заново и стала изменять старую программу, приспосабливая её к поиску по шаблону. Ну и вот: сколько раз убеждалась, что лучше написать программу с чистого листа, чем вносить изменения в старую программу.

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

#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

#2
1 3 3 3 3 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 3 4 4 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 3 3 3 3 3 4
1 1 1 1 3 3 3 3 3
1 3 3 3 3 4 4 4 4

Решение (показываю оба покрытия):

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

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

Надеюсь, что теперь всё правильно, тщательно не проверяла.

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

[Nataly-Mak]

Ассоциативный квадрат

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

$K=2722$, $S=12249$

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

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

#3
1 1 3 3 3 3 3 3 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 1 1 3 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 4 4 4 4 4 4

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

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

[Nataly-Mak]

Ну вот и всё: данный вариант проверен полностью - третье покрытие не найдено (если не ошиблась в программе).
Но это только один вариант (одно первое точное покрытие --> одно второе точное покрытие --> третье точное покрытие; попарно ортогональные). А таких вариантов будет достаточно много.

Вывод: поиск комплекта покрытий по модели выполняется значительно быстрее и выполнить проверку модели комплекта можно за приемлемое время.

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

[Nataly-Mak]

Решила протестировать программу поиска третьего покрытия.

Ввожу два первых точных покрытия, полученных из решения с дырками:

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

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

Эти реальные покрытия соответствуют тестируемой модели комплекта.
Программа выполняется полностью (полный перебор!) и выдаёт несколько эквивалентных третьих покрытий, то есть фактически всего одно:

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

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