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

[Nataly-Mak]

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

#1
1 1 3 3 3 3 3
1 1 1 1 1 1 3
1 1 3 3 3 3 3
1 1 1 1 1 1 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3

13  17  7  71  223  227  239 
29  37  41  53  193  233  211
61  73  11  83  179  191  199 
89  97  101  109  113  137  151
149  157  19  43  127  139  163 
173  181  23  67  79  107  167 
197  229  31  47  59  103  131

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

[Nataly-Mak]

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

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

13 29 127 131 151 167 179
17 37 97 181 103 163 199
41 89 31 67 139 191 239
61 113 19 59 107 211 227
53 109 149 229 11 23 223
73 101 197 233 43 71 79
137 157 173 193 7 47 83

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

13 17 239 227 223 71 7
29 37 41 211 53 233 193
179 199 191 61 11 73 83
151 97 89 113 109 101 137
127 163 139 19 149 43 157
167 181 67 107 23 79 173
131 103 31 59 229 197 47

$S=797$

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

[Nataly-Mak]

Не нашлось третье покрытие. Результат вполне ожидаемый.
Удалось найти всего три цепочки в третьем покрытии:

#3
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 1 1 1 1 3
1 1 1 1 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3

13  109  47  79  139  199  211 
53  61  97  173  43  131  239 
17  41  73  113  157  229  167 
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

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

Предлагается такая схема:

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

Всё это надо, разумеется, делать в одной программе.
Кто поможет реализовать?

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

-- Пн июл 13, 2015 00:57:26 --

Посмотрите, какой интересный подход к решению задачи предложил whitefox:

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

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

Поэтому предлагаю следующий подход к созданию многопоточной программы:

1. программа должна иметь "генератор заданий", "диспетчер" и неограниченное количество "обработчиков";
2. каждый из этих элементов выполняется в отдельном потоке;
3. генератор заданий находит полумагические квадраты и помещает их в "очередь заданий";
4. диспетчер извлекает очередное задание из очереди и передаёт его очередному обработчику;
5. если "очередь обработчиков" пуста, то диспетчер создаёт нового обработчика и передаёт задание ему;
6. обработчик полным перебором проверяет возможность из данного полумагического квадрата построить пандиагональный магический квадрат;
7. когда обработчик завершает своё задание, он становится в очередь обработчиков.

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

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

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