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

[svb]

N=60(2515) - 10 квадратов:

1:
 2515  454  202  121  346 2326
 1165   58 1903 2227   94  517
  958 1507  895  382 2218    4
  985 1255  535  355 1921  913
  319 2605  274  265 1219 1282
   22   85 2155 2614  166  922
Time: 6867.39 sec
2:
 2515 2173   22  202  958   94
    4  391 2218 1795 1282  274
 1822  895  121  634  985 1507
  346  526 1678  913  319 2182
  922 1921 1219 1255  382  265
  355   58  706 1165 2038 1642
Time: 10085.64 sec
3:
 2515 1894  382  202  706  265
 1255    4  319 2578 1282  526
  562  922 2182  166  454 1678
  913  391 1822  346  985 1507
   85 1795 1165   58  895 1966
  634  958   94 2614 1642   22
Time: 23750.33 sec
4:
 2515  517  454  202 1894  382
  985 1903  355 2578   22  121
  958 1255    4  706 1822 1219
  913   58 2614  346 1507  526
  319 1966  895   94   85 2605
  274  265 1642 2038  634 1111
Time: 24072.72 sec
5:
 2515  274  895  391 1111  778
 1282  319 1642 2038  562  121
  454 2362  355  958  922  913
  985  265  382   85 2326 1921
   22 2578 2155  634  517   58
  706  166  535 1858  526 2173
Time: 46380.30 sec
6:
 2515  121  346   94 2614  274
  535  706 2461  382  922  958
  265 1255 1858  895  526 1165
 1282   22  778   85 1219 2578
  454 2182  202 2605  166  355
  913 1678  319 1903  517  634
Time: 52222.00 sec
7:
 2515  382  274    4 2434  355
  265 2182 1966 1111  346   94
  454  526   22  706 2038 2218
  895  958 2362  562  202  985
  922 1282  121 1678  166 1795
  913  634 1219 1903  778  517
Time: 55786.30 sec
8:
 2515 1507  121  454  202 1165
  526  517 2326 1282  355  958
   22  319  382 1642  985 2614
  913 1921 1795   94  346  895
 1903  922  634  265 2182   58
   85  778  706 2227 1894  274
Time: 67729.14 sec
9:
 2515  454  265   22 2434  274
  355 1921 1894  535   94 1165
  346  778  319 2461  202 1858
  517  382 1282  922  706 2155
 2173 1795  526  913  166  391
   58  634 1678 1111 2362  121
Time: -4301.17 sec
10:
 2515  706  121  265 1903  454
   58  166 2722 1795 1219    4
 2218  535   94  913   22 2182
  562 1165 1894  634  202 1507
   85  958  355 2038 1633  895
  526 2434  778  319  985  922
Time: 6555.00 sec

Цитата:

Да, а что означает отрицательное время?

В полночь внутренний счетчик машины меняет свои показания. Можно добавить сутки (86400 сек).

[Nataly-Mak]

Ага, понятно.
И осталось вам проверить всего 4 числа

[svb]

Цитата:

Среди квадратов, выложенных svb вчера (неполный поиск) нашла два новых квадрата,...

Я, вроде, написал вчера, что полный поиск совпал с неполным А те 2 квадрата, которые вы выложили, это:

7:
 3046   22  778   94  913 1111
  265  706 1633 2434  535  391
  382 1903 1219  454   85 1921
  634  526  121  202 2515 1966
  355 2461 1894  922  274   58
 1282  346  319 1858 1642  517
Time: 28673.69 sec
8:
 3046  202   94  121 1219 1282
   85  706 2515 1678  526  454
 1858  895  265  958 1822  166
  535 1633  634  274  922 1966
   58 2182   22 2155  562  985
  382  346 2434  778  913 1111
Time: -42760.74 sec

Как определять N конкретного квадрата я уже писал, делается это вручную достаточно быстро. Смешивать в одну кучу результаты работы разных программ - себе дороже. Необходимо выбрать либо одну, либо другую программу для классификации в зависимости от используемой программы. Например, число 3046 может входить в любой квадрат при N=64..71 (по моей программе).

-- Пт май 18, 2012 08:05:43 --

Оказывается это ваша цитата - а я и не понял Т.е. вчера это не совсем вчера, даже совсем не вчера .

Кстати, посмотрел куда еще входит 3046, вот: N=67(3091)

[Nataly-Mak]

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

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

Это я уже поняла.
Но можно и смешать в кучу, ничего страшного. Я делаю так: ранжирую массив каждого квадрата, сразу по ранжированному массиву всё становится ясно - что за квадрат.
Удивительно, но пока мне не попался ни один массив из 36 чисел, чтобы из них составилось более одного квадрата!

[svb]

Закончена полная проверка N=63(2911), найдено 9 квадратов, на 2 квадрата больше, чем при неполной проверке (CP=4):

16:
 2911 1507  319  526  346  355
  391   94  985 1966 1822  706
  562 1894 2155  121  274  958
  535  265  517    4 1858 2785
  454 2038 1903 1165   22  382
 1111  166   85 2182 1642  778
Time: 53180.91 sec
17:
 2911   58  265  202 1633  895
  166  562 2326 1795 1111    4
 2155 1822   22 1165  526  274
  517  382  454  346 1903 2362
   94 2218 1255 1921   85  391
  121  922 1642  535  706 2038
Time: -24868.92 sec
18:
 2911  526 1219   22 1282    4
 1111 1165  346 2605  355  382
 1633  319  265 1507  562 1678
   85 1255 1858  958  913  895
  166 2182  634   94  274 2614
   58  517 1642  778 2578  391
Time: -8303.03 sec
19:
 2911   22  958    4 1795  274
  634  454 2578  895 1282  121
 1921   94  562 1678  202 1507
  355 1642  778  706  517 1966
   85 1894  166 2362  346 1111
   58 1858  922  319 1822  985
Time: -7461.36 sec
20:
 2911  355  121   94 1921  562
 1282  985 2614  526  391  166
  319  274  382 1858 1966 1165
  913 1678 1255   58   22 2038
  535 1894   85 1633  706 1111
    4  778 1507 1795  958  922
Time: -4223.39 sec
21:
 2911    4  895   22 1219  913
   58 1822 1795  985  382  922
  454  634  274 2614   85 1903
  517 1642  202  526 1111 1966
 1678 1507 1165 1255  265   94
  346  355 1633  562 2902  166
Time: 1071.75 sec
22:
 2911  166  778  274 1633  202
  265 1282 1165  895  391 1966
  535  922 1507 2461   22  517
  706  958   94   85 1219 2902
  913 2182  526 1903  121  319
  634  454 1894  346 2578   58
Time: 9470.44 sec
23:
 2911  958  319  274  985  517
  265  454 2182 2326  202  535
 1894   94  121 1678  355 1822
  706 1255 1507   85  778 1633
  166 2038  913 1219 1282  346
   22 1165  922  382 2362 1111
Time: 9801.11 sec
24:
 2911 1111  517   85  634  706
  265  778 2515 1678  526  202
  454  274  166  382 2362 2326
  958 2173 1858   22   58  895
  391 1507  346 1642 1165  913
  985  121  562 2155 1219  922
Time: 29717.39 sec

[Nataly-Mak]

У меня тоже с числа 2911 9 квадратов, при этом я добавила к 7 квадратам, найденным по программе alexBlack, 2 отличных квадрата из ваших (по неполной ещё проверке когда вы выложили).

Вчера вечером всё-таки прервала программу alexBlack, проверяющую число 2722, после найденных 7 квадратов и примерно 1,5 суток работы программа наглухо "застопорилась" (перестала рисовать и точки, и квадраты), не стала оставлять на вторую ночь.
Квадраты найдены такие:

S = 5964
№ 1
913 526 1642 2155 634 94
2578 166 202 958 1282 778
319 2605 1111 985 922 22
562 454 274 346 2362 1966
85 1822 2614 355 706 382
1507 391 121 1165 58 2722
№ 2
526 2182 1921 346 355 634
535 121 1507 958 1165 1678
1642 562 922 202 2578 58
2326 985 1255 778 454 166
22 1795 85 2461 895 706
913 319 274 1219 517 2722
№ 3
706 2434 958 1165 535 166
2515 526 85 562 2218 58
454 922 895 1507 2182 4
1903 985 1633 202 22 1219
265 319 2038 634 913 1795
121 778 355 1894 94 2722
№ 4
166 2173 2155 319 517 634
1903 121 985 382 2182 391
958 1255 535 346 2605 265
1633 1282 913 1858 4 274
526 1111 922 1165 562 1678
778 22 454 1894 94 2722
№ 5
1678 958 2218 274 58 778
121 202 1966 1219 562 1894
1903 706 346 985 1633 391
1642 1165 895 382 1795 85
454 2578 22 2182 634 94
166 355 517 922 1282 2722
№ 6
1282 274 2614 535 913 346
1219 1165 1633 94 58 1795
517 391 355 1858 2578 265
2038 1678 562 121 1111 454
202 2434 166 2461 319 382
706 22 634 895 985 2722
№ 7
985 202 1894 1822 706 355
265 1111 1921 319 382 1966
1858 1219 346 94 2173 274
391 913 1165 778 2155 562
958 2461 4 2434 22 85
1507 58 634 517 526 2722

Прекращаю проверку магической константы 5964 и возвращаюсь к проверке других потенциальных констант, мне осталось проверить всего 6 штук: 4506 - 4776 (с шагом 54).
Вот что у меня получилось при проверке магической константы 5964 по программе alexBlack (в обозначениях svb):

N=65(3046) - 6 квадратов (не полностью)
N=64(2911) - 7 (не полностью)
N=63(2974) - 3 (не поностью)
N=62(2839) - 4 (полностью)
N=61(2902) - 5 (не полностью)
N=60(2785) - 3 (не полностью)
N=59(2722) - 7 (не полностью)

[N=65 означает, что в исходном массиве 65 чисел, число в скобках - 3046 - проверяемое число из данного массива чисел].
Чтобы получить все квадраты, надо повторить проверку чисел, которые у меня проверились не полностью, и продолжить проверку с N=58.

Сейчас проделаю эксперимент - запущу проверку магической константы 4506 сразу по обеим программам (svb и alexBlack).

-- Сб май 19, 2012 06:05:47 --

Эксперимент стартовал

Программа svb сформировала для магической константы 4506 массив из 60 чисел, а программа alexBlack - из 83 чисел.

Интересная картинка старта программы alexBlack, покажу:



"Хвост" массива, несколько последних чисел проверились секунд за 5, замедлилась проверка только на числе 2839.

[Nataly-Mak]

Захватывающее соревнование двух программ



Верхняя программа alexBlack, нижняя - svb.
Обе программы хорошо идут, пока "ухо в ухо"; в данный момент обе программы имеют для проверки массив из 50 чисел.
Порядок проверки чисел, как всегда, различный.
Обе программы совершенно в равных условиях, работают сейчас только эти две программы, каждая обслуживается, как я понимаю, отдельным ядром процессора (у меня двухядерный процессор).

Какая программа финиширует первой?

Делайте ваши ставки, господа! (шутка )

[svb]

Закончена полная проверка N=59(2227), найдено 8 квадратов

(Оффтоп)

11:
 2227  778  958  202 1282  517
 1111  454  985 2326  526  562
   85 1858 1642  355   58 1966
  634   94  319  913 1822 2182
  274 2614 2038  265  382  391
 1633  166   22 1903 1894  346
Time: 16390.03 sec
12:
 2227  382  121  202 2974   58
   85 1894 2038  319  706  922
  634  355  913 2218  166 1678
 1282  526 1219  265   94 2578
  958  985  562 2614  391  454
  778 1822 1111  346 1633  274
Time: 37392.35 sec
13:
 2227   85  346  517 1507 1282
   22 1822 2605  985    4  526
   94  382  634  562 2434 1858
 1111 2218  706  121  166 1642
  355 1255  454 2614  895  391
 2155  202 1219 1165  958  265
Time: 40558.18 sec
14:
 2227  985   94   22 2182  454
  319 1903 1795 1507  382   58
  913  265    4 2362  562 1858
 1642  535 1255   85  274 2173
  517 1165 1921 1633  526  202
  346 1111  895  355 2038 1219
Time: 52465.30 sec
15:
 2227  391  913   85 1894  454
  121 1642 2434   94 1111  562
  922  355   22 2218  274 2173
  382 1633  706 1282   58 1903
 1795  958  634 1966  265  346
  517  985 1255  319 2362  526
Time: 56864.16 sec
16:
 2227    4  391  526 2362  454
 1903  778  922  274 1822  265
  121 1111 2605 1507   85  535
 1165  355  517   58 1255 2614
  166 1282  895 1633   94 1894
  382 2434  634 1966  346  202
Time: 66806.35 sec
17:
 2227 2218  535    4  778  202
  913   85 1111  391 1642 1822
  382  346 2578 1633  706  319
 1219  958  634  526   22 2605
 1165 1795  121 1507  454  922
   58  562  985 1903 2362   94
Time: 69694.19 sec
18:
 2227 1219  202   85 2173   58
  526 1507  895 1111 1903   22
  778  391 1678  346  913 1858
 1282  319 2461  382  265 1255
  517  562  454 1822    4 2605
  634 1966  274 2218  706  166
Time: 19069.38 sec

[Nataly-Mak]

Финиш:



Почти одинаковое время.

svb
у меня такой вопрос по вашей программе, я давно заметила эту особенность, но всё забывала спросить:
почему программа останавливает проверку при N=37? Ведь в массиве ещё 37 чисел.
В программе alexBlack проверяется даже массив из 36 чисел (видно на картинке).

[svb]

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

svb
у меня такой вопрос по вашей программе, я давно заметила эту особенность, но всё забывала спросить:
почему программа останавливает проверку при N=37? Ведь в массиве ещё 37 чисел.
В программе alexBlack проверяется даже массив из 36 чисел (видно на картинке).

Насколько я помню, для 37 идет проверка возможности квадрата и если нет такой возможности то идет остановка. Программа же проверяет массивы из 36 чисел - вы это видели неоднократно. Кстати, легко проверить - возьмите 37 чисел с имеющимся квадратом.

-- Сб май 19, 2012 15:46:04 --

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

[Nataly-Mak]

Я так и предполагала.
То есть получается, что когда в массиве остаётся 37 чисел, надо сразу проверить возможность образовать из этих 37 чисел хоть один набор из 36 чисел, имеющий нужную сумму (наборов-то будет всего 37). Если ни одного такого набора сформировать невозможно, проверку надо останавливать.

Насчёт несовершенства алгоритма пока не поняла.

Кстати, я писала в теме "Распараллеливание для многоядерных процессоров", что пыталась действовать так: из всех чисел массива (пусть их, к примеру, 60, как было в только что проведённом эксперименте для магической константы 4506) сформировать все возможные наборы по 36 чисел и проверять каждый такой набор отдельно. Ведь массивы из 36 чисел проверяются очень быстро (в большинстве случаев).
Но... число сочетаний из 60 по 36 величина огромная, поэтому данная затея мне показалась нереальной.

[Nataly-Mak]

Проверила массив из 37 чисел, который остаётся в программе alexBlack. Вот этот массив:

4 22 58 85 94 121 166 202 265 274 319 346 355 382 391 454 517 526 535 562 634 706 778 895 913 922 958 985 1111 1165 1219 1255 1282 1507 1633 1642 1678

Совершенно очевидно, что из этого массива невозможно сформировать ни одного набора из 36 чисел, чтобы их сумма была равна 4506\cdot6=27036.
Так что, в программе alexBlack тоже можно было остановить проверку на массиве из 37 чисел. Это дало бы некоторый выигрыш во времени.

[svb]

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

Насчёт несовершенства алгоритма пока не поняла.

Тот, кто это поймет, сможет создать новый алгоритм

Цитата:

Кстати, я писала в теме "Распараллеливание для многоядерных процессоров", что пыталась действовать так: из всех чисел массива (пусть их, к примеру, 60, как было в только что проведённом эксперименте для магической константы 4506) сформировать все возможные наборы по 36 чисел и проверять каждый такой набор отдельно. Ведь массивы из 36 чисел проверяются очень быстро (в большинстве случаев).
Но... число сочетаний из 60 по 36 величина огромная, поэтому данная затея мне показалась нереальной.

Эх! Именно вокруг этого всё и вертится. А, например, квадратов с суммой $2S_c$ не так уж и много - у меня в программе $NQ$ высвечивается, около 1000.

[Nataly-Mak]

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

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

Насчёт несовершенства алгоритма пока не поняла.

Тот, кто это поймет, сможет создать новый алгоритм

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

Цитата:

А, например, квадратов с суммой $2S_c$ не так уж и много - у меня в программе $NQ$ высвечивается, около 1000.

Это девятки??
А на форуме ПЕН я выкладывала алгоритм "перебор по девяткам". Не видели? Этот перебор вообще секунды выполняется. Я и программу писала для этого перебора. Даже на моём старом компьютере (ужасном тихоходе) этот перебор выполнялся мгновенно. Дело встало за формированием всех различных наборов по 4 девятки Тоже задачка ещё та

add
а, нет, это у вас не девятки, а четвёрки.
А девяток будет меньше, наверное?

[svb]

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

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

Я вот вижу несовершенство нашей власти (да и любой другой, впрочем), но вот ...

Цитата:

Это девятки??

Да нет, четверки.

Цитата:

А на форуме ПЕН я выкладывала алгоритм "перебор по девяткам". Не видели? Этот перебор вообще секунды выполняется. Я и программу писала для этого перебора. Даже на моём старом компьютере (ужасном тихоходе) этот перебор выполнялся мгновенно. Дело встало за формированием всех различных наборов по 4 девятки Тоже задачка ещё та

Чёрт прячется в деталях

Цитата:

Тихоход

Ох и любите вы пококетничать , а вот я бы с удовольствием на 286 процессоре продолжал бы работать - мозгам было бы больше пользы.