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

[Nataly-Mak]

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

Вчера стартовал новый конкурс "Pandiagonal Squares of Consecutive Primes"
http://primesmagicgames.altervista.org/wp/competitions/

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

Это было очень интересное обсуждение. Особенно трудной была задача построения наименьшего пандиагонального квадрата 7-го порядка с магической константой $S=733$. Задача решалась уже после окончания конкурса. В решении приняли участие многие.
Мне, например, очень понравился алгоритм, предложенный whitefox

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

Алгоритм "танцующих связей" для решения задачи точного покрытия:
http://arxiv.org/pdf/cs/0011047v1.pdf

Мы пытались применить этот алгоритм при поиске минимального решения для $n=7$. Но наши попытки не увенчались успехом.
А какой красивый алгоритм! Очень хочу попробовать этот алгоритм для построения наименьшего решения в новой конкурсной задаче - это пандиагональный квадрат 7-го порядка из последовательных простых чисел с магической константой $S=797$.

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

Всех форумчан приглашаю к решению этой очень сложной проблемы. Готовых решений вы не найдёте в Интернете. Известны решения только для двух порядков - $n=4 $ и $n=6$.
Правила конкурса (подробное описание по указанной ссылке) запрещают вводить известные решения.
Найдите новые решения! Будьте первыми!
Считаю, что самые сложные и интересные задачи - это те, которые ещё никто не решил.

Конкурс продлится 3 месяца, времени много.

[Nataly-Mak]

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

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

Магическая константа $S = 797$.

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



Такие квадраты без проблем может генерировать программа ice00, например.
Моя программа тоже может, но не так быстро.

Теперь о покрытиях.

Определение 1
точным покрытием массива, состоящего из 49 чисел, называется набор из 7 цепочек, каждая из которых состоит из 7 различных чисел массива, дающих в сумме магическую константу квадрата, и никакие две цепочки не содержат одинаковых чисел
(магическая же константа квадрата, понятно, получается как сумма всех чисел массива, делённая на 7)

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

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

Что мы имеем в магическом квадрате? Два точных ортогональных покрытия плюс по одной цепочке из третьего и четвёртого покрытий (это главные диагонали магического квадрата).
Для приведённого квадрата

первое точное покрытие (строки):

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

второе точное покрытие (столбцы):

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

одна цепочка из третьего точного покрытия (диагонали):

43 173 227 179 17 19 139

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

97 47 113 179 157 101 103

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

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

Я уже состряпала программку поиска цепочек для третьего покрытия. Думала, что это быстро получится. Ничего подобного!
Первые две цепочки нашлись мгновенно:

7 41 73 101 167 197 211
53 71 97 127 131 137 181

а третья уже не нашлась.

Понятно, что нужно возвращаться на поиск другой второй цепочки, перебрав все варианты, возвращаться на поиск другой первой цепочки. В общем, тут дерево с тысячами ветвей.
И всё это очень непросто реализовать.
Далее: вполне может оказаться, что для выбранного магического квадрата невозможно найти третье и четвёртое покрытия. Тогда надо брать другой магический квадрат и начинать поиск третьего и четвёртого покрытий сначала. А обычных МК будут многие тысячи, может, даже миллионы.

Надо делать анализ БД (всех цепочек), как это whitefox сделал для квадрата из простых чисел с магической константой $S=733$. Надо эту БД составить.

[Nataly-Mak]

Для квадратов порядка $n=6$

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

Вот нашла страницу на сайте alexBlack, посвящённую пандиагональным квадратам 6-го порядка
http://alex-black.ru/article.php?content=121

Замечательная статья! Во-первых, есть общая формула пандиагонального квадрата 6-го порядка. Во-вторых, очень подробно описан алгоритм построения, приведены иллюстрации.

Однако, я не вижу программу хотя написано:

Цитата:

Ниже программа для проверки и исходники (Delphi).

Удалил автор программу? Но почему?! Такая отличная программа!

Программа на сайте автора появилась после этого сообщения.
Прекрасно!
alexBlack
спасибо, что выложили программу.

Помнится, программ для поиска пандиагонального квадрата 6-го порядка я в прошлом написала не менее 10 штук. Это были самые разные алгоритмы поиска. И общая формула у меня тоже была получена решением системы уравнений. Использовала при поиске и общую формулу, и шаблоны, и псевдокомплементарные пары, и... чего только я не использовала
Сейчас вот думаю: не написать ли новую программу?
Программы коллег хороши, но... они не годятся для проверки большого количества потенциальных магических констант. Здесь ведь как надо: генерируем некоторый массив простых чисел, ищем в нём все годные массивы из 36 последовательных простых чисел и сразу же проверяем каждый годный массив на предмет построения пандиагонального квадрата 6-го порядка. Такой конвейер должен работать.

Я вот по одной константе уже проверила до константы 264918, но очень нудно
А решение, похоже, где-то далеко-далеко...

[Nataly-Mak]

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

Надо делать анализ БД (всех цепочек), как это whitefox сделал для квадрата из простых чисел с магической константой $S=733$ . Надо эту БД составить.

Ну, составить БД всех цепочек - не проблема.
Составляю, конечно, упорядоченные цепочки. На составление ушло секунд 5.
Это хвост БД:

. . . . . . . . . 
89  97  107  109  113  131  151 
 89  97  107  109  127  131  137 
 89  101  103  107  109  131  157 
 89  101  103  107  109  137  151 
 89  101  103  107  109  139  149 
 89  101  103  107  113  127  157 
 89  101  103  107  127  131  139 
 89  101  103  109  113  131  151 
 89  101  103  109  127  131  137 
 89  101  107  109  113  127  151 
 89  103  107  109  113  127  149 
 89  103  107  109  113  137  139 
 97  101  103  107  109  113  167 
 97  101  103  107  109  131  149 
 97  101  103  107  113  127  149 
 97  101  103  107  113  137  139 
 97  101  107  109  113  131  139 
 97  103  107  109  113  131  137 
 101  103  107  109  113  127  137 

D= 397303 

Итак, имеем 397303 упорядоченных цепочек для построения пандиагонального квадрата 7-го порядка из последовательных простых чисел с магической константой $S=797$.
Теперь нужен анализ цепочек.

Из этой БД для 4-х точных попарно ортогональных покрытий массива нам надо выбрать всего 28 цепочек!
Неужели это невозможно

[Nataly-Mak]

Ранжировала цепочки в двух первых точных покрытиях, показанных выше.

Первое покрытие – строки:

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

Второе покрытие – столбцы

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

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

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

Вот два ортогональных покрытия у нас есть. А теперь из составленной БД надо составить ещё два точных покрытия, то есть выбрать всего 14 цепочек, но чтобы это были 4 попарно ортогональных точных покрытия.
Если это удастся, тогда надо решить вопрос: всегда ли 4 точных попарно ортогональных покрытия дают пандиагональный квадрат (мы сейчас рассматриваем квадраты 7-го порядка, вот для них и будем решать вопрос).

[Nataly-Mak]

Господа!
Замечу, что я разрешаю выкладывать в обсуждении всё, кроме готовых решений.
Алгоритмы, идеи, коды программ... Разумеется, если кому не жалко
Если кто-то хочет посоревноваться и быть лидером, естественно, он может и не раскрывать пока свои алгоритмы.

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

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

-- Пт сен 26, 2014 04:22:06 --

Начались эксперименты по точным покрытиям ну очень зацепил меня этот алгоритм.

Вчера думала целый день, с чего же начать реализацию этого алгоритма. Уже к вечеру начала писать программу поиска пары точных ортогональных покрытий; вот чтобы это была не случайно сгенерированная пара (такие-то легко находить), а созданная по порядку, перебором.
И что у меня получилось, ужас Такое впервые случается за всю мою практику - переполнение вложенности циклов.
QBASIC не потянул столько вложенных циклов, явно растерялся

Вот что уже удалось получить:

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  37  59  113  149  181  239 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 

Почти готовая пара точных ортогональных покрытий массива. И это получается мгновенно!

Что же мне делать с этим переполнением вложенности циклов

Я, конечно, могу достроить второе точное покрытие в другой программе, но это уже не будет точный перебор всех вариантов, который мне нужен.

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

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

-- Пт сен 26, 2014 05:01:10 --

Эксперимент

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

(Оффтоп)

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  37  59  113  149  181  239 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0
- - -  

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  41  53  103  149  193  239 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - - 

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  41  59  103  149  193  233 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  41  61  101  149  193  233 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  41  61  107  149  193  227 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  41  61  113  131  193  239 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  43  53  101  149  193  239 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  43  53  107  149  193  233 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  43  53  113  149  193  227 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
- - -

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

 7  17  71  139  173  191  199 
 11  29  223  47  151  157  179 
 13  23  83  137  163  167  211 
 19  43  59  101  149  193  233 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0

Вроде всё правильно.

[Nataly-Mak]

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

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

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

 11  47  53  107  157  199  223 
 13  61  89  101  149  191  193 
 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]

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

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

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

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

Что же мне делать с этим переполнением вложенности циклов

Я, конечно, могу достроить второе точное покрытие в другой программе, но это уже не будет точный перебор всех вариантов, который мне нужен.

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

[Nataly-Mak]

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

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

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

Вы уже этот алгоритм реализовали, как я понимаю. Так не поискать ли вам решение конкурсной задачи для $n=7$?

Цитата:

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

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

[Nataly-Mak]

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

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

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

17  31  73  107  163  167  239 
11  47  61  113  137  199  229 
13  71  97  103  109  181  223 
19  29  41  139  157  179  233 
0  0  0  0  0  0  0 
0  0  0  0  0  0  0 
0  0  0  0  0  0  0 

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

Ошибки возможны, тщательно не проверяла все три программы.

[Nataly-Mak]

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

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

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

13  37  71  83  179  191  223 
17  43  61  101  149  199  227 
7  47  53  113  137  211  229 
23  41  73  97  151  173  239 
31  59  79  89  139  167  233 
0  0  0  0  0  0  0 
0  0  0  0  0  0  0 

-- Пт сен 26, 2014 13:09:44 --

whitefox
а что вы можете сказать по поводу вашей гипотезы: любой комплект 4-х точных попарно ортогональных покрытий массива из 49 чисел даёт пандиагональный квадрат 7-го порядка из этих чисел
Я что-то так и не поняла: эта гипотеза верна?

Я сейчас решила протестировать свои 4 программки, которые строят по порядку все 4 точных попарно ортогональных покрытия. Первые два покрытия взяла из известного решения (мой пандиагональный квдарат 7-го порядка из простых чисел с магической константой $S=1597$), третье и четвёртое покрытия строила программками.
Они получились не такие, как в исходном квадрате.

191 89 397 409 43 157 311
379 103 101 491 17 313 193
317 241 109 163 439 47 281
223 383 227 107 541 37 79
331 337 7 139 167 563 53
83 347 389 277 127 307 67
73 97 367 11 263 173 613

191 379 317 223 331 83 73
89 103 241 383 337 347 97
397 101 109 227 7 389 367
409 491 163 107 139 277 11
43 17 439 541 167 127 263
157 313 47 37 563 307 173
311 193 281 79 53 67 613

613  17  83  157  163  227  337 
11  79  103  127  317  397  563 
7  73  107  311  313  347  439 
37  89  167  277  281  367  379 
43  67  109  173  331  383  491 
47  97  139  191  193  389  541 
53  101  223  241  263  307  409

7  47  89  127  223  491  613 
11  53  109  157  347  379  541 
17  73  139  281  307  383  397 
37  103  163  263  311  331  389 
43  83  107  193  241  367  563 
67  97  167  227  313  317  409 
79  101  173  191  277  337  439 

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

[Nataly-Mak]

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

Тогда зачем нам искать четвёрки точных попарно ортогональных покрытий, если вы говорили, что легко проверить, можно ли из полумагического квадрата получить пандиагональный? А пары-то ортогональных покрытий (полумагические квадраты) ищутся легко.

-- Пт сен 26, 2014 16:42:08 --

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

613  17  83  157  163  227  337 
11  79  103  127  317  397  563 
7  73  107  311  313  347  439 
37  89  167  277  281  367  379 
43  67  109  173  331  383  491 
47  97  139  191  193  389  541 
53  101  223  241  263  307  409

7  47  89  127  223  491  613 
11  53  109  157  347  379  541 
17  73  139  281  307  383  397 
37  103  163  263  311  331  389 
43  83  107  193  241  367  563 
67  97  167  227  313  317  409 
79  101  173  191  277  337  439

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

7 47 89 127 223 491 613
73 139 281 397 307 383 17
107 193 367 563 241 43 83
311 389 37 103 263 331 163
313 97 167 317 409 67 227
347 541 379 11 53 109 157
439 191 277 79 101 173 337

Всё чётко.

[whitefox]

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

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

В данном случае это и не возможно.

Существует всего три способа объединить точные покрытия в пары: (1,2)(3,4); (1,3)(2,4); (1,4)(2,3).

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

Если этим точным покрытиям соответствует какой-то пандиагональный квадрат, то им также соответствует и пандиагональный квадрат с 7 в левом верхнем углу.

Тогда через верхний левый угол проходит прямая диагональ (7, 73, 107, 311, 313, 347, 439). И если этим точным покрытиям и этому их распределению по "линиям" соответствует какой-то пандиагональный квадрат, то им также соответствует и пандиагональный квадрат с 7 в левом верхнем углу и 439 в правом нижнем углу.

Строка (7, 53, 139, 167, 331, 337, 563) пресекается со столбцом (17, 43, 127, 167, 263, 439, 541) в точке 167 в правом верхнем углу. А столбец (7, 101, 109, 227, 367, 389, 397) пересекается со строкой (47, 109, 163, 241, 281, 317, 439) в точке 109 в левом нижнем углу.

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

Другие два случая проверяются аналогично.

[Nataly-Mak]

Так вот именно так я и проверяла и ничего не смогла построить.
Жалко, что сканер у меня давно сломался, а то бы показала листочек, на котором все эти цепочки пыталась разместить в квадрат 7х7.

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

Тут выше Pavlovsky задавал вопрос: так мы можем проверять четвёрку точных попарно ортогональных покрытий на построение из этих покрытий пандиагонального квадрата?
В этом примере показано, как это проверяется. Значит, можем проверять. Давайте побольше таких четвёрок точных попарно ортогональных покрытий
Я пока ни одной такой четвёрки не нашла для массива из 49 простых чисел, дающих потенциальную магическую константу 797.

Цитата:

Существует всего три способа объединить точные покрытия в пары: (1,2)(3,4); (1,3)(2,4); (1,4)(2,3).

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

-- Сб сен 27, 2014 03:31:32 --

whitefox
А я вчера весь вечер ломала голову над вашим алгоритмом проверки полумагического квадрата.
Очень долго до меня доходил смысл трансверсалей. Потом, наконец, дошёл
Несколько лет назад я писала программу построения обычных МК из простых чисел. Вот там алгоритм был такой: сначала случайная генерация 7 цепочек, это 7 строк. Второй этап: перестановками чисел в строках добиваемся, чтобы получились нужные суммы чисел в столбцах. Полумагический квадрат построен. А вот на третьем этапе пытаемся превратить полученный полумагический квадрат в магический, сделав две главные диагонали квадрата магическими. Вот тут и работали ваши трансверсали
Этот алгоритм я придумала на заре своего увлечения магическими квдратами (ещё на старенькой ЭВМ применила этот алгоритм для построения обычных классических МК 6-го порядка; прекрасно работал). Алгоритм подробно описан в одной из моих статей.
А когда познакомилась с ice00, узнала, что он примерно так же строил магические квадраты из простых чисел (это есть в его статье, которую я не раз выкладывала).

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

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

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



Такие квадраты без проблем может генерировать программа ice00, например.
Моя программа тоже может, но не так быстро.

(кстати, квадрат построен как раз по описанному алгоритму)

Вот мы имеем вагон и маленькую тележку магических квадратов с магической константой $S=797$. При этом случайная генерация вряд ли даст хотя бы два одинаковых квадрата, вероятность этого события почти равна 0.
Ну и вот: генерируем миллион магических квадратов и проверяем, можно ли их превратить в пандиагональные.
А как это проверяем? Да очень просто - с помощью М-преобразований.
Заглянула вчера в свою книгу "Волшебный мир магических квадратов"; М-преобразования в этой книге подробно описаны (я указываю, что описываю эти преобразования по книге Ю. В. Чебракова).
Действительно, М-преобразования не изменяют суммы чисел в строках, в столбцах и в главных диагоналях квадрата, зато изменяют эти суммы для чисел в разломанных диагоналях. И поэтому можно получить с помощью этих преобразований из магического квадрата пандиагональный. Но! замечу, что вероятность этого чрезвычайно мала, практически равна 0. Таких изоморфов для порядка 7 очень мало и вряд ли это приведёт к получению нужных сумм во всех разломанных диагоналях.

Кстати, вчера пыталась посчитать, сколько же этих изоморфов для квадратов 7-го порядка. Вы говорите, что их 8. В книге Чебракова написано, что М-преобразований для квадратов 7-го порядка 24.

[Nataly-Mak]

svb
поискала на вашем сайте программу Diab_v5.exe и, увы, не нашла.
Хотела дать ссылку на эту программу.
Вот нашла статью о пандиагональных квадратах
http://svb.hut.ru/mag_pand.htm

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

Summa=462042
Time: 157.05 sec
Summa=469818
Time: 72.73 sec
Summa=471714
Time: 35.80 sec
Summa=473910
Time: 77.25 sec
Summa=475866
Time: 211.36 sec
Summa=482586
Time: 13.32 sec

Хорошо идёт проверка, одно плохо: программа может проверять по одной константе

Как насчёт того, чтобы немножко модифицировать программу
Чтобы она работала так, как работает программа для поиска квадрата Стенли 5-го порядка из последовательных простых чисел. Нашла подходящий массив из 36 последовательных простых чисел, сразу же его проверила, снова ищет подходящий массив и т.д.

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