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

[Nataly-Mak]

При данных этого примера быстро находятся 40 различных элементов (пара секунд):

23  37  313  277  223  157  131  79 
 139  241  0  59  0  41  0  229 
 0  0  181  103  0  0  0  11 
 0  0  31  7  0  0  269  127 
 197  43  199  211  397  163  17  13 
 0  379  0  101  61  179  0  271 
 0  0  0  409  0  0  19  317 
 0  0  151  73  0  0  389  193

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

[Nataly-Mak]

Прежде чем двигаться дальше по неизведанному пути, решила протестировать программу, написанную по общей формуле.
Для теста, конечно, взяла известное решение с магической константой 1584.
Разбиение хорошее в этом примере получается (отклонения 66 и 96; кстати, в статье опечатка - написано, что отклонение p1 равно 60; должно быть 66).
Отклонение 66 даёт 28 пар чисел, отклонение -66 --- 24 пары, отклонение 96 --- 20 пар, отклонение -96 --- 21 пару. Могу привести эти группы чисел, если кому интересно (в статье группы не показаны; конечно, группы легко находятся по заданному отклонению от константы комплементарности - программка простенькая).

Программа нашла такое решение:

5  13  463  191  443  283  179  7 
 257  373  229  43  163  41  197  281 
 199  59  181  331  173  353  137  151 
 379  269  79  97  61  37  439  223 
 19  47  313  293  457  317  29  109 
 167  421  103  211  73  89  71  449 
 127  139  193  311  101  433  149  131 
 431  263  23  107  113  31  383  233

Сравните с известным решением:

5 13 463 293 443 283 53 31
313 379 71 73 89 79 191 389
23 211 167 331 199 353 149 151
449 239 41 97 59 127 349 223
19 47 439 269 457 317 29 7
241 383 109 103 17 83 229 419
101 139 181 311 277 281 163 131
433 173 113 107 43 61 421 233

Очевидно, что получилось новое решение, неизоморфное.

Теперь проверено: общая формула работает. Можно двигаться дальше.

[whitefox]

Для тех кому посчастливится найти четвёрку попарно ортогональных покрытий по моей программе, поясню формат выходного файла pokryt4.txt.

Каждая запись в выходном файле отвечает следующему шаблону:

2 5 5 3 3 3 3
2 5 5 3 3 3 3
4 5 3 3 3 3 3
4 5 3 3 3 3 3

где числа это номера подбаз данных (файлы razb2.txt, razb3.txt, razb4.txt, razb5.txt соответственно). В самой записи вместо номера подбазы будет стоять индекс разбиения (цепочки по терминологии Nataly-Mak) из соответствующей подбазы (нумерация начинается с нуля).
Каждой строке записи отвечает одно точное покрытие.

P.S. Кстати, проценты, что вы видите при работе программы, это процент от размера соответствующей подбазы (11141, 281234, 39698, 57683 для razb2.txt, . . .).

[Pavlovsky]

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

[whitefox]

Pavlovsky
Запустите пакетный файл exactcvr.bat.
Перевод сообщений сделаю попозже.

[Pavlovsky]

Запускал и пакетный файл.
Спрашивает <кракозябры> (y/n)
Затем просит ввести какой то интервал (тоже кракозябры).

[Nataly-Mak]

Тоже пробовала запустить пакетный файл. Аналогично.

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

[whitefox]

Англоязычную версию программы exactcvreng.exe берите там же: http://yadi.sk/d/Qr1NDjYR8q67V

[Nataly-Mak]

Решила попробовать построить решение с магической константой 1248 (лучшее решение Jarek). Решение с 4 дырками нашлось за 10 минут:

47  17  367  229  173  239  139  37 
 271  257  97  83  101  13  163  263 
 131  41  227  167  357*  211  107  7 
 331  181  31  19  149  33*  313  191 
 151  61  251  197  277  283  23  5 
 199  311  71  127  29  67  137  307 
 -123* 179  193  317  103  349  73  157 
 241  201*  11  109  59  53  293  281

Дальше не стала крутить программу, много времени может понадобиться для получения полного решения, но думаю, что оно существует --- именно построенное из псевдокомплементарных пар чисел. Разбиения на 4 группы хорошие получаются. В этом примере использовала отклонения 12, -12, 78 и -78, в группах 20, 21, 27 и 15 пар соответственно.
Напомню, что из каждой группы выбирается набор из 8 пар.

[whitefox]

Попробуйте русскоязычную версию exactcvrA.exe с принудительной перекодировкой в кодировку cp866.
Лежит там же: http://yadi.sk/d/Qr1NDjYR8q67V

[Nataly-Mak]

Попробовала искать решения с магической константой 1224.
Приближения с 8 дырками находятся мгновенно в большом количестве:

13  5  373  139  173  211  197  113 
 251  233  43  191  103  67  109  227 
 0  23  181  167  0  293  41  17 
 283  0  19  11  37  0  269  151 
 157  71  223  79  317  277  47  53 
 179  263  83  193  31  97  149  229 
 0  127  241  313  0  397  101  163 
 383  0  61  131  137  0  311  271

17  5  397  139  173  193  191  109 
 251  227  79  179  19  97  149  223 
 0  41  181  167  0  353  71  13 
 347  0  37  11  61  0  283  151 
 157  89  229  83  313  277  23  53 
 263  233  43  197  31  103  113  241 
 0  67  211  317  0  379  101  163 
 359  0  47  131  73  0  293  271

Чувствую, что решение с такой магической константой существует.

Однако... похоже, энтузиазм участников пошёл на убыль
Решений нет и не ожидается в ближайшем будущем.
Жду, может быть, Jarek появится...

А там и новый конкурс у AZ близко уже. Тогда и подавно все бросят эту задачу и примутся за новую. Но... сложные задачи так быстро не решаются, они решаются месяцами, а иногда и годами. Так что, кто надеялся с ходу, с лёту найти оптимальное решение для N=7, явно разочаровались. Оно, может быть, уже и найдено, как я уже писала ($S=749$), но кто его знает...

[Jarek]

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

Жду, может быть, Jarek появится...

I am back

I am afraid that the search for $N=7$ may require rethinking the whole algorithm - my original program was not designed to go so close to the lower bound.

[svb]

Pavlovsky в сообщении #762738 писал(а):

Запускал и пакетный файл.
Спрашивает <кракозябры> (y/n)
Затем просит ввести какой то интервал (тоже кракозябры).

Мне удалось увидеть нормальный текст после смены шрифта на Lucida Console (свойства окна -> шрифты)

[Nataly-Mak]

Jarek в сообщении #762859 писал(а):

I am back

С возвращением!

Цитата:

I am afraid that the search for $N=7$ may require rethinking the whole algorithm - my original program was not designed to go so close to the lower bound.

Вы могли бы сделать исполняемые программы для поиска решений $S=737$ и $S=743$, задав конкретный массив простых чисел для каждой магической константы?
Я хотела бы покрутить такие программы. Долго крутила программы mertz, но в этих программах нет нужных массивов простых чисел и в решениях появляются недопустимые числа, это плохо.
Объединённые массивы для указанных магических констант приведены выше.
То же самое можно сделать и для других магических констант. То есть для каждой магической константы должна быть своя индивидуальная программа: Pan743.exe, Pan737.exe и т.д.
Думаю, что можно сосредоточиться на проверке магических констант 743, 737, 735 и 733.

Да, новые подходы, конечно, очень нужны.
Здесь whitefox предложил один из таких подходов - алгоритм четырёх точных попарно ортогональных покрытий заданного массива из 49 различных простых чисел. Массив должен быть из класса потенциальных массивов, то есть он должен давать нужную магическую константу по сумме всех чисел массива.
Для магической константы 733, например, существуют всего два потенциальных массива из 49 различных простых чисел.

[Jarek]

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

Вы могли бы сделать исполняемые программы для поиска решений $S=737$ и $S=743$, задав конкретный массив простых чисел для каждой магической константы?
Я хотела бы покрутить такие программы.

I need some time to think more about it. The problem is that we can alter the program blindly and run it, but as we approach the lower bound there may be some constrains which have to be taken into account - otherwise we risk wasting time on running a program which isn't going to find anything for reasons forseeable with a little theoretical analysis.

I am thinking of a new approach, namely constructing pandiagonal squares modulo 30 from a given set of primes. Let start from the other end, namely 733. My question is: Can we use the two sets of primes to construct pandiagonal squares modulo 30?