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

[dmd]

У меня первая единичка в строящемся случайно базисе обязательно привязана к последней обнаруженной дырке. Видимо опять закодил "что увидел то и спел".

[Pavlovsky]

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

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

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

[dimkadimon]

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

А зачем вам все квадраты с нулевой магической суммой? Чтобы получить любой пандиагональный квадрат, достаточно набора квадратов составляющих базис. Количество квадратов в базисе равно количеству независимых переменных в общей формуле. А это заметно меньше $N^2$. Описанный мною выше набор квадратов, содержит огромное количество вариантов базиса, в качестве своего подмножества.

Затем чтобы метод отжига быстрее работал. Я нахожу все базисные квадраты (из 0, 1 и -1) для N<=13. Все такие квадраты имеет два прямоугольника в виде

+1 -1
-1 +1

и их можно все найти методом перебора (я это уже писал). Для N>13 я нахожу первые 1000 случайных базисных квадратов. Но это только часть истории. Очень важны мелкие детали, которые могут сильно изменить мощность метода и в этом кроется настоящий секрет Jarek.

Я написал очень много кода потому что пробовал много разных идей до того как нашёл эту. Я написал 5000 строк в Java!

[Pavlovsky]

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

Затем чтобы метод отжига быстрее работал.

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

-- Пт авг 16, 2013 12:57:09 --

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

Для N>13 я нахожу первые 1000 случайных базисных квадратов.

А почему не все? По моим расчетам для N=13, квадратов с нулевой магической суммой и с 8 ненулевыми ячейками будет 169*12=2028. Можно рассмотреть и все.

-- Пт авг 16, 2013 13:06:00 --

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

[Nataly-Mak]

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

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

Может быть, лучше строить в качестве начального квадрата не квадрат из произвольных натуральных чисел, а квадрат из простых чисел (по алгоритму Россера - из примитивного квадрата) с несколькими не простыми числами (дырками)?

Как я помню, у меня данным методом квадраты даже с одной дыркой получались довольно быстро; пример тут был приведён с $S=1433$. Если взять меньше $S$, то дырок можно разрешить две или даже три.
dimkadimon тоже приводил пример квадрата 7х7 - с двумя дырками и с довольно маленькой магической константой.

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

Решение для N=7 и S=735 с двумя дырками:

(73,47,151,61,103,23,277),
(173, ? ,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),
(? ,251,137,113,193,7,229)

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

Кстати, теоретический минимум для N=7 равен 733.

[dimkadimon]

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

А почему не все? По моим расчетам для N=13, квадратов с нулевой магической суммой и с 8 ненулевыми ячейками будет 169*12=2028. Можно рассмотреть и все.

У меня таких квадратов около 9000.

[svb]

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

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

Что вы хотите от простого математика-любителя? Если даже автор не оценил глубины идей, изложенных в своей статье. Иначе нерегулярные пандиагональные квадраты из простых чисел были найдены еще в 2010 году.

Автора статьи в студию!
Почему он не оценил глубины своих идей? Пусть объяснится перед коллегами

Почему не оценил? Помню, какой восторг я тогда испытал, когда столкнулся с разностными преобразованиями и с некоторыми первыми странными выводами. И программа дальнейших исследований достаточно прозрачна: для начала переизложить статью Россера в иной интерпретации, затем попытаться от линейных пространств перейти к другим областям математики, к той же алгебраической геометрии. Работы очень много. Ощущение, что повезло наткнуться на достойный "цветок" меня не покидает до сих пор. За первыми идеями необходимо понять и найти более глубокие корни видимой сейчас картинки. Но жизнь есть жизнь и я на время отошел от задачи, но надеюсь продолжить работу позднее.

Там что-то есть, в этом я не сомневаюсь. Нужно работать и искать

[Pavlovsky]

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

У меня таких квадратов около 9000.

Кто то из нас двоих ошибается в расчетах.

[Nataly-Mak]

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

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

Вот, оказывается Pavlovsky не прав, автор оценил свои идеи.

Я вообще восхищалась исследованиями svb, начиная ещё с алгоритмов построения пандиагональных квадратов 6-го порядка. Это очень красивые алгоритмы!

Цитата:

Там что-то есть, в этом я не сомневаюсь. Нужно работать и искать

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

[Pavlovsky]

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

Вот, оказывается Pavlovsky не прав, автор оценил свои идеи.

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

[Nataly-Mak]

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

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

[dmd]

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

(Оффтоп)

[Nataly-Mak]

dmd
а вы используете метод, о котором в самом начале писал Pavlovsky?
Может быть, это поможет? Изменить положение тупиковой дырки, а заодно уменьшить магическую константу, затем применить опять обработку с помощью квадратов с нулевой магической константой.
Вот я уменьшила магическую константу в вашем квадрате с дыркой 235 на 38. В результате получился квадрат с магической константой 1047 и четырьмя дырками, два не простых числа и две двойняшки:

23   233   41   271   107   271   101
113   409   103   293   73   13   43
269   29   59   31   211   137   311
251   23   197   179   223   167   7
151   37   191   257   79   201   131
157   269   317   5   109   17   173
83   47   139   11   245   241   281

Дырки: 23, 201, 269, 245.
И таких новых исходных квадратов можно сделать вагон и маленькую тележку, причём с разным количеством, качеством и положением дырок.

P.S. Обработку квадрата выполнила с помощью следующего латинского квадрата

0 1 2 3 4 5 6
4 5 6 0 1 2 3
1 2 3 4 5 6 0
5 6 0 1 2 3 4
2 3 4 5 6 0 1
6 0 1 2 3 4 5
3 4 5 6 0 1 2

Во всех ячейках, в которых стоит 0, вычла 38.

[dmd]

Nataly-Mak
Нет, так ещё пока не пробовал. Если успею разобраться, то обязательно попробую.

Всё что сумел выжать, лишь на одну дырку меньше:

(1047)

[Nataly-Mak]

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

Например, вижу в статье такой квадрат 4-го порядка с 8-ю единичками:

0 1 -1 0
-1 0 0 1
1 0 0 1
0 -1 1 0

А вот для других чётных порядков не вижу подобных квадратов.

Здесь, конечно, опечатка в третьей строке должно быть: 1 0 0 -1.

Осенило, как строить подобные квадраты для следующих чётных порядков. Это же очень просто - путём окаймления строками и столбцами из нулей.
Например, квадраты порядков 6 и 8:

0 0 0 0 0 0
0 0 1 -1 0 0
0 -1 0 0 1 0
0 1 0 0 -1 0
0 0 -1 1 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 1 -1 0 0 0
0 0 -1 0 0 1 0 0
0 0 1 0 0 -1 0 0
0 0 0 -1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

И так далее для любого чётного порядка.
Для нечётных порядков можно взять квадрат порядка 7, приведённый Pavlovsky, и точно так же его окаймлять сначала до порядка 9, потом до порядка 11 и т.д.

Можно и по-другому: помещаем квадрат 4х4 в левый верхний угол строящегося нового квадрата, а всё окаймление нулями будет справа и снизу (так квадрат 7х7 сделан у Pavlovsky).

Остался не охваченным квадрат 5-го порядка:

0 1 -1 0 0
-1 0 0 1 0
1 0 0 -1 0
0 -1 1 0 0
0 0 0 0 0