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

[Nataly-Mak]

whitefox
когда обсуждали метод точных ортогональных покрытий для пандиагонального квадрата 7-го порядка, вы что-то писали об алгоритме танцующих связей (у Кнута). Этот алгоритм нам не поможет?

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

-- Вс июл 05, 2015 13:36:44 --

Например, по модулю 4 массив разбивается на следующие две группы:

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

А по модулю 5 - на следующие три группы:

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

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

[Nataly-Mak]

Вот один из шаблонов из вычетов по модулю 5:

4  1  4  4  4  3  4  1  4 
4  1  4  3  4  4  3  3  3 
1  4  1  1  3  1  3  1  4 
3  4  4  1  3  4  3  3  4 
4  4  1  4  1  3  1  3  3 
3  4  4  3  4  1  3  3  4 
3  1  4  1  4  1  1  3  1 
4  4  4  3  3  4  3  1  3 
3  1  3  4  3  3  3  1  3 

И уже есть типы цепочек.

[whitefox]

Типы цепочек должны удовлетворять следующим требованиям:

1. сумма всех элементов сравнима с 4 по модулю 5;
2. число троек сравнимо с числом четвёрок по модулю 5.

То есть возможны только следующие типы цепочек:

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 3 4
1 1 1 1 1 3 3 4 4
1 1 1 1 3 3 3 3 3
1 1 1 1 4 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 3 3 3 3 3 4
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
3 3 3 3 3 3 3 4 4
3 3 4 4 4 4 4 4 4

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

"Центральные" цепочки обязательно содержат единицу (центральный элемент) и одинаковое число троек и четвёрок. То есть центральными могут быть только цепочки следующих типов:

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 3 4
1 1 1 1 1 3 3 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4

[Nataly-Mak]

Цепочки такого вида

1 1 1 3 3 3 4 4 4

содержат центральный элемент (число 1361).
Ага, вы тоже добавили про цепочки, содержащие центральный элемент.
Верно. Я указала только один из видов.

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

[whitefox]

Можно перечислить все допустимые шаблоны если из не более чем 283 миллиардов возможных шаблонов (по одному для каждого из $3^{24}$ возможных значений свободных перемененных) отобрать только те, которые содержат ровно 21 единицу. Число последних можно ещё уменьшить если учесть, что идеальный квадрат нечётного порядка имеет 16 симметрий.

[Nataly-Mak]

Любой комбинации значений 24 свободных переменных из множества значений (1, 3, 4) обязательно будет соответствовать свой шаблон

[whitefox]

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

[Nataly-Mak]

Написала программку построения шаблонов из вычетов по модулю 5.
Если программа не врёт, это 500-ый шаблон:

 1  1  1  1  1  1  3  1  4 
 1  3  1  4  1  1  1  1  1 
 4  3  3  1  4  1  1  1  1 
 4  4  1  3  1  1  1  3  1 
 3  1  1  1  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0

(симметричные элементы не записывала)
Конечно, на изоморфизм не проверяла.
А всего шаблонов будет уйма. Моя программа даже затрудняется их все посчитать

-- Вс июл 05, 2015 17:58:20 --

А это 3000-ый шаблон:

 1  1  1  1  1  1  1  1  1 
 3  3  1  4  4  4  1  3  1 
 1  4  4  3  3  1  1  1  1 
 4  3  3  1  1  3  1  4  4 
 4  4  1  1  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0

[whitefox]

Эти шаблоны не являются допустимыми. Так как каждая единица симметрична единице, то в первом шаблоне будет 55 единиц, а во втором 45 единицы. Допустимы же только 21 единица, а если не учитывать симметричные элементы, то 11 единиц (одна из них центральная).

[Nataly-Mak]

Да, об этом я забыла
Искала все возможные шаблоны для идеального квадрата 9-го порядка (по общей формуле), составленные из элементов 1,3,4.
Надо же ещё привязаться к тому массиву, который мы имеем. Ну, тогда шаблонов будет гораздо меньше.

Сейчас попробую подкорректировать программу.

-- Вс июл 05, 2015 19:16:31 --

А такие годятся?

3  1  3  1  4  3  4  1  4 
 4  4  4  3  4  4  1  4  1 
 4  3  3  3  3  1  3  1  3 
 3  4  1  3  1  4  1  4  3 
 3  4  4  3  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 

 3  3  4  3  4  3  4  1  4 
 4  4  4  4  4  3  1  4  1 
 1  3  3  4  4  1  4  1  3 
 1  3  4  3  1  4  1  4  3 
 3  3  1  3  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 

 3  3  4  3  4  4  4  1  3 
 4  4  3  3  4  1  1  3  1 
 1  4  3  4  3  1  4  1  3 
 1  4  3  3  1  4  1  3  4 
 3  4  3  3  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 

Количество троек и четвёрок, наверное, не надо проверять? Должно автоматически обеспечиваться (?)

[whitefox]

Такие годятся

Тройки симметричны четвёркам, поэтому в полном шаблоне их будет поровну, то есть по 30.

[Nataly-Mak]

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

Тройки симметричны четвёркам, поэтому в полном шаблоне их будет поровну, то есть по 30.

Да, правильно.
Это 100-ый шаблон (изоморфные не выбрасывала):

 4  3  4  3  4  3  4  1  3 
 3  1  3  4  3  4  1  4  1 
 3  3  3  1  4  1  4  1  4 
 3  3  4  4  1  4  3  4  3 
 4  1  4  1  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 

-- Вс июл 05, 2015 20:18:36 --

Моя программа говорит, что шаблонов будет 6814416, считая все эквивалентные.
Не врёт?

[whitefox]

Всего имеется 60 типов точных покрытий:

9 — (5,1,0,0) (4,2,0,0) (4,1,1,0) (3,3,0,0) (3,2,1,0) (3,1,1,1) (2,2,2,0) (2,2,1,1)
7 — (7,0,0,0) (5,2,0,0) (5,1,1,0) (4,3,0,0) (4,2,1,0) (4,1,1,0) (3,3,1,0) (3,2,2,0) (3,2,1,1) (2,2,2,1)
5 — (7,1,0,0) (5,3,0,0) (5,2,1,0) (5,1,1,1) (4,4,0,0) (4,3,1,0) (4,2,2,0) (4,2,1,1) (3,3,2,0) (3,3,1,1) (3,2,2,1) (2,2,2,2)
3 — (9,0,0,0) (7,2,0,0) (7,1,1,0) (5,4,0,0) (5,3,1,0) (5,2,2,0) (5,2,1,1) (4,4,1,0) (4,3,2,0) (4,3,1,1) (4,2,2,1) (3,3,3,0) (3,3,2,1) (3,2,2,2)
1 — (9,1,0,0) (7,3,0,0) (7,2,1,0) (7,1,1,1) (5,5,0,0) (5,4,1,0) (5,3,2,0) (5,3,1,1) (5,2,2,1) (4,4,2,0) (4,4,1,1) (4,3,3,0) (4,3,2,1) (4,2,2,2) (3,3,3,1) (3,3,2,2)

Здесь каждая цифра означает допустимую цепочку с соответствующим числом единиц, наименьшую в лексикографическом порядке. Цифра слева от тире — это центральная цепочка, а справа от тире перечислены возможные покрытия с этой центральной цепочкой. Комплементарные цепочки и центральная цепочка в коде покрытия опущены.

Например, код (5,1,0,0) означает следующий тип точного покрытия:

1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
3 3 3 3 3 3 3 4 4
3 3 3 3 3 3 3 4 4
1 1 1 1 1 1 1 1 1
3 3 4 4 4 4 4 4 4
3 3 4 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4

[Nataly-Mak]

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

Типы цепочек должны удовлетворять следующим требованиям:

1. сумма всех элементов сравнима с 4 по модулю 5;
2. число троек сравнимо с числом четвёрок по модулю 5.

То есть возможны только следующие типы цепочек:

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 3 4
1 1 3 3 3 3 3 3 4
1 1 3 4 4 4 4 4 4
1 1 1 1 1 3 3 4 4
3 3 3 3 3 3 3 4 4
3 3 4 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 1 1 1 1 1 1

годятся только на роль "центральных". Нет?

Ого! Вот уже и анализ покрытий готов.

[whitefox]

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

Моя программа говорит, что шаблонов будет 6814416, считая все эквивалентные.
Не врёт?

Похоже на правду.