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

[Nataly-Mak]

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

n = 3     S = 822   существует (книга М. Гарднера)
n = 4   S = 1195   существует (автор tolstopuz)
n = 5   S =1831   существует (автор Бодигрим)
n = 6    S = 2460   ?
n = 7   S = 3720   ?
n = 8   S = 5856   ?
n = 9   S = 8737   ?
n = 10   S = 12202   ?
n = 11   S = 16335   ?
n = 12   S = 21333   существует (автор Nataly-Mak)
n = 13   S = 27612   существует
n = 14   S = 35185   существует
n = 15   S = 43968    существует
n = 16   S = 54013   существует

Минимальность магических констант, начиная с порядка 6, надо проверить. Я определяю эти константы простым подбором, у меня пока нет такой программы, поэтому могла ошибиться. Может быть, существуют меньшие константы, чем найденные мной. Квадраты, начиная с порядка 12, строятся очень быстро по программам ice00. А вот с квадратами порядков 6 - 11 проблемы. Даже квадрат 11-го порядка уже никак не хочет строиться. И по своей программе пробовала. Полумагических квадратов получается очень много, а магический - никак. Продолжить серию этих квадратов дальше, наверное, не составит труда. Сложная задача - квадраты порядков 6 - 11. Подключайтесь к её решению!

[ice00]

If you use the program with high order, remember to look if there was error in generating result.

Here one example of the error message you got:

Verify that square is magic:
rows    @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
columns @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@0
diag \: @
diag /: @

ERROR in verify: there's an error not view before now

[Nataly-Mak]

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

-- Пт окт 16, 2009 12:09:15 --

Составила примитивную программку для определения минимальной магической константы квадрата из смитов (кстати, её можно использовать и для квадратов из простых чисел; надо будет и все константы наименьших квдаратов из простых чисел проверить, может быть, тоже улучшения найдутся). Эту программу можно составить с более высокой точностью, но тогда она будет дольше работать. Но даже примитивная программка сразу обнаружила одну неправильную магическую константу: для порядка 7 получилась минимальная константа 3719 вместо 3720, что я нашла раньше подбором. Кроме того, программа нашла для некоторых порядков два варианта массива, подбором я эти варианты не увидела.
Вот привожу таблицу - уточнённую и дополненную до порядка 20 включительно. Все квадраты, начиная с порядка 12, построены. Для порядков 14 и 16 квадраты построены для обоих вариантов массива.

n = 3   S = 822   существует (книга М. Гарднера)
n = 4   S = 1195   существует (tolstopuz)
n = 5   S = 1831   существует (Бодигрим)      
n = 6    S = 2460   ?
n = 7   S = 3719   ?
n = 8   S = 5856   ?
n = 9   S = 8737   ?
n = 10   S = 12202   ?
n = 11   S = 16335   ?            два варианта массива
n = 12   S = 21333   существует (Nataly-Mak)
n = 13   S = 27612   существует
n = 14   S = 35185   существует         два варианта массива
n = 15   S = 43968    существует
n = 16   S = 54013   существует         два варианта массива
n = 17 S = 65464   существует
n = 18 S = 78281   существует
n = 19 S = 92422   существует
n = 20 S = 107933   существует

Удивительное дело: квадрат порядка 12 строится в долю секунды, а квадрат порядка 11 совсем не хочет строиться. Я ждала 40 минут, нет квадрата! Попробовала все методы, кроме $c3$. Не знаю, что такое параметр $t$ и каким числом его надо задавать. В инструкции написано так: $-t<nn>$, где $nn$ - это количество выполняемых циклов, после которых происходит таймаут. Какое значение надо задавать для $nn$? И обязательно ли его задавать?
Свою программу (и программу ice00 тоже) попробовала для обоих вариантов массива. Ничего! Хотя в моей программе полумагических квадратов очень много получается. Что же это за причина такая? Всего в один порядок разница, квадрат 12-го порядка строится, а квадрат 11-го порядка нет. Может быть, не существует магического квадрата из таких массивов чисел? Но однозначного ответа здесь нет. Вполне возможно, что квадрат такой существует, но просто не находится так быстро, как квадраты больших порядков.
Приведу данные для построения этого злосчастного квадрата, на который я уже ухлопала уйму времени.
Массив чисел: 4, ..., 2964, но...
1-й вариант массива: заменить число 2934 на число 2970;
2-й вариант массива: заменить число 2944 на число 2970 и число 2964 на 2974.
Магическая константа равна 16335 (для обоих вариантов массива). Минимально возможная константа наимеьшего квадрата 11-го порядка из смитов равна 16332.
Может быть, кто-нибудь попробует построить этот квадрат по программе ice00?

[ice00]

Цитата:

Попробовала все методы, кроме $c3$. Не знаю, что такое параметр $t$ и каким числом его надо задавать. В инструкции написано так: $-t<nn>$, где $nn$ - это количество выполняемых циклов, после которых происходит таймаут. Какое значение надо задавать для $nn$? И обязательно ли его задавать?

$C3$ can be used without that parameter.
If $-t<nn>$ is specify, when the program goes in recursion to all the permutation that will make the diagonal magic, it stops to recurse after $<nn>$ cycles.
This is to prevent (in high order) to check all the permutation (that will require more time) and to goes to another square to check.
Method $C3$ is the most similar to the one I use in Pascal program for making magic square and it works fine (even using with that parameter) even at order 35. Then I make all the other methods when I see the difficult of order 124.

So, if you don't use that $-t<nn>$ in $C3$, you will scan all the permutation, instead, adding that value you limit the number of recursion to use.
The value to use is just an empiric choice: start with some low value and increase them if you want more recursion.

[Nataly-Mak]

ice00
Спасибо за разъяснения. Сейчас попробую ещё метод $c3$.
А вы не хотите попробовать мой трудный квадрат порядка 11? Данные для него в предыдущем посте приведены. Я уже отчаялась его построить

-- Пт окт 16, 2009 13:40:25 --

О! Есть! Методом $c3$ квадрат сразу построился (за 3 секунды).

825 1449111123262475562 26881633895 228685  
729 1966913 12822614852 627 391 187226052484
18222067483 265 184229642970535 166 2576645 
1086319 706 236212552173666 438 278519622583
915 257824611376355 28882155222727  663 690 
1507985 19522373762 778 207923662218454 861 
2911648 2182274511651858922 634 2038274 958 
1776382 1736294494  192127222409121 1642588 
346 188112194   28391755202 517 267919352958
190322651894636 255658  728 24341626654 1581
25151795167822  378 526 576 2751190812842902

Но тут проблема с форматом вывода результата - числа сливаются. Вы мне продублировали программы для порядков начиная с 20. Пожалуйста, продублируйте программы меньших порядков (6 - 19).
Сейчас попробую квадрат 10-го порядка этим же методом построить.

-- Пт окт 16, 2009 18:00:04 --

Наконец-то этот "трудный" квадрат поддался:

1935 2484 915  2902 1626 2286 265  1921 690  648  663  
2182 27   1903 2409 346  1755 1881 202  2751 985  1894 
2173 4    1822 121  2578 1633 654  2218 517  1776 2839 
2515 2556 913  1284 576  1962 562  274  2155 1165 2373 
2067 1255 634  2964 22   94   2722 1449 2362 2038 728  
588  1966 1642 526  58   2614 2679 2785 355  2227 895  
645  762  1581 2366 2475 2461 706  861  1795 825  1858 
1952 778  2265 2079 2888 85   2944 958  378  1842 166  
922  2434 319  666  2583 391  2688 1219 2970 636  1507 
627  2958 1736 483  438  1678 852  1872 454  2911 2326 
729  1111 2605 535  2745 1376 382  2576 1908 1282 1086

Квадраты 11-го порядка построились для обоих вариантов массива.
Теперь осталось всего 5 "трудных" квадратов в этой серии - порядков 6 - 10.
Квадрат 10-го порядка снова не строится, даже методом $с3$

[Nataly-Mak]

ice00
Забыла вас вчера поблагодарить за вторично присланные программы. По вашей программе удалось построить наименьший магический квадрат 11-го порядка из смитов (для двух вариантов массива), о чём я уже сообщила.
Теперь пытаюсь построить подобный квадрат 10-го порядка. Снова никак не строится квадрат! У меня работают одновременно две программы: ваша и моя (я раньше даже не знала, что можно выполнять сразу две программы ). Но ни одна программа результата не даёт. Ваша программа и методом с3 не даёт результата.
Хочу предложить одну идею. Как я уже говорила, для моей программы исходным является набор строк, сумма чисел в каждой строке равна магической константе квадрата. Если я введу в свою программу готовый магический квадрат, программа мгновенно возвратит мне этот квадрат и сообщит, что квадрат построен. Я попробовала проделать такое же с вашей программой: ввела в качестве исходного массива готовый магический квадрат (эксперимент проводился с программой для порядка 10). Ваша программа не возвратила этот магический квадрат! Это очень любопытный факт.
Теперь представьте: по моей программе получается очень много полумагических квадратов; например, вот сейчас, когда я работаю над построением "трудного" квадрата 10-го порядка из смитов. Что если исходным массивом для вашей программы сделать какой-нибудь полумагический квадрат, а не просто массив чисел? И попытаться превратить этот полумагический квадрат в магический. Может быть, такая программа будет работать эффективнее? Ну, например, можно выполнить тотальную перестановку всех строк и столбцов, это может привести к возникновению магического квадрата. Или ещё какие-то способы применить.
Замечу, что моя программа, получив полумагический квадрат, тоже пытается превратить его в магический, но при этом использует не все возможности для такого превращения. Например, выполнить полную перестановку всех 10 строк на Бейсике нереально (очень долго!), не говоря уже о перестановке всех строк и столбцов.
Эта идея для всех! И большая просьба предлагать свои идеи для построения наименьших квадратов из смитов порядков 6 - 10.

[ice00]

My program always starts creating a random square with the given set of numbers, so this is why you will not get magic square from the set you insert.
I had hack the program using C3 methods only for diagonal, assuming the sqare was already built by the sequence intruduced, but never find solution (I have use it only with one case, maybe I need to test more with your sequences of numbers)

[Nataly-Mak]

Я поняла так ваше сообщение, что вам бы надо попробовать ещё другие варианты полумагических квадратов (такой эксперимент вы уже проводили, но для квадрата 6-го порядка). Разумеется, я могу дать вам для такого эксперимента много полумагических квадратов 10-го порядка.
У меня встречное предложение: не могли бы вы сделать программу для построения магического квадрата 10-го порядка, используя в качестве исходного массива полумагический квадрат? Тогда вам надо будет делать в этом квадрате только диагонали. Такая программа должна иметь "СТОП", то есть она может совершить некоторое конечное число операций и сообщить, что магический квадрат не найден. Затем я ввожу другой полумагический квадрат и снова выполняю программу. Вы поняли мою идею?
Вот, например, у меня есть подобная программа для квадратов 6-го порядка. На входе - полумагический квадрат; в программе выполняется полная перестановка всех строк и столбцов (для порядка 6 я могу это выполнить довольно быстро). Если это не приводит к возникновению магического квадрата, программа останавливается и сообщает, что квадрат не найден. Если же магический квадрат получится, программа его выдаст. Для порядка 10 такая программа на Бейсике не выполняется за разумное время.

[ice00]

I can do this for order 10. I will start to code the program within 3 ours.

[dezdlisa]

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

[ice00]

Windows executable:
http://www.4shared.com/file/138533403/e526403c/pms11-20.html
http://www.4shared.com/file/138534021/a3c0d3f7/pms21-30.html
http://www.4shared.com/file/139813131/46e7fb32/pms31-40.html
http://www.4shared.com/file/138532176/647a87fa/pms4-10.html
http://www.4shared.com/file/140624365/405970d3/pms41_50.html

Source of programs (not the last one with all the order up to 50), but with the main core:
http://digilander.iol.it/ice00/download/pms_new3.zip

[dezdlisa]

Огромное спасибо ice00, теперь можно будет в свободное время занятся этим вопросом.

[Nataly-Mak]

dezdlisa в сообщении #252434 писал(а):

Просмотрел весь свой материал и убедился, что ни один мой метод не строит совершенных квадратов.

Если вас интересуют совершенные магические квадраты, посмотрите мою статью о них. Статья написана в 4 частях. Где искать статью, вы знаете. В статье есть разработанный мной метод построения совершенных квадратов любого чётно-чётного порядка (совершенные квадраты существуют только для таких порядков). Алгоритм реализован на Бейсике. Кроме того, совершенные квадраты можно строить методом латинских квадратов. Этот метод вы тоже найдёте на моём сайте.

[dezdlisa]

Nataly-Mak писал(а):

n = 3 S = 822 существует (книга М. Гарднера)
n = 4 S = 1195 существует (tolstopuz)
n = 5 S = 1831 существует (Бодигрим)  
n = 6  S = 2460 ?
n = 7 S = 3719 ?
n = 8 S = 5856 ?
n = 9 S = 8737 ?
n = 10 S = 12202 ?
n = 11 S = 16335 ?    два варианта массива
n = 12 S = 21333 существует (Nataly-Mak)
n = 13 S = 27612 существует
n = 14 S = 35185 существует   два варианта массива
n = 15 S = 43968  существует
n = 16 S = 54013 существует   два варианта массива
n = 17 S = 65464 существует
n = 18 S = 78281 существует
n = 19 S = 92422 существует
n = 20 S = 107933 существует

Может я ошибаюсь, но если взять массив 4...706 для квадрата 6-го порядка, то сумма всего массива дает нам число 14737 и если мы поделим его поровну на шесть строк, то мы не получим минимальную константу квадрата, равную 2460, а получим 2456,1(6).
А вот если мы возьмем массив 346...958, то сумма этого массива равна 23238, которая делится на 6 и мы получаем минимальную предполагаемую константу квадрата 6-го порядка, равную 3873.
Таким образом, массив 346...958 является первым массивом, сумма которого делится на 6. Если я прав, то это и будет доказательством тому, что минимальный квадрат из смитов может быть только с константой 3873. Если я не прав, то нужно все таки найти минимальный квадрат с константой 2460.

[Nataly-Mak]

dezdlisa в сообщении #252463 писал(а):

Если я не прав, то нужно все таки найти минимальный квадрат с константой 2460.

Найдите
Вы не смешивайте два вида наименьших квадратов из смитов: 1) из последовательных смитов; 2) из произвольных смитов.
Посмотрите мою таблицу для квадратов из последовательных смитов (она чуть раньше была приведена), в ней вы найдёте константу 3873 для квадрата 6-го порядка, которую вы вычислили. Кстати, квадрат с такой константой из последовательных смитов тоже пока не построен и неизвестно, существует ли он вообще. Квадрат 6-го порядка из смитов вообще мне известен пока только один, но у него магическая константа имеет большое значение. Этот квадрат я построила методом, изложенным в книге Чебракова.