Магические квадраты

[Nataly-Mak]

Я ищу сразу наборы (квадраты 2х2) из разных чисел. Первый набор найду, сразу выбрасываю из исходного массива эти 4 числа и ищу второй набор, затем снова выбрасываю из массива найденные 4 числа и так далее. В результате программа выдаёт мне только по 9 различных квадратов.
Теперь надо для каждого набора из 9 различных квадратов дописать блок проверки условий для отклонений. Вроде всё просматривается чётко.

[svb]

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

В результате программа выдаёт мне только по 9 различных квадратов.

Именно таких 9-ок и много, вот, например, 10000-ая 9-ка:

  5  11  17   7  13  29 
 19  23  31 101  61  47 
 41  43  53  71  79  59 
 37  67 137 283 241 149 
103  97  73 109 151 181 
 89  83 107 131 127 113 

[Nataly-Mak]

Так и радуйтесь, что их много, есть из чего выбирать

Программу дописала, тест она проходит, но только если задаю конкретные значения для получения первых трёх квадратов 2х2. Остальные 6 квадратов она находит быстро. Но если убираю конкретные значения для третьего квадрата, всё! Программа задумывается надолго.
Для тестирования взяла недавно построенный пандиагональный квадрат с магической константой 510.

Таким образом, первая реализация есть (через квадраты 2х2), но результатов пока нет.

Нужно придумывать оптимизации. Пока ничего хорошего не приходит в голову

Кстати, вот вы получили набор из 9 квадратов и сразу проверяете в нём отклонения? Я так делаю. Тогда если подходящий набор квадратов найдётся, он сразу же выведется и дальше уже не надо искать. То есть выполнение программы до первого пандиагонального квадрата.

P.S. Мне кажется, через квадраты 2х2 плохая реализация: очень много циклов.
Надо что-то другое попробовать.

[svb]

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

Надо что-то другое попробовать.

Есть одна идейка. Квадратов 2х2 не так уж и много. Для $S=498$ всего 931, если выкинуть 3 из состава простых чисел. Для каждого квадрата всего 3 возможных положительных $p$. Можно для каждого $p$ создать списки квадратов, которые допускают этот параметр "псевдокомплементарности". Эта предварительная работа не должна занять много времени.
Далее приступаем к следующему перебору.

1. Выбираем произвольные 4-ки параметров $p$ для $p2, p4, p6, p8$
2. Для каждой 4-ки вычисляем оставшиеся $p1, p3, p5, p7, p9$
3. Находим соответствующие квадраты с этими параметрами в списках квадратов с проверкой на совпадение входящих чисел.
4. В случае удачи восстанавливаем пандиагональный квадрат (к сожалению, не всегда).

Шаг 1 можно будет брать и в урезанном виде - обнадеживает то, даже для очень частных случаев выбора $p2, p4, p6, p8$:
$(0,0,0,0)$
$(p,0,0,-p)$
которые рассматривались ранее, был некоторый успех.

[Nataly-Mak]

Сначала брала массив из 50 первых простых чисел. Потом решила сократить массив до минимума, сгенерировала случайным образом массив из 36 чисел, дающий магическую константу 498:

29 211 67 113 191 73 23 139 181 43 41 151 149 101 53 59 97 3 19 11 5 17 137 71 131 107 37 31 13 61 79 103 199 109 127 7

Проверила, обычный МК из чисел этого массива строится.

Не стала массив ранжировать. Запустила программу поиска квадратов 2х2, программа нашла 7 правильных квадратов с ходу, вот с такими отклонениями p_i: 74, 14, 48, 58, 2, -64, -50. Условия для этих отклонений выполняются (я их сразу проверяю). Но дальше никак не хочет найти ещё два квадратика.
Интересный момент: когда числа идут вразброд, отклонения лучше получаются - и положительные, и отрицательные. И результат, наверное, получить быстрее удастся.

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

[Nataly-Mak]

Разложила два шаблона пандиагональных квадратов на квадратики 2х2, получились такие шаблоны:

1 5   1 1   5 5   1 1   5 1   5 5   1 5   1 1   5 5
1 1   5 1   5 5   1 5   1 1   5 5   1 1   5 1   5 5

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

Я уже начала переписывать программу с учётом шаблонов квадратов 2х2. В этом случае весь массив можно разделить на две равные части, например: 25 чисел с вычетом 1 и 25 чисел с вычетом 5 (можно увеличить количество чисел в массиве, но чем больше чисел, тем дольше программа будет выполняться; для магических констант 486 и 498 вполне достаточен массив из 50 чисел).
Тогда переменные циклов пробегают ровно в два раза меньше значений, что, естественно, убыстряет выполнение программы.

Товарищи программисты! Где же вы? Тему просматривают многие. Задача очень интересная! Тот случай, когда от очень изящного алгоритма до его реализации, как от неба до земли. Написать абы какую программу - это запросто (я уже написала такую). Но! Надо сделать такую программу, которая не за сутки выполнится и не за 12 часов. Вот в чём суперзадача.
Например, программа по предыдущему алгоритму svb находит пандиагональные квадраты за 10-20 секунд (сама в этом убедилась). Это высший пилотаж!

[Nataly-Mak]

Детализация предложенного svb алгоритма на самых простых примерах.

Пример 1.

Как я уже сказала, написала программу построения квадратов 2х2 по шаблону (один из двух видов шаблонов запрограммировала).
Далее генерирую случайным образом массив простых чисел для квадрата с магической константой 498:

157  151  139  163  73  97  31  43  13  103  109  19  79  37  7  181  193  67  11  71  23  89  149  113  59  5  137  41  47  53  17  83  167  101  29  131

Массив разделила на две группы: первые 18 чисел - с вычетом 1, следующие 18 чисел - с вычетом 5.
Теперь программа долго не думала Она отработала полностью за 1 секунду и ничего не нашла. Это может означать только одно: из чисел данного массива нельзя составить 9 квадратов 2х2, составленных по запрограммированному шаблону и удовлетворяющих нужным условиям.
Однако ещё ничего нельзя сказать о возможности или невозможности составления из чисел данного массива пандиагонального квадрата 6-го порядка с магической константой 498. Потому что есть другие шаблоны для квадратов 2х2, сколько их всего я пока не выяснила, но два вида точно имеется.

Но уже хоть что-то, по крайней мере, программа массив обсчитала мгновенно, это уже хорошо.

[svb]

Забыл сказать. Та же программа, которая выдавала очень много 9-ок квадратов 2х2 для $S=498$ не выдала ни одной 9-ки для $S=488$, но полную проверку провести не удалось - долго

[Nataly-Mak]

svb в сообщении #349557 писал(а):

Забыл сказать. Та же программа, которая выдавала очень много 9-ок квадратов 2х2 для $S=498$ не выдала ни одной 9-ки для $S=488$...

Вы хотели сказать для S = 486?

[svb]

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

Вы хотели сказать для S = 486?

Хотел , но сейчас решил заново проверить. Где-то через час 9-ки посыпались и вот 10000-ый набор:

  5  11  17   7  13  29
 23  31  37  79  47  73
 41  43  59  71  53  61
 19 107 127 293 193 151
 83  89 101 139 157 113
103  97  67 109 131 137

[Nataly-Mak]

А как насчёт 4 квадратов 3х3 с суммой чисел в них равной 3S/2?
Вот, например, такой квадратик из того же самого пандиагонального квадрата из последовательных простых чисел:

67 71 109
241 191 163
199 227 127

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

Интересно, что проще искать: наборы по 9 квадратов 2х2 или наборы по 4 квадрата 3х3?
Вообще обо всех этих необходимых условиях построения пандиагонального квадрата 6-го порядка писал в одном из сообщений Pavlovsky. Он, помнится, доказал с помощью вычетов, что из какого-то конкретного массива чисел пандиагональный квадрат построить невозможно именно потому, что не выполняется одно из необходимых условий разбиения массива чисел на группы.

[Nataly-Mak]

В статье Россера приведён следующий классический нерегулярный пандиагональный квадрат 9-го порядка:

1 65 48 41 24 58 81 34 17
57 76 33 13 8 70 53 39 20
68 49 44 27 62 75 28 12 4
80 36 16 3 64 47 40 23 60
52 38 19 56 78 32 15 7 72
30 11 6 67 51 43 26 61 74
42 22 59 79 35 18 2 66 46
14 9 71 54 37 21 55 77 31
25 63 73 29 10 5 69 50 45

Чтобы понять, как построен этот квадрат, изучила его "анатомию". Она очень занятная. Сразу увидела, что нетрадиционный нерегулярный пандиагональный квадрат, подобный данному классическому, можно построить из девяти арифметических прогрессий длины 9 с одинаковой разностью, первые члены которых a_i удовлетворяют следующим условиям:
a_1 + a_6 + a_8 = a_2 + a_4 + a_9 = a_3 + a_5 + a_7
a_1 + a_5 +a_9 = a_2 + a_6 + a_7 = a_3 + a_4 + a_8

Понятно, что этим условиям будут удовлетворять такие прогрессии, первые члены которых тоже образуют арифметическую прогрессию. Вот такие прогрессии я и взяла из произвольных натуральных чисел; разность прогрессий равна 3, первые члены a_i прогрессий образуют арифметическую прогрессию с разностью 10:

a_1 = 3, a_2 =13, a_3 = 23, a_4 = 33, a_5 = 43, a_6 = 53, a_7 =63, a_8 = 73, a_9 = 83
Замечу, что прогрессии, конечно, составляют примитивный квадрат.
Нетрадиционный нерегулярный пандиагональный квадрат 9-го порядка из чисел этих прогрессий получился такой:

3 76 59 55 38 72 107 51 34
69 92 48 22 24 91 74 49 26
85 62 64 47 84 89 33 19 12
104 57 31 9 73 56 52 35 78
71 46 23 66 98 45 28 21 97
39 16 18 82 68 61 44 81 86
58 32 75 101 54 37 6 79 53
25 27 94 77 43 29 63 95 42
41 87 83 36 13 15 88 65 67

Интересно, можно ли найти 9 прогрессий из простых чисел, удовлетворяющих указанным условиям? Ну, понятно, что условиям будет удовлетворять арифметическая пргогрессия длины 81, но такой пока не найдено Хотя теоретически она существует, значит и нерегулярный пандиагональный квадрат 9-го порядка из простых чисел существует, как, впрочем, и регулярный, потому что из чисел прогрессии длины 81 можно построить и регулярный пандиагональный квадрат.

Напомню, что пандиагональный квадрат 9-го порядка из простых чисел у нас вообще пока отсутствует, никакого нет

(Оффтоп)

Опять все пропали
Один svb воюет с квадратами 2х2
Pavlovsky, ау! Как у вас дела с нерегулярными пандиагональными квадратами? Мой квадрат вам не поможет?
Похоже, ваш приз останется невостребованным У меня тоже иногда возникало желание учредить приз за решение очень трудной задачи. Одна была у меня такая - построение обычного магического квадрата 7-го порядка из смитов, полгода её решала, но всё-таки решила. Но..., наверное, чтобы хоть кого-нибудь заинтересовать, приз надо учредить как минимум в миллион долларов или евро. Да где же мне взять такой приз

[Nataly-Mak]

Ещё одна деталь к алгоритму svb.

Пример 2.

Судя по сообщению svb для константы 486 наборов по 9 квадратов 2х2 получается значительно больше, чем для константы 498.
Я попробовала для этой константы конкретный массив, состоящий ровно из 36 чисел (случайная генерация):

139  37  7  41  23  131  157  181  47  73  173  31  67  109  151  97  11  13  17  71  59  113  137  53  89  43  61  199  19  5  79  107  163  83  29  101

По-прежнму разбила массив на две группы - с вычетом 1 и с вычетом 5.
Запустила программу построения квадратов 2х2 по шаблону, программа задумалась надолго. Вот! А для константы 498 программа через секунду вышла в конец и ничего не нашла.
Так что константа 486 подаёт большие надежды на составление пандиагонального квадрата 6-го порядка с такой константой.

Ой, извиняюсь, не ту программу запустила - общий вариант (не по шаблону).
Программа построения по шаблону точно так же через секунду вышла в конец и ничего не нашла. Может, в программе ещё чего-то не так

[svb]

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

Я сейчас расписала эту решётку, в ней всё совершенно аналогично.

Любопытно, действительно:
$\left( {\begin{array}{*{20}c} {\left( {q1} \right)} & { - q3} & {\left( {q2} \right)} & { - q1} & {\left( {q3} \right)} & { - q2} \\ { - q7'} & {q9'} & { - q8'} & {q7'} & { - q9'} & {q8'} \\ {\left( {q4} \right)} & { - q6} & {\left( {q5} \right)} & { - q4} & {\left( {q6} \right)} & { - q5} \\ { - q1'} & {q3'} & { - q2'} & {q1'} & { - q3'} & {q2'} \\ {\left( {q7} \right)} & { - q9} & {\left( {q8} \right)} & { - q7} & {\left( {q9} \right)} & { - q8} \\ { - q4'} & {q6'} & { - q5'} & {q4'} & { - q6'} & {q5'} \\ \end{array}} \right)$
При этом соотношения между $q$ напоминают (но не совпадают!) соотношения между $p$
$q1+q5+q9=0$
$q3+q5+q7=0$
$q1+q6+q8=0$
$q9+q2+q4=0$
$q3+q4+q8=0$
$q7+q2+q6=0$
Жаль, что не совпадают , иначе можно было бы получить симпатичное преобразование квадратов. Но ... в любом случае необходимо будет в этом направлении "покопать".

-- Вс сен 05, 2010 12:26:26 --

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

Судя по сообщению svb для константы 486 наборов по 9 квадратов 2х2 получается значительно больше, чем для константы 498.

Я сейчас уже не уверен в этом, т.к. "сыпались" они так же быстро, как и для 498, просто позднее.

[Nataly-Mak]

svb
по вашей программе perebor2.exe составила вот такую любопытную статистику по отклонениям для магической константы 486. S_c = 162.
Далее в первой колонке таблицы S_b, во второй колонке отклонение, в третьей колонке - количество пар с суммой S_b, в четвёртой колонке - S_a, в пятой колонке количесвто пар с суммой S_a:

162   0   9   162   9
164   2   5   160   8
166   4   5   158   4
168   6   13 156   11
170   8   9   154   8
172  10   5   152   3
174   12  11 150   12
176  14   7   148   5
178  16   6   146   5
180  18  14   144   10
182  20   6   142   7
184  22   8   140   7
186  24  12   138   7
188  26   5   136   5
190  28   8   134   5
192  30  11   132   9
194  32   6   130   7
. . . . . . . . . . .
316  154   10   8   1
318  156   15   6   0
320  158   10   4   0
322  160   11   2   0
324  162   20   0   0

Как вы думаете, эта статистика не может нам как-то помочь?

Для статистики я взяла массив первых 86 простых чисел (конечно, без числа 2, но включая число 3). Если взять меньше чисел, количество многих пар уменьшится. Вообще зря взяла такой большой массив, надо было взять из 50 чисел. Но это недолго пересчитать.