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

[Nataly-Mak]

Наборы - это здорово. Спасибо!

А если сразу ПМК генерировать?
Я сейчас над этим думаю. По-моему, исходя из общего вида ПМК, можно сделать программу генерации сразу ПМК, а не наборов из 8 строк.

Получив ПМК, сразу проверяем их по вашей программе.
А наборы надо ещё в ПМК превращать, что довольно долго (у меня, по крайней мере).

-- Сб апр 10, 2010 12:39:18 --

Кстати, имея общий вид ПМК, вы можете по своему алгоритму перемешивания строк и столбцов проверить возможность превращения такого ПМК в магический квадрат. Тогда и нет смысла генерировать такие ПМК, которые всё равно в магический квадрат не превратятся

[Nataly-Mak]

Написала часть программы генерации ПМК.
Взяла вот такой вид ПМК:

6 6 6 4 4 4 4 8
4 4 4 0 0 4 4 4
4 6 6 0 0 4 0 4
8 4 6 4 6 4 4 6
6 4 6 4 6 6 4 6
6 8 6 4 4 4 4 6
4 6 4 4 4 3 4 4
4 4 4 4 0 4 0 4

Пока запрограммировала только расстановку чисел с остатками 0, 6, 8. Ну, с остатком 3 число единственное и оно всегда стоит на определённом месте.
Вот такой первый квадрат выдала программа:

438  483  627  0  0  0  0  728 
 0  0  0  27  378  0  0  0 
 0  636  645  576  648  0  666  0 
 1376  0  654  0  663  0  0  690 
 762  0  825  0  852  861  0  915 
 1086  1736  1284  0  0  0  0  1581 
 0  1626  0  0  0  588  0  0 
 0  0  0  0  729  0  1449  0

Осталось сделать расстановку чисел с остатком 4, таких чисел 36. Сейчас вместо этих чисел стоят нули. Ну, и, конечно, сделав очередной вариант расстановки, надо проверять суммы чисел во всех строках и столбцах.

Итак, схема генерации ПМК вроде понятна. Однако сгенерировать все ПМК проблематично. Ещё сложнее их все проверить по программе svb.
Тут ведь надо не по одному квадратику проверять, а сразу несколько сотен или даже тысяч. Точно так, как ice00 проверял по своей программе ПМК 9-го порядка, которые я ему посылала, их было в одном случае 1197, а в другом более двух тысяч.

[Nataly-Mak]

С ходу не получилось сделать программу генерации ПМК по представленной выше схеме. Пять строк программа делает быстро, а на шестой мёртво встаёт. Слишком много вложенных циклов и переменных. Вот результат первого прохода для пяти строк:

 438  483  627  4  265  1633  1678  728 
 22  166  1219  27  378  1255  1282  1507 
 535  636  645  576  648  985  666  1165 
 1376  58  654  346  663  958  1111  690 
 762  85  825  634  852  861  922  915 
 1086  1736  1284  0  0  0  0  1581 
 0  1626  0  0  0  588  0  0 
 0  0  0  0  729  0  1449  0

Надо придумывать другую схему.

svb
проверила 14 ваших наборов, получила 5 ПМК (как я уже говорила, это не все возможные ПМК, моя программа не делает полную “выжимку” всех ПМК из набора). К сожалению, ни один ПМК не превратился в МК.

Ну, если проверять по 10 наборов в день, то за 50 дней все ваши наборы проверю Хотя вероятность получить МК очень мала.

Итак, мене видятся три пути решения данной задачи:

1. как говорит 12d3, надо сделать более эффективную программу генерации ПМК разных видов;
2. попытаться доказать по общему виду ПМК, представленных в виде остатков по модулю 9, что их невозможно превратить в МК;
Это можно попробовать сделать по алгоритму перемешивания строк и столбцов, который даёт все потенциальные диагонали. Ни один из ПМК с константой 5856 не имел больше 7 потенциальных диагоналей. Напомню, что ПМК с константой 5861, из которого получен МК, имел 17 потенциальных диагоналей.
3. придумать принципиально новый алгоритм построения МК 8х8.

[Nataly-Mak]

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

Мне понравился подход 12d3. Для квадрата 8х8 с константой 5856, если я не ошибаюсь, существует всего 3 вида:

a   4 4 4 6 6 6 6 6
b   4 4 4 4 6 6 6 8
c   4 4 4 4 4 6 8 8
d   3 4 4 4 4 4 4 6
e   0 6 6 6 6 6 6 6
f    0 0 4 4 4 4 4 4
g   0 0 0 4 4 4 6 6

У меня получились ещё такие комбинации:

h   0 0 0 4 4 4 4 8
i   0 3 4 4 4 4 6 8
j   0 4 4 6 6 6 8 8
k   0 3 4 4 4 6 6 6

Видов ПМК получилось уже 4. Это я расписала всего 7 из имеющихся у меня ПМК. Думаю, что если расписать все, которые у меня есть, ещё что-нибудь найдётся.

[svb]

1:
  915  438   22 1284  861 1219  762  355
  319  728   94 1581  690  517  645 1282
  666  274 1626  121 1086  729  706  648
   27 1678 1633  166  562  454  958  378
  627  265  778 1736  483  913  663  391
 1507  202  588   85  535  922  852 1165
 1449  895    4   58  985  576  634 1255
  346 1376 1111  825  654  526  636  382

2:
   58  895 1255    4  576  985 1449  634
 1284 1376  391   22  913  861  346  663
 1581  438  382  778  517  483  915  762
  166  274  378 1633 1219  562  666  958
   85  265 1165  588  454 1086 1507  706
  121 1678  648 1111  729  690   27  852
  825  202  355 1626  922  654  627  645
 1736  728 1282   94  526  535  319  636

3:
   58  895 1255    4  576  985 1449  634
 1581 1376  391   22  517  861  346  762
 1284  438  382  778  913  483  915  663
  166  274  378 1633 1219  562  666  958
   85  265 1165  588  454 1086 1507  706
  121 1678  648 1111  729  690   27  852
  825  202  355 1626  922  654  627  645
 1736  728 1282   94  526  535  319  636

4:
  438   22  915 1581 1219  355  636  690
  274  588 1507   85  922 1282  663  535
  895  778  666  166  576 1255  958  562
  728 1633  346  825  526  382  762  654
  202 1626  319 1736  454  391  645  483
 1376    4  627   58  913 1165  852  861
 1678   94 1449  121  517  378  634  985
  265 1111   27 1284  729  648  706 1086

5:
  915   22  274 1736 1165  636  454  654
  319  588  895  166 1282  852 1219  535
   27 1111 1678  121  378  634  922  985
 1449 1633  202   85  391  958  576  562
  346 1626  438  825  355  663  517 1086
 1507   94  728 1284  382  645  526  690
  666  778  265 1581  648  706  729  483
  627    4 1376   58 1255  762  913  861

Теперь нужно разбираться в своей программе

[Nataly-Mak]

О!!
Я чувствовала, что они есть!
Умаялась уже их искать. Ещё 25 ваших наборов проверила. Получила 20 ПМК, а магического ни одного.

Как получили-то? Расскажите, пожалуйста. Или это секрет?

[Nataly-Mak]

Я тоже получила в некотором роде магические квадраты
Взяла один из имеющихся у меня ПМК, записала его в виде остатков по модулю 9:

6 6 6 4 4 4 4 8
4 4 4 0 0 4 4 4
4 6 6 0 0 4 0 4
8 4 6 4 6 4 4 6
6 4 6 4 6 6 4 6
6 8 6 4 4 4 4 6
4 6 4 4 4 3 4 4
4 4 4 4 0 4 0 4

Кажется, уже показывала здесь этот ПМК.
У меня во всех ПМК, как я уже говорила, одна диагональ правильная. Тогда я решила сделать полную перестановку столбцов в этом ПМК с целью получить вторую правильную диагональ. Программа выдала штук 50 магических квадратов (счётчик не поставила). Вот первые три:

 6  6  4  4  4  6  4  8 
 4  4  0  0  4  4  4  4 
 4  6  0  0  0  6  4  4 
 8  4  4  6  4  6  4  6 
 6  4  4  6  4  6  6  6 
 6  8  4  4  4  6  4  6 
 4  6  4  4  4  4  3  4 
 4  4  4  0  0  4  4  4 

 6  6  4  4  4  6  4  8 
 4  4  0  4  0  4  4  4 
 4  6  0  0  0  6  4  4 
 8  4  4  4  6  6  4  6 
 6  4  4  4  6  6  6  6 
 6  8  4  4  4  6  4  6 
 4  6  4  4  4  4  3  4 
 4  4  4  0  0  4  4  4 

 6  6  4  4  4  6  4  8 
 4  4  4  0  0  4  4  4 
 4  6  0  0  0  6  4  4 
 8  4  4  4  6  6  4  6 
 6  4  4  4  6  6  6  6 
 6  8  4  4  4  6  4  6 
 4  6  4  4  4  4  3  4 
 4  4  0  4  0  4  4  4

Теперь дело техники, осталось подобрать соответствующие числа и магические квадраты готовы!

Собственно, это реализация блестящей идеи 12d3.

[svb]

Нет, не секрет. Просто нужно все привести в порядок и попытаться нормально описать - сейчас такой бардак с этими программами! Написал программу, которая переводит набор строк в магические квадраты. Оказалось, что из любого набора, которые я выкладывал получаются квадраты и, похоже, очень много - я специально ограничил работу и после 5 квадратов поставил выход.
Полуфабрикат m8s выкладываю, сделал выход по нажатию на ESC.

-- Вс апр 11, 2010 18:56:44 --

Да, забыл написать, программа работает только с теми наборами, которые я отправлял.

[Nataly-Mak]

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

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

Каким образом переводит? Интересно узнать алгоритм перевода.
У меня был такой алгоритм: набор строк -> ПМК -> магический квадрат.
А у вас какой путь превращения набора строк в магический квадрат?

Да, интересно также понять, почему мой путь, применённый к вашим наборам, даёт ПМК, но ни один ПМК в магический не превращается.

[svb]

Точно также: набор строк -> ПМК -> магический квадрат.

[Nataly-Mak]

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

[svb]

Был сильно удивлен тем, почему m8s не работает с любыми наборами. Проблема оказалась в большом количестве ПМК. Нужно либо переходить на использование бОльших объемов памяти, либо вводить в алгоритм ограничения. Я склоняюсь ко второму варианту, т.к. мы работаем с такими объектами, которые сожрут любую память и желательно уметь использовать минимальные ресурсы - всех квадратов не построишь.

[Nataly-Mak]

Это надуманная проблема. Даже квадраты 5-го порядка трудно построить ВСЕ (особенно классические).
Я почти во всех своих программах (кроме программ для квадратов 4-го порядка) работаю "до первого квадрата".

[svb]

Все проблемы кем-то "надуманы", а мне нужно модифицировать следующую процедуру, которая хорошо работает для 5856 и не работает для 5861

procedure pmk(var ind:tind);
var  i,j,k,cq,c:integer;
     nn:array[0..N] of integer;
     st:array[0..N-1] of integer;
     bo:boolean;
     p:array[1..N] of byte;
begin
  for i:=1 to N do p[i]:=0;
  nn[0]:=0;c:=-1;cq:=0;
  repeat
    w:=0;for i:=0 to N-1 do w:=w+B[i,p[i+1]];
    if w=w0 then begin
      inc(c);
      for i:=0 to N-1 do ind[c,i]:=8*i+p[i+1];
    end;
    if c>=5000 then exit;
    i:=N;
    while (p[i]=N-1)and(i>1) do begin p[i]:=0;i:=i-1 end;
    if i=1 then nn[p[i]+1]:=c+1;p[i]:=p[i]+1;
  until p[1]=N;
  for i:=0 to N do write(nn[i],' ');writeln;
  for i:=0 to N*N-1 do met[i]:=0;
  for i:=0 to N-1 do st[i]:=nn[i];
  i:=0;
  repeat
    while st[i]=nn[i+1] do begin
      if i>0 then begin
        st[i]:=nn[i];
        dec(i);for j:=0 to N-1 do met[ind[st[i],j]]:=0;
        inc(st[i]);
      end else exit;
    end;
    bo:=false;
    for j:=0 to N-1 do if met[ind[st[i],j]]<>0 then begin bo:=true;break end;
    if bo then begin
      inc(st[i]);
    end
    else begin
      for j:=0 to N-1 do met[ind[st[i],j]]:=1;
      inc(i);
      if i=N then begin
        inc(cq);
        for k:=0 to N-1 do
          for j:=0 to N-1 do A[k,j]:=B[ind[st[k],j] div 8,ind[st[k],j] mod 8];
        dec(i);
        for j:=0 to N-1 do met[ind[st[i],j]]:=0;
        inc(st[i]);
        analiz(A);
      end;
    end;
  until false;
end;

[12d3]

Первые результаты.
ПМК
Тут 60 ПМК, без обеих диагоналей, сгенерированы примерно за минуту.