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

[svb]

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

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

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

К сожалению в ближайшие дни я не смогу заниматься квадратами, т.к. буду занят другим делом.

-- Вс сен 05, 2010 15:48:34 --

Кстати, из Вашей статистики видно, что отклонения кратные 6 более перспективные. Выбор весовой функции от 9 отклонений интересен в теоретическом плане, как самостоятельная задача.
Т.к. отклонения "ходят парами", то при появлении 0 пару сразу выбрасываем. Если одно из отклонений дает 1, то в 9-ку подобная пара не может входить более одного раза и т.д. В рассмотренных ранее примерах отклонений $p, 0, 0, -p$ пары входили по 6 раз, поэтому при статистике $<6$ претенденты отсекались. Фактически уже при 7 перебор не находил решения.

[Nataly-Mak]

Ну вот, и вы меня покидаете

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

Но вот квадраты я набрала, отклонения в них всем вашим условиям удовлетворяют. Но как теперь решётку-то заполнить? Чего-то тут мне не хватает
Посмотрите, пожалуйста и подскажите, у меня уже завихрение мозгов.
Вот набор из 9 квадратов 2х2 (магическая константа 486):

11 37     3 67     5 23     13 191     19 83     7 139     59 43     5 43     23 31
139 137  61 193   199 97     41 79     29 193   47 131   109 113   109 167   167 103

Я думала, что у меня квадрат готов уже, ан нет! Стала записывать квадраты в матрицу 6х6 и ничего не получается.

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

[svb]

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

Но как теперь решётку-то заполнить? Чего-то тут мне не хватает

Увы, каждый квадрат для уже выбранного $p$ можно вставить 4-мя способами, но и этого может не хватить, тогда его нужно заменить на другой с тем же $p$. Здесь, в общем-то, наступает "классический" перебор по 12 независимым элементам. Просто выбор этих элементов достаточно сильно сужен. Работая с программой perebor2, Вы могли наблюдать этот перебор. Он терпимый по скорости, но ... если выполняется для одной 9-ки. Почему и важно правильно подсунуть эту 9-ку - объем перебора должен быть достаточно большим, чтобы позволить получить магические суммы по строкам и по столбцам. Только о диагоналях не нужно беспокоиться, они получатся автоматически.

Цитата:

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

Так и должно быть, максимальное простое число не стоит ограничивать, она и так не будет больше $Sb$, а объем перебора, если он оказывается большим, уменьшать нужно другим способом.

[Nataly-Mak]

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

Тогда весь процесс можно разбить на 2 этапа:
1. нахождение потенциальных наборов из 9 квадратов;
2. построение квадрата из этих наборов.

Кстати, я пыталась варьировать числа в квадратах 2х2, чтобы получить магические суммы в строках квадрата 6х6, но вручную это сделать сложно, да и вообще не всегда возможно. Может быть, с данным набором квадратов так ничего и не получится.

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

[svb]

Увы. Но тотальный перебор по 16 независимым параметрам просто зашкаливает. У нас еще не исследованы допустимые 9-ки, здесь могут оказаться полезными методы Павловского. Посмотрим

[Nataly-Mak]

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

[svb]

Кстати, у пандиагональных квадратов 6 порядка большой плюс - их много, а нам нужен хотя бы один.

[Nataly-Mak]

Да, их много для такого массива, для какого они вообще существуют
Но как узнать, существуют ли вообще?

[maxal]

Я тут неспешно отсеял магические суммы 43246, 45514, 48160 для идеального квадрата 7x7 из смитов. Сейчас прорабатывается 51814.

[Nataly-Mak]

maxal писал(а):

Я тут неспешно отсеял магические суммы 43246, 45514, 48160 для идеального квадрата 7x7 из смитов. Сейчас прорабатывается 51814.

Почему неспешно?

Моя программа построения идеального квадрата 7-го порядка (основанная на построении примитивного квадрата) даёт ответ на этот вопрос за одну секунду.
Так, для магической константы 51814 идеального квадрата по мнению моей программы не существует.
Число в центральной ячейке 7402, количество комплементарных пар 25.

Я уже проверила (между делом) для простых чисел до центрального числа 2243 (магическая константа 15701). Идеальный квадрат пока не найден.
Программа работает секунды, вот только один недостаток у неё: надо вводить каждое новое центральное число. Это требует моего постоянного присутствия. Всё собираюсь её подкорректировать, чтобы всё шло автоматически, но не хватает времени.

Кстати, я задала вам вопрос о шаблонах для пандиагональных квадратов 6-го порядка из простых чисел, а ответа не получила. Вопрос касался количества различных (неизоморфных) шаблонов с использованием простого числа 3. Вы писали, что такой шаблон всего один. Я привела второй шаблон, который, по-моему, не изоморфен вашему шаблону.

Ещё у нас остались две магические константы для простых чисел (пандиагональные квадраты 6-го порядка): 486 и 498, для которых не выяснен вопрос существования пандиагонального квадрата.
svb предложил очень хороший алгоритм построения пандиагональных квадратов 6-го порядка, но пока не реализован.

-- Пн сен 06, 2010 06:00:22 --

Вот предлагаю программу построения идеального квадрата 7-го порядка:
http://www.natalimak1.narod.ru/mk/ID7A.rar

Это для простых чисел (программу можно использовать и для смитов, но тогда во входной файл MK.txt надо поместить массив смитов).

В архиве:
1. программа KOMPLA.EXE (определяет количество комплементарных пар для заданного центрального числа); комплементарные пары будут записаны в файл MK3.TXT.
2. программа ID7A.EXE (построение идеального квадрата 7-го порядка с заданным центральным числом и из найденных комплементарных пар);
3. входной файл MK.TXT с массивом простых чисел:
4. пакетный файл run.bat (обеспечивает многократное повторение двух программ).

Первая программа запрашивает центральное число (число в центральной ячейке квадрата, это число равно $S/7$, $S$ - магическая константа квадрата; понятно, что для квадратов из простых чисел центральное число должно быть простым числом, а для квадратов из смитов - смитом), надо ввести это число. Программа выдаст на экран константу комлементарности (первое число) и количество комплементарных пар (второе число).
Вторая программа запрашивает количество комплементарных пар, надо ввести это количество (второе число, выданное первой программой). Всё, больше ничего не надо, программа выполнится и выдаст идеальный квадрат, если он будет найден.
Программа работает до первого найденного квадрата, он будет выведен на экран и записан в файл MK10.TXT.

Следует заметить, что сейчас в программе задействован массив из 2500 простых чисел. Если выполнять программу для очень больших магических констант, то центральное число будет тоже большим и количество комплементарных пар будет считаться неправильно. Это надо оценивать непосредственно (по величине задаваемых магических констант). Тогда надо будет увеличивать массив простых чисел (для этого придётся изменить программу kompla.exe).

Ах, забыла сказать. Важное уточнение: программа выведет примитивный квадрат, а не идеальный. Из полученного примитивного квадрата надо получить идеальный с помощью преобразования Россера.

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

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

[Nataly-Mak]

Эх, жалко, что svb в "отгулы" ушёл

Используя статистику и программу поиска отклонений, нашла замечательный комплект отклонений:

-12 -84 -6 18 78 12 -72 -24 -66

Ну, насколько он замечательный, покажет проверка по программе построения пандиагонального квадрата 6-го порядка из 9 квадратов 2х2 с такими отклонениями.
Количества пар для этих отклонений хорошие, самое меньшее - 6 пар (для отклонения -84), наибольшее - 17 пар (для отклонения 78).
Всё это для магической константы 486.

[Nataly-Mak]

Да, я таких сложных для реализации алгоритмов ещё не встречала
svb гуляет, дал сложнейший алгоритм, а сам ушёл

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

11 5  7 157 227 79
0  0  0  0  0  0
0  0  0  0  0  0
17 19 89 139 73 149
0  0  0  0  0  0
0  0  0  0  0  0

Прямо весь процесс приходится ручками прощупывать. И пока ничего! Всего две строки

[Nataly-Mak]

Буквально вгрызаюсь в этот квадрат

11 5 7 157 227 79
167 29 137 47 23 83
31  0  0  71  0  0
17 19 89 139 73 149
97 61 67 13 211 37
163  0  0  59  0  0

Неужели не получится?

[maxal]

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

Почему неспешно?

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

Вот поэтому и неспешно. Моя программа не опирается на недоказанные факты.

-- Mon Sep 06, 2010 11:49:00 --

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

Кстати, я задала вам вопрос о шаблонах для пандиагональных квадратов 6-го порядка из простых чисел, а ответа не получила. Вопрос касался количества различных (неизоморфных) шаблонов с использованием простого числа 3. Вы писали, что такой шаблон всего один. Я привела второй шаблон, который, по-моему, не изоморфен вашему шаблону.

Я несколько потерял нить обсуждения - укажите прямую ссылку на ваш вопрос/шаблон.

[Nataly-Mak]

maxal в сообщении #350138 писал(а):

Моя программа не опирается на недоказанные факты.

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

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

Цитата:

Я несколько потерял нить обсуждения - укажите прямую ссылку на ваш вопрос/шаблон.

post347084.html#p347084