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

[mertz]

64-bit Windows: https://www.dropbox.com/s/rjbx2ot427mkbr9/Pan737.exe

64-bit Linux: https://www.dropbox.com/s/tfdquiu14lcbzaz/panlinux737

[dimkadimon]

После 12.5 дней так и не нашёл решение для 743. Нашёл 1026 решений с одной ошибкой. Останавливаю все программы, пусть компьютер отдыхает.

[whitefox]

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

Интересно, а сколько требуется времени чтобы проверить один из шаблонов и возможно ли это вообще?

Массив №2 имеет следующее распределение вычетов по модулю 12:

1 -- 10
3 -- 1
5 -- 12
7 -- 13
11 -- 13

Вот один из шаблонов:

B B 5 B B 5 7
 B 7 5 7 1 7 B
 7 7 1 B 5 B 7
 7 7 B 7 B 7 B
 5 B 5 B 7 5 5
 7 5 5 1 1 1 5
 1 1 5 1 1 1 3
здесь B означает 11.

Свободные переменные:

$x_{23},x_{24},x_{25},x_{26},x_{27},x_{28},x_{30},x_{31},x_{32},x_{33},x_{34},x_{35},$ $x_{37},x_{38},x_{39},x_{40},x_{41},x_{42},x_{44},x_{45},x_{46},x_{47},x_{48},x_{49}$

Положение тройки фиксировано ($x_{49}$). Среди остальных свободных переменных вычеты по модулю 12 распределены так:

1 -- 7
5 -- 7
7 -- 4
11 --5

Всего имеется $\mathrm P_{10}^7=604800$ вариантов выбора 1,
$\mathrm P_{12}^7=3991680$ вариантов выбора 5,
$\mathrm P_{13}^4=17160$ вариантов выбора 7,
$\mathrm P_{13}^5=154440$ вариантов выбора 11.

То есть полная проверка этого шаблона потребует рассмотреть примерно $6{,}398\cdot10^{21}$ вариантов.

[dimkadimon]

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

То есть полная проверка этого шаблона потребует рассмотреть примерно $6{,}398\cdot10^{21}$ вариантов.

Значит мы даже один шаблон не сможем проверить :(

[whitefox]

С шаблонами по модулю 60 ситуация иная.

Массив №2 имеет следующее распределение вычетов по модулю 60:

1 -- 2
3 -- 1
5 -- 1
7 -- 3
11 -- 4
13 -- 3
17 -- 3
19 -- 4
23 -- 2
29 -- 3
31 -- 3
37 -- 3
41 -- 2
43 -- 3
47 -- 4
49 -- 2
53 -- 3
59 -- 3

Имеется некоторая свобода в выборе свободных переменных.

Пусть мы выбрали свободные переменные так, чтобы вычеты по модулю 60 распределились среди них следующим образом:

1 -- 2
3 -- 1
5 -- 1
7 -- 2
11 -- 0
13 -- 2
17 -- 1
19 -- 0
23 -- 2
29 -- 2
31 -- 1
37 -- 1
41 -- 2
43 -- 1
47 -- 0
49 -- 2
53 -- 2
59 -- 2

Тогда полная проверка такого шаблона потребует рассмотреть 10077696 вариантов.

[trurl]

I switched back to the older pan.exe program (the first version with random seed) and S=737 popped up after running 13 days. 249 1-holes.

[dimkadimon]

Congratulations Wes!!! Now we just need to find 733 and we are done :)

[dimkadimon]

Для тех кто не знает, Al Zimmermann начал новый конкурс, который обсуждается тут: topic76097.html

[Pavlovsky]

Цитата:

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

Jarek Wroblewski нашел таки оптимальное решение для N=7!

[dmd]

Грандиозно!!!



Мечтаю, надеюсь изучить статью с описанием алгоритма, давшего это решение.

[korolev]

Для чего нужны Дьявольские магические квадраты ?

[Pavlovsky]

Изгонять Дьявола.

[korolev]

А такой нетрадиционный дьявольский и причем совершенный магический квадрат сможете строить?
(1,78,8,80,6,73),(54,31,47,29,49,36),(64,15,71,17,69,10),(72,13,65,11,67,18),(46,33,53,35,51,28),(9,76,2,74,4,81)

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

[Nataly-Mak]

Замечательные решения Jarek Wroblewski, найденные уже после конкурса - это пандиагональные квадраты из простых чисел и числа 1, можно посмотреть здесь:

http://www.primepuzzles.net/puzzles/puzz_699.htm

Найдены решения до порядка n=13 включительно, однако наименьший опять же только для порядка n=7:

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

Конкурс закончился и запал у всех закончился
А ведь тут ещё решать и решать!
Даже для порядка n=8 не доказано, что найденное решение минимальное (что с числом 1, что без него).

Когда переписывались немного с Jarek после конкурса, я изложила ему свой алгоритм поиска решений для n=8 и попросила помочь с программной реализацией. Давно это было, летом ещё. Он написал тогда, что в данный момент очень занят, но, возможно, вернётся к этой задаче (не обязательно с моим алгоритмом, можно и с другими подходами).
Ну, скоро и новое лето наступит, а времени на эту задачу так и не нашлось.
Увы и ах!