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

[mertz]

Hi Jarek. I might have found a program error

   if(bad&&number[*t[r][c]]!=3);
   {
      ImproveRing(HalfRandomRing(r+N,c+N),(rand()%3)?1:-1);
#if (N%2)==0   
      if(bad&&number[*t[r][c]]!=3)ImproveRing(HalfRandomRing2(r+N,c+N),(rand()%3)?1:-1);
#endif   
   }

the ; at the end of the statement would cause the code inside the braces to be executed every time.

Can you tell me how to change the program to find 761 or higher ( something quickly ). I want to make sure the program is running correctly.

[Nataly-Mak]

Есть сообщение об оптимальном решении для $N=7$, $S=733$

YuriiS пишет на форуме ПЕН:

Цитата:

Я нашел решение для n=7 (733) в самом начале конкурса. Как и обещал, при случае, "причешу" программу и опубликую (за исключением описания создания базы данных) на яхе вместе с описанием алгоритма.

Предложила ему ввести свой рекорд (он, может быть, не знал о такой возможности). Ждём.

[mertz]

I changed the sum to 767 and changed the -=6 to +=12.

I quickly had 1 fault results. I ran with the ; removed in the above code.

changed to 773 and += 18 and got a result.

https://www.dropbox.com/s/rddu003k1au0qkz/869.jpg

Not the correct sum, but it is a solution

[Nataly-Mak]

dimkadimon
помнится, вы предлагали свои вычислительные ресурсы для поиска оптимального решения (N=7).

dimkadimon в сообщении #756809 писал(а):

If you tell me which code to run then I can run it on some machines.

Jarek выложил код программы.
Вы знаете язык, на котором написана программа?
Поможете в этом проекте распределённых вычислений?

Всё-таки найти оптимальное решение очень интересно.

Pavlovsky
видела вас на ПЕН; надеялась, что вы напишете комментарий к сообщению YuriiS о том, что он нашёл оптимальное решение для N=7 (S=733). Но вы почему-то прошли мимо такого важного сообщения
Своё мнение на этот счёт пока не озвучиваю, но почти не сомневаюсь в нём.

-- Вс авг 25, 2013 09:09:20 --

mertz
вы можете вставлять изображения здесь.
Сверху есть кнопка Img; эта кнопка обеспечивает тег [img]...[/img] для ссылки на изображение (вместо ... прямая ссылка на изображение).
Но изображение не должно быть больше 800х800.

[mertz]

I tried. It said it could not determine image size. Maybe it was too big.

I have the app mostly written. You can select the sum. Number of threads to run. Still need to write the display. Right now the results go to files.

[Nataly-Mak]

mertz в сообщении #757499 писал(а):

I tried. It said it could not determine image size. Maybe it was too big.

Да, всё верно, ваше изображение слишком большое (больше чем 800х800).
Я тоже пыталась вставить ваше изображение, выдалось такое же сообщение - "не может определить размер изображения".

Цитата:

I have the app mostly written. You can select the sum. Number of threads to run. Still need to write the display. Right now the results go to files.

Выкладывайте ваше Приложение, я буду пробовать.

[Nataly-Mak]

Я предлагаю свой алгоритм поиска оптимального решения для N=7.
В алгоритме используется общая формула пандиагонального квадрата 7-го порядка, она была приведена здесь:
post744916.html#p744916
и кроме того используется шаблон.

Покажу конфигурацию квадрата:

a1 x1 a2 x2 a3 x3 a4
x4 a5 x5 a6 x6 a7 x7
a8 x8 a9 x9 a10 x10 a11
x11 a12 x12 a13 x13 a14 x14
a15 x15 a16 x16 a17 x17 a18
x18 a19 x19 a20 x20 a21 x21
x22 x23 x24 x25 x26 x27 x28

По этой конфигурации была получена общая формула.
Элемент а4 свободный.
Поскольку мы с Jarek установили, что для квадратов с магической константой $S<761$ обязательно использовать простое число 3, зафиксируем свободный элемент а4, присвоив ему значение 3.

Теперь представлю шаблон из вычетов по модулю 3 (этот шаблон получен по одному из решений Jarek):

2 2 1 2 1 1 0
2 2 1 2 2 1 2
2 1 2 1 1 1 1
1 2 1 2 2 2 2
2 2 1 2 2 2 1
1 2 2 2 2 1 2
2 1 1 1 2 1 1

Имеем 21 чисел равных 1(mod3) и 27 чисел равных 2(mod3). Вычет 0 соответствует числу 3.
Этот шаблон годится для построения квадратов с магическими константами S=0(mod3), например, 735, 741 и т.д.

Осталось представить массив простых чисел, из которых будем строить квадраты. Этот массив я составила из чисел, составляющих два решения Jarek: $S=761$ и $S=769$. В массиве 59 простых чисел:

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 193  197  199  211 223  227 229  233  239  241 251 257 263 269 271 277  281

Разобьём массив на две группы: числа, соответствующие вычету 1, и числа, соответствующие вычету 2.

Группа 1

7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241, 271, 277

(27 чисел)

Группа 2

5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281

(31 число)
Очень хорошо распределились числа. В шаблоне имеем 21 элемент из первой группы (будут выбираться из 27 чисел) и 27 элементов из второй группы (будут выбираться из 31 числа).
Всё готово. Осталось написать программу.
Я написала программу построения по общей формуле, но без использования шаблона. Выше показала некоторые результаты, полученные по этой программе (полуфабрикаты). До конца программу не выполнила - очень долго надо ждать.
Теперь напишу программу с использованием шаблона, это должно существенно уменьшить время выполнения, так как перебор сильно сокращается.

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

[Nataly-Mak]

Программу написала.
Пока только протестировала по известному решению.
Это известное решение Jarek с магической константой $S=777$, в скобках написаны обозначения элементов квадрата:

113 (a1) 257 (x1) 103 (a2) 101 (x2) 19 (a3) 181 (x3) 3 (a4)
179 (x4) 23 (a5) 43 (x5) 11 (a6) 167 (x6) 163 (a7) 191 (x7)
5 (a8) 73 (x8) 281 (a9) 199 (x9) 37 (a10) 31 (x10) 151 (a11)
67 (x11) 59 (a12) 61 (x12) 239 (a13) 71 (x13) 131 (a14) 149 (x14)
227 (a15) 83 (x15) 139 (a16) 41 (x16) 17 (a17) 47 (x17) 223 (a18)
79 (x18) 89 (a19) 137 (x19) 29 (a20) 293 (x20) 97 (a21) 53 (x21)
107 (x22) 193 (x23) 13 (x24) 157 (x25) 173 (x26) 127 (x27) 7 (x28)

Чтобы провести тестирование быстро (всего за 5 минут квадрат строится) я задала искусственно 10 первых свобобдных переменных, у меня в программе это такие элементы:
а5, a8, a9, a12, a18, x16, a15, a16, a17, x17 (перечислены в том порядке, в каком перебираются). Всего в программе 23 свободных элемента (один элемент зафиксирован).
Остаются 13 свободных переменных.

Программа выдаёт в точности такой квадрат.
Тут есть ещё такой приём: можно эти 10 свободных переменных выбирать случайным образом (задать конкретные значения - это слишком жёстко). Для остальных 13 переменных полный перебор. Конечно, случайный выбор есть случайный выбор, можно крутить программу сутками и не будет никакой определённости - есть решение или нет его. Тут надежда только на удачу.
Ну, а если заставить все 23 свободные переменные полностью перебираться, тогда, наверное, будет очень долго программа работать. Но опять же может повезти - решение может найтись задолго до завершения полного перебора.

Сейчас попробую поэкспериментировать с другой магической константой по этой программе.

-- Вс авг 25, 2013 17:11:36 --

Вот первый полуфабрикат - с магической константой 759:

251  167  37  101  7  193  3 
 47  23  43  11  257  199  179 
 5  0  281  157  73  0  79 
 61  59  0  107  0  269  137 
 227  29  139  41  17  83  223 
 19  89  173  131  263  13  71 
 149  127  0  211  53  103  67

В квадрате 5 дырок. При этом остались только зависимые элементы, то есть всё уже вычисляется. Только результаты вычислений плохие: есть не простые числа, есть отрицательные числа, есть двойняшки. В общем, полный букет.
Однако полуфабрикат нашёлся за пару минут.
Воспользовалась приёмом: случайный выбор первых 10 свободных переменных.

Очень сильно подозреваю, что решение с магической константой 759 существует.
YuriiS написал, что и решение с магической константой 733 существует (он его нашёл), однако показать почему-то не хочет

[Nataly-Mak]

И за несколько секунд найден квадрат с 4 дырками для магической константы 753:

131  239  37  101  13  229  3 
 149  23  103  17  263  127  71 
 5  97  281  79  67  0  199 
 43  59  0  197  0  107  191 
 227  11  139  41  29  83  223 
 31  53  179  137  233  73  47 
 167  271  0  181  113  109  19

И с 4 дырками с магической константой 747:

239  263  109  53  7  73  3 
 179  23  43  11  191  199  101 
 5  79  233  193  61  0  103 
 31  59  0  131  0  197  137 
 227  29  139  41  17  71  223 
 19  167  149  89  173  37  113 
 47  127  0  229  281  97  67

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

Магическая константа 741 и 4 дырки:

101  269  181  113  7  67  3 
 239  23  13  11  149  127  179 
 5  103  233  157  79  0  31 
 61  59  0  167  0  257  83 
 227  107  139  53  17  47  151 
 19  137  197  29  191  37  131 
 89  43  0  211  263  73  163

И последняя магическая константа кратная 3 - 735:

101  227  127  113  7  157  3 
 251  23  109  11  191  103  47 
 5  43  233  163  73  0  181 
 19  59  0  269  0  83  293 
 173  131  139  53  17  71  151 
 79  41  257  89  179  61  29 
 107  211  0  37  239  223  31 

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

[mertz]

I am probably not using Jarek's program correctly. Looking for 773 I found 869. 767 found 833. 761 found 797. Looking for 755 now. This is what the code was supposed to look for. The program finds results much faster with the ; removed in the above code.

[Nataly-Mak]

К сожалению, Jarek уехал отдыхать и вернётся только 10 сентября. Поэтому он не отвечает.
Я не знаю, будет ли у него возможность посетить форум во время отдыха.

dimkadimon пропал куда-то. Он мог бы помочь разобраться с кодом Jarek.

[Nataly-Mak]

Продолжаю эксперименты. Нашла квадрат с магической константой 735 с 3 дырками:

 137  131  229  113  79  43  3 
 71  23  103  11  263  67  197 
 5  241  233  19  31  97  109 
 73  59  0  89  0  269  47 
 173  107  139  53  29  83  151 
 37  167  101  251  149  13  17 
 239  7  0  199  41  163  211 

Это тоже несколько секунд искалось. Но здесь я уже случайно выбрала первые 16 свободных элементов (а не 10, как в первых экспериментах).
Пока я задаю случайный набор первых свободных элементов вручную.
Поясню, как это делается.

Вот у нас группа 2:

5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293

Например, свободные переменные a5, a8, a9, a12 принадлежат этой группе чисел (согласно шаблону).
Тогда я в соответствующих циклах пишу, что переменная а5 принимает значение 4-го члена в группе, переменная а8 - значение 1-го члена, переменная а9 - значение 25-го члена, переменная а12 - значение 9-го члена.
И так для всех 16 свободных переменных. Среди этих 16 переменных 5 принадлежат первой группе и 11 - второй группе. Надо, конечно, следить за тем, чтобы одной и той же переменной не присвоить значение одного элемента группы. В этом случае в квадрате будут двойняшки.
Всё это надо вставить в программу, чтобы случайный выбор выполнялся в программе.
Итак, на полный перебор остаётся всего 7 переменных. Это, я думаю, будет быстро выполняться. Но нужна большая удача, чтобы найти решение без дырок.

Да, полный перебор всех 23 свободных переменных за реальное время не выполнить даже с использованием шаблона. Надо искать другие, более эффективные алгоритмы.
Один из альтернативных алгоритмов имеет Jarek. Будем надеяться, что этот алгоритм позволит найти оптимальное решение.

[Nataly-Mak]

Кстати, дырки в приведённом решении, конечно, известны, элементы в дырках вычисляются, это числа 55, 143, -125:

137 131 229 113 79 43 3
71 23 103 11 263 67 197
5 241 233 19 31 97 109
73 59 55 89 143 269 47
173 107 139 53 29 83 151
37 167 101 251 149 13 17
239 7 -125 199 41 163 211

Кто умеет с дырками бороться, попробуйте убить
Понимаю, что дело непростое.
И в решении dimkadimon с магической константой 735 можно попытаться убить дырки, у него их всего две. Вот это решение:

(73,47,151,61,103,23,277),
(173,-59,239,43,3,269,67),
(163,101,149,157,17,59,89),
(53,131,29,181,233,71,37),
(271,97,19,41,79,223,5),
(197,167,11,139,107,83,31),
(-195,251,137,113,193,7,229)

В обеих дырках стоят отрицательные числа.

[dimkadimon]

mertz в сообщении #757606 писал(а):

I am probably not using Jarek's program correctly. Looking for 773 I found 869. 767 found 833. 761 found 797. Looking for 755 now. This is what the code was supposed to look for. The program finds results much faster with the ; removed in the above code.

Perhaps the ; should be there after all?

It probably doesn't work if you change the constants. Jarek told me that as it is, it should find a 1-error 755 every 2 minutes running 20 threads. In my experience it works correctly, but finds one every 10 minutes (he probably has a faster machine than me).

I will now start looking for 749.

[mertz]

The results are the same with and without the ;. without finds solutions much faster.

I probably made an error stuffing the program in a thread.