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

[Pavlovsky]

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

Для обычных магических квадратов всё намного проще.

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

К сожалению, совсем не значит.

Хорошо. Тогда в эту сторону я схожу один.

[Nataly-Mak]

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

Вот я сейчас программу сделала и кручу её для массива из 59 чисел. Разумеется, если взять массив ровно из 49 чисел, выполнение программы ускорится во много-много раз. Это очевидно. Но сколько будет потенциальных массивов? Тысяча, миллион?

-- Вт авг 27, 2013 10:35:31 --

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

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

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

Кстати, думаю, думаю... Кажется, я догадываюсь о подходе YuriiS, если он всё время талдычит о базе данных.
Этот подход не новый, его, как мне кажется, использовал 12d3 ещё когда мы искали наименьший квадрат 6-го порядка из чисел Смита. Этот квадрат у меня никак не получался по моему алгоритму, хотя алгоритм прекрасно работает для квадратов из простых чисел.
Тогда 12d3 и сделал свою программу. Алгоритм свой он описал очень кратко, но мне кажется, я проникла в его суть. Ну, может, и не проникла
Итак, база данных... Что может быть в этой базе данных? Первое, что приходит в голову: в этой базе данных могут быть цепочки!
В показанном выше квадрате вы видите 7 таких цепочек. Цепочки - это все возможные наборы по 7 различных чисел, сумма которых равна магической константе квадрата. Все такие цепочки и составляют базу данных для данной магической константы.
Теперь начинаем строить квадрат из этих цепочек.
Положили две цепочки:

3 5 7 23 223 233 239
11 13 17 103 193 197 199

Теперь проверяем по всей БД, есть ли цепочки, начинающиеся с (3,11), (5,13) и т.д. При этом проверять надо комбинации по всем столбцам и всем диагоналям, в строках не надо проверять, так как мы кладём в строки готовые цепочки.
Если цепочки со всеми комбинациями по два числа в БД имеются, идём дальше: добавляем третью строку:

3 5 7 23 223 233 239
11 13 17 103 193 197 199
19 29 31 71 181 191 211

Теперь проверяем, есть ли в БД цепочки, начинающиеся с трёх чисел: (3,11,19), (5,13,29) и т.д.
Может, я ошибаюсь и это бредовый метод. Но! 12d3 именно на цепочках основывал своё построение. Это точно.
Может, не совсем так, как я это описала, но где-то очень близко.

P.S. Я много раз пользовалась программой 12d3. Очень хорошо видно, что работа программы начинается именно с нахождения всех цепочек по 6 чисел (программа для квадратов 6-го порядка). На это уходит некоторое время; потом программа выдаёт количество найденных цепочек. Вот! Прямо точно сообщает, сколько найдено цепочек!
И уже после этого начинается поиск квадратов.
В самом начале программа заправшивает ввод магической константы. То есть цепочки она ищет по заданной магической константе.

[Nataly-Mak]

Тем временем программа нашла второе решение с одной дыркой и опять двойняшки



-- Вт авг 27, 2013 11:05:13 --

Кстати, да: построение БД из всех возможных цепочек - задача непростая, ибо цепочек будет очень много, особенно из простых чисел (в отличие, скажем, от цепочек из чисел Смита).
Цитата из вышеуказанной статьи:

Цитата:

При построении квадрата 7-го порядка я не стала генерировать все строки из чисел данного массива с суммой чисел в строке, равной 733, потому что таких строк получается очень много и обработка полученного массива строк затруднительна. Я придумала хитрый ход: сразу стала генерировать нужный набор из 7 строк, используя функцию случайных чисел. Такой набор для порядка 7 генерируется за несколько секунд. И первый же набор превратился в магический квадрат.

[Pavlovsky]

Прибрасываю алгоритм для нечетных N. Пусть у нас есть $N^2$ различных простых чисел. Для построения пандиагонального квадрата достаточно разбить эти $N^2$ чисел на N групп по N чисел 4-мя способами. Сумма чисел в каждой группе равна магической константе. Причем две любые группы чисел из различных способов разбиения должны иметь ровно одно общее число.

[Nataly-Mak]

(Оффтоп)

svb
ау!
С днём рождения!
И нехорошо, однако, отлынивать, когда коллеги трудятся в поте лица
Подключайтесь уже. Надо же всё-таки решить задачу до конца. Тем более что, как утверждает один персонаж на форуме ПЕН, решение с магической константой 733 существует. Ну, если оно существует, мы его, конечно, найдём

[dmd]

Почему алгоритм Jarek настолько эффективен и чем он отличается от алгоритма Pavlovsky?

Кто понял и кому не трудно - опишите пожалуйста алгоритм Jarek по-русски.

[Nataly-Mak]

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

Сумма чисел в каждой группе равна магической константе.

Вот эти группы и есть цепочки.

[Nataly-Mak]

mertz
что означает информация в файле LOG?

 100000000  0    0 0
 300000000  0    0 0
 100000000  0    0 0
 200000000  0    0 0
 400000000  0    0 0
 200000000  0    0 0
 300000000  0    0 0
 100000000  0    0 0
 400000000  0    0 0
 200100000  1   41 3108
 400100000  0   56 3113
 300100000  0   51 3146
 100100000  1   40 3034

-- Вт авг 27, 2013 14:13:47 --

Программа нашла третье решение с одной дыркой и опять двойняшки, на этот раз повторено число 89.
Не часто у меня находятся решения с одной ошибкой, почти за 7 часов всего 3 решения. С двумя ошибками решений уже более 200.

[Nataly-Mak]

dmd в сообщении #758096 писал(а):

Кто понял и кому не трудно - опишите пожалуйста алгоритм Jarek по-русски.

dmd
Если не поняли отдельные места, задайте ваши вопросы Jarek здесь по-русски.
Jarek прекрасно владеет русским языком; пишет здесь по-английски только потому, что у него нет клавиатуры с кириллицей. Мне он пишет по-русски, но латинскими буквами.

Программа поиска решения с магической константой 743 работала весь день (более 12 часов), по-прежнему только 3 решения с одной ошибкой, более 500 решений с двумя ошибками.
Как я понимаю, на моём компьютере программа будет работать очень долго, в течение одного рабочего дня она не выполняется. Это уже плохо.

Надо делать в программе прерывания.
Так делал программу whitefox (поиск диагональных раскрасок для С5). Что значит - делать прерывания? Это значит, что программу можно прервать в любой момент с сохраненем всех уже найденных результатов и текущих значений переменных; при следующем запуске программа начнёт работать с этих сохранённых значений. Не знаю, возможно ли такое прерывание в данной программе.
Я на ночь компьютер выключаю. Поэтому такие долгоиграющие программы не могу выполнять без прерываний.

-- Вт авг 27, 2013 22:13:57 --

А вот и четвёртое решение с одной дыркой



Здесь дырка весьма симпатичная - двойняшки рядышком.
Эх, никак не находится решение без ошибок, а так хочется

-- Вт авг 27, 2013 22:31:00 --

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

Прибрасываю алгоритм для нечетных N. Пусть у нас есть $N^2$ различных простых чисел. Для построения пандиагонального квадрата достаточно разбить эти $N^2$ чисел на N групп по N чисел 4-мя способами. Сумма чисел в каждой группе равна магической константе. Причем две любые группы чисел из различных способов разбиения должны иметь ровно одно общее число.

Pavlovsky
вы совершенно правильно мыслите.
Вот вам разбиение первым из 4-х способов:

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

В вашей терминологии 7 групп, в моей терминологии - 7 цепочек.
Все 7 цепочек составлены из различных чисел, то есть никакие две цепочки не имеют ни одного общего элемента. Всё правильно. Задействованы все 49 чисел массива.

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

Насколько трудно найти такие разбиения?
Первое разбиение - это 7 строк, второе разбиение - это 7 столбцов, ещё два разбиения - это диагонали двух направлений.
В обычном магическом квадрате проще: первое разбиение - строки (с поиска этого разбиения я начинала свой метод), второе разбиение - столбцы, а вот в двух последних разбиениях всего по одной цепочке - это главные диагонали.
Ещё проще в полумагических квадратах, для них надо искать всего два разбиения - строки и столбцы, что в главных диагоналях получится - неважно.

Эх, ну где же svb со своими базисами? Так его не хватает.

[Nataly-Mak]

Конкретный пример разбиений, о которых написал Pavlovsky.

Взяла решение Jarek с магической константой 755:

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

Ранжированный массив простых чисел, из которых составлен этот квадрат:

3  5  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  197  199  223  227  241  251  311

Кстати, последнее число куда отлетело! Я использую в своей программе массив, заканчивающийся числом 293, оказывается этого не достаточно.

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

Первое разбиение (строки):

(3  11  43  103  157  197  241),
(5  19  101  113  127  139  251),
(7  23  29  37  149  199  311),
(13  41  71  109  167  173  181),
(17  67  97  107  137  151  179),
(31  59  79  83  89  191  223),
(47  53  61  73  131  163  227)

Второе разбиение (столбцы):

(3  19  73  79  97  173  311),
(5  59  61  67  167  197  199),
(7  31  41  113  157  179  227),
(11  29  101  109  151  163  191),
(13  23  83  127  131  137  241),
(17  37  53  71  103  223  251),
(43  47  89  107  139  149  181)

Третье разбиение - диагонали первого направления:

(3  41  61  127  149  151  223),
(5  13  17  89  157  163  311),
(7  53  79  101  107  167  241),
(11  71  73  83  139  179  199),
(19  29  59  103  137  181  227),
(23  31  47  97  109  197  251),
(37  43  67  113  131  173  191)

Четвёртое разбиение - диагонали второго направления:

(3  7  67  83  163  181  251),
(5  79  103  109  131  149  179),
(11  37  89  97  127  167  227),
(13  29  73  107  113  197  223),
(17  19  41  47  191  199  241),
(23  53  59  139  151  157  173),
(31  43  61  71  101  137  311)

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

Ну, и конечно, работать надо только с массивом из 49 чисел - одним, конкретным. А таких массивов для одной магической константы, как я уже отметила, будет море.
Так что, алгоритм хорош, но... в реализации очень непростой, на мой взгляд.

P.S. Разбиения делала вручную, возможны ошибки.

-- Ср авг 28, 2013 00:27:32 --

Внимание! Вопрос:
возможен ли другой набор 4-х разбиений для приведённого примера ($S=755$)
Другими словами: существует ли неизоморфное решение?

[mertz]

New version. Results will be different every time you run it. Added a box next to the Run button. This shows the total number of searches for all threads. I get 145 per second with 12 threads. Consider there are 4 billion possible. Trying them all would take a long time. Now to work on speed improvements.

https://www.dropbox.com/s/utxwf45xo83ry6l/Pan.exe

[Nataly-Mak]

mertz
спасибо за новую версию программы.

Сегодня я пробую найти решение $S=737$.
Успехов у меня пока никаких.
Параллельно работаю над своей программой. Выполнив много экспериментов, установила оптимальное соотношение между случайно выбранными и полностью перебираемыми переменными, это соотношение такое: 9 переменных выбираются случайно, 14 переменных полностью перебираются. При таком раскладе программа работает приемлемое время. Теперь остаётся крутить её для различных наборов случайно выбранных переменных, что и буду сегодня делать. Посмотрев на решение Jarek $S=755$, добавила в свой массив ещё два числа: 307 и 311. Теперь у меня в массиве 63 числа - все простые от 3 до 311.
Напомню: моя программа составлена для поиска решений с магическими константами кратными 3.

dimkadimon
а что у вас нового?

-- Ср авг 28, 2013 08:13:27 --

Jarek
вопрос к вам: какой массив простых чисел вы задействовали в вашей программе
При поиске решения с магической константой 737 сейчас у меня появилось решение с двумя ошибками, в котором присутствует число 373. Это число ни в каком случае не может входить в решение с магической константой 737, так как оно слишком большое для данной магической константы.
Я определяю максимально возможный размер массива так: вычисляю сумму всех чисел для квадрата с данной магической константой; при $S=737$ сумма всех чисел в квадрате равна 5159. Далее вычисляю сумму первых 48 нечётных простых чисел - от 3 до 227 (она равна 4886) и потом смотрю на разность этих двух сумм. В данном примере $5159-4886=273$.
Очевидно, что число 373 не может входить в квадрат с магической константой 737.
Количество чисел в массиве должно быть выбрано строго максимально возможное для заданной магической константы; лишние числа включать нежелательно, ибо это увеличивает время выполнения программы.

[Nataly-Mak]

Вот какое интересное решение:



Интересное тем, что в нём присутствует число 1.
Есть головоломка на сайте Carlos Rivera, в которой надо искать пандиагональные квадраты из простых чисел плюс число 1
http://www.primepuzzles.net/puzzles/puzz_699.htm
Если бы в показанном решении не было повторения числа 17, то это было бы нужное решение.
У меня результат в этой головоломке для N=7, S=1577; это регулярный пандиагональный квадрат.

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

Jarek
к вам такая же просьба.

[whitefox]

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

Ну, и конечно, работать надо только с массивом из 49 чисел - одним, конкретным. А таких массивов для одной магической константы, как я уже отметила, будет море.

Для S=755 таких массивов 2415,
для S=737 -- 7,
для S=733 -- 2.

[Nataly-Mak]

О, кто к нам пришёл!
whitefox
рада вас видеть.

Спасибо за данные. Значит, для маленьких магических констант (733, 737) массивов не море, а маленький ручеёк
Ну что ж, это хорошо.
А почему вы для магической константы 735 не посчитали? Мне как раз очень интересна эта магическая константа, ибо она кратна 3 и подходит для моей программы.
Если не трудно, выложите, пожалуйста, все массивы для этой магической константы, если, конечно, их не очень много. Я буду тогда проверять не объединённый массив из 63 чисел (как сейчас), а отдельно массивы из 49 чисел.