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

[Nataly-Mak]

whitefox, Pavlovsky
выложить БД? Чтобы вам не строить, когда уже есть готовая.

С магической константой 737 дела намного хуже. За 7 часов работы ни одного решения с одной ошибкой, 94 решения с двумя ошибками. Чем меньше магическая константа, тем сложнее найти решение.
Да, очень нужен новый подход. Для констант 735 и 733 просто необходим!

-- Ср авг 28, 2013 13:22:01 --

whitefox в сообщении #758305 писал(а):

Для S=735 существует всего 3 массива простых:

3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,223,227,229,241;

3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,229,239,241;

3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,229,257;

Из этих трёх массивов надо сделать объединённый массив:

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
211 223 227 229 239 241 257

В массиве 52 числа. В своей программе сейчас введу этот массив для проверки магической константы 735.

-- Ср авг 28, 2013 13:43:51 --

Увы, для моей программы этот объединённый массив не годится.
Разбила массив на две группы, соответствующие вычетам 1 и 2 по модулю 3:

Группа 1

7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241

(25 чисел)

Группа 2

5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 239, 257

(26 чисел)

Шаблон у меня такой:

2 2 1 2 1 1 0
2 2 1 2 2 1 2
2 1 2 1 1 1 1
1 2 1 2 2 2 2
2 2 1 2 2 2 1
1 2 2 2 2 1 2
2 1 1 1 2 1 1

1 – 21 штука, 2 – 27 штук.
Не хватает одного числа с вычетом 2. Надо брать другой шаблон и переписывать программу.

[whitefox]

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

whitefox, Pavlovsky
выложить БД? Чтобы вам не строить, когда уже есть готовая.

Спасибо, эта база у меня тоже есть.

[mertz]

Reviewing all the changes, I had commented out the section with the extra ; error. Here are the timings for 12 threads on my machine.

original code 7 searches per second
; removed 35 searches per second
no ; section 150 searches per second

Results are similar for all runs. The ; section appears to be a last try to improve the solution. It appears to fail 100% of the time. With the ; removed the code is 5 times faster. Not running that section is 21 times faster.

[Nataly-Mak]

Выкладываю свою программу поиска решений для N=7
http://yadi.sk/d/6li8bpwm8RHaW

В архиве исполняемая программа PAND7formA.exe и три текстовых файла с исходными данными - A50.txt, A51.txt, A52.txt.

Программа предназначена для поиска решений с магическими константами кратными 3: 735, 741, 747, 753, 777. Константа 777 добавлена для тестирования программы, остальные 4 константы актуальны для поиска в данный момент.

В файлах A51.txt, A52.txt находятся две группы простых чисел, в этих файлах исходные данные постоянны, ничего менять не надо. О данных в файле A50.txt скажу ниже.

Сначала выполните тест. При запуске программа требует ввести магическую константу из списка, введите для теста константу 777. Больше ничего не надо делать. Программа выполнится и решение запишется в файл A53.txt. Это в точности решение Jarek с магической константой 777. У меня это решение находится секунд за 10.

Чтобы искать другие решения, надо изменять данные в файле A50.txt.
Сейчас вы видите в этом файле следующий вектор:

1 31 9 6 24 3 23 15

Это значения номеров случайно выбранных переменных. Как видите, таких переменных всего 8 штук. Обозначим номера переменных Ki.
Ki при i=1,2,...,6 могут принимать попарно различные значения от 1 до 33 (включительно);
Ki при i=7,8 могут принимать различные значения от 1 до 29 (включительно).

Понятно, что можно вставить генерацию этого вектора в программу. Ну, пока не стала этого делать, чтобы наглядно показать тест с заданным начальным вектором K, который записан в файле A50.txt.
Я сейчас ввожу этот вектор в файл A50.txt вручную, какой в голову взбредёт. Запускаю программу, программа работает, решение ищет, но увы, не находит пока.

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

[Nataly-Mak]

Как обидно - всего одна дырка и число очень похоже на простое.
Давайте объявим 133 простым числом (временно)



Покрутив программу для $S=737$ часов 8 и не найдя ни одного решения с одной дыркой, бросила эту константу и опять начала проверять константу 743. Для этой константы лучше дело идёт, уже найдено 4 решения с одной ошибкой.

Jarek
такой вопрос возник: решения с одной ошибкой доработке не подлежат? Ликвидировать в них ошибку уже невозможно (с помощью волшебного квадрата из 8 единичек)?
Программа mertz сохраняет все такие решения, и с двумя ошибками тоже сохраняет.

[Nataly-Mak]

whitefox в сообщении #758323 писал(а):

...Четырежды решаем задачу точного покрытия заданного набора простых найденным множеством разбиений (например, использую алгоритм "танцующих связей" Д. Кнута).

Вот так выглядит первое точное покрытие массива, взятого из решения Jarek $S=755$



Каждой цепочке соответствует свой цвет.
Для массива, дающего магическую константу 733, я нашла 393510 цепочек. Четырежды выполнить задачу точного покрытия цепочками из такой огромной БД и при этом получить ортогональные покрытия, и при этом получить из 4-х ортогональных покрытий пандиагональный квадрат - задачка не лёгонькая.

-- Чт авг 29, 2013 08:59:09 --

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

Неспешно обдумываю алгоритм проверки. Выбираю из двух вариантов: либо делать перебор по общей формуле или строить 4 разбиения на N групп по N чисел.

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

[Pavlovsky]

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

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

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

[Nataly-Mak]

Я сегодня ищу по программе mertz решение с магической константой 749.

dimkadimon
что у вас с этой константой?
У меня пока 3 решения с одной ошибкой и более 200 решений с двумя ошибками.

-- Чт авг 29, 2013 09:28:34 --

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

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

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

FOR I5=K5 TO K5

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

Я вчера выложила программу со случайным выбором первых восьми свободных переменных.

[Nataly-Mak]

whitefox в сообщении #758323 писал(а):

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

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

Проверяем, что найденные покрытия составляют пандиагональный квадрат (желательно эту проверку выполнять ещё на этапе построения).

whitefox
встречная идея...
Не находим БД.
Сразу начинаем со второго пункта: находим 4 точных покрытия.
Находить точное покрытие я могу и без алгоритма "танцующих связей"; это делается просто (см. указанную выше статью о построении обычных МК). В статье написано, что одно точное покрытие для квадрата порядка 7 генерируется за несколько секунд.
Итак,
1. генерируем 4 точных покрытия (несколько секунд);
2. проверяем их ортогональность (у вас есть программа проверки ортогональности 4-х точных покрытий?); думаю, что ортогональность покрытий тоже выполнится за несколько секунд;
3. проверяем, получается ли из этих ортогональных 4-х покрытий пандиагональный квадрат. Вот этот пункт пока плохо представляю, поэтому время назвать не могу.
Всё.

Стоп! Кажется, я упустила один момент. Точные покрытия должны состоять из различных цепочек; то есть в первом покрытии какие-то 7 цепочек, во втором покрытии уже другие 7 цепочек (использованные в первом покрытии уже нельзя использовать во втором). И т.д. Верно?
Тогда случайная генерация 4-х покрытий не годится, хотя вероятность получить при случайной генерации совпадающие в покрытиях цепочки очень мала. К тому же, если это и случится, то на втором этапе этот набор 4-х покрытий сразу забракуется, как набор не ортогональных покрытий.
В общем, надо попробовать этот путь.

-- Чт авг 29, 2013 11:18:47 --

Это обычный магический квадрат с константой 733 из моей статьи:

3 5 7 23 223 233 239
211 191 181 19 31 29 71
79 83 89 107 109 127 139
199 197 103 193 17 11 13
53 149 59 157 101 47 167
151 67 131 137 73 113 61
37 41 163 97 179 173 43

Первое точное покрытие (строки):

3 5 7 23 223 233 239
211 191 181 19 31 29 71
79 83 89 107 109 127 139
199 197 103 193 17 11 13
53 149 59 157 101 47 167
151 67 131 137 73 113 61
37 41 163 97 179 173 43

Второе точное покрытие (столбцы):

37  151  53  199  79  211  3 
 41  67  149  197  83  191  5 
 163  131  59  103  89  181  7 
 97  137  157  193  107  19  23 
 179  73  101  17  109  31  223 
 173  113  47  11  127  29  233 
 43  61  167  13  139  71  239

В третьем и четвёртом покрытиях имеем только по одной цепочке - это главные диагонали квадрата:

3 191 89 193 101 113 43

и

37 67 59 193 109 29 239

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

Осталось всего чуть-чуть: найти недостающие цепочки в последних двух покрытиях с выполнением всех нужных условий.

[Pavlovsky]

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

Осталось всего чуть-чуть: найти недостающие цепочки в последних двух покрытиях с выполнением всех нужных условий.

Тут должно сработать забавное свойство пандиагональных квадратов. Чем больше N тем легче пострить квадрат. Так что можно начать поиск не с N=7, с больших порядков, например N=11.

[Nataly-Mak]

Цитата:

Находить точное покрытие я могу и без алгоритма "танцующих связей"; это делается просто

Раскопала старую программу генерации набора из 7 строк.
Один набор (точное покрытие) генерируется мгновенно (доля секунды).

whitefox
вот несколько точных покрытий

(Оффтоп)

 83  107  79  137  131  179  17 
 41  157  127  109  101  7  191 
 173  5  31  223  67  53  181 
 151  113  61  149  163  73  23 
 239  197  71  167  37  3  19 
 233  11  193  139  97  13  47 
 211  103  199  89  43  59  29 

 193  19  83  17  199  179  43 
 211  167  23  191  3  101  37 
 157  223  53  41  67  11  181 
 5  89  131  239  59  113  97 
 233  137  73  13  103  127  47 
 71  31  173  149  139  163  7 
 197  29  109  61  107  79  151 

 109  31  181  17  137  131  127 
 73  83  97  37  23  223  197 
 19  107  173  211  59  13  151 
 199  71  53  47  139  67  157 
 79  41  5  103  163  149  193 
 233  61  89  3  43  113  191 
 167  179  101  239  11  29  7 

 43  109  157  103  151  3  167 
 173  5  139  193  59  67  97 
 23  7  191  181  89  163  79 
 223  41  53  197  71  17  131 
 239  101  137  83  47  107  19 
 73  29  31  127  61  233  179 
 37  113  199  13  149  211  11 

 41  61  59  11  157  181  223 
 199  167  5  71  23  131  137 
 139  149  151  197  47  37  13 
 3  211  7  113  127  193  79 
 191  67  101  73  29  163  109 
 83  239  53  89  233  19  17 
 107  31  173  179  103  97  43 

 113  163  109  103  139  101  5 
 97  233  167  11  29  17  179 
 61  31  137  73  181  191  59 
 107  3  43  239  19  149  173 
 89  157  37  193  47  79  131 
 13  23  211  223  53  83  127 
 199  67  7  197  41  71  151 

 109  179  163  97  29  17  139 
 103  193  7  199  53  47  131 
 173  11  223  67  37  71  151 
 233  13  5  107  191  83  101 
 137  239  43  149  61  73  31 
 197  181  157  3  113  59  23 
 89  19  127  79  167  211  41 

 181  67  199  127  23  47  89 
 173  61  73  233  31  79  83 
 239  11  137  109  19  7  211 
 157  139  53  41  3  149  191 
 107  43  179  17  223  13  151 
 167  197  101  29  131  37  71 
 113  103  5  193  163  97  59 

 31  149  41  19  157  97  239 
 109  43  113  199  233  13  23 
 61  53  211  181  71  83  73 
 163  167  223  101  3  29  47 
 7  59  193  197  173  67  37 
 137  11  79  131  107  89  179 
 139  127  151  103  191  5  17

Это по моей старой программе; магическая константа 733 (первый из приведённых выше массивов).
Вы можете найти тут набор хотя бы из 3-х попарно ортогональных покрытий? У меня нет программы проверки ортогональности покрытий.
Очевидно сразу же, что два первых покрытия не ортогональны.

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

[whitefox]

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

встречная идея...
Не находим БД.
Сразу начинаем со второго пункта: находим 4 точных покрытия.

Есть у меня программа следующая этому пути.

Начинает она свою работу со случайного выбора пары ортогональных покрытий (что эквивалентно случайному выбору полумагического квадрата). Делается это мгновенно.

Затем полным перебором проверяется -- существует ли пандиагональный квадрат, два покрытия которого совпадают с выбранными (то есть можно ли из данного полумагического квадрата получить пандиагональный). Перебор сильно оптимизирован, проверка выполняется очень быстро (примерно 700 пар покрытий за секунду для N=7).

И, хотя, не гонял эту программу более одного часа, сомневаюсь в её эффективности для N=7.

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

Находить точное покрытие я могу и без алгоритма "танцующих связей"; это делается просто (см. указанную выше статью о построении обычных МК). В статье написано, что одно точное покрытие для квадрата порядка 7 генерируется за несколько секунд.

Д. Кнут разработал свой алгоритм для нахождения всех покрытий. Если для N=7 S=733 падиагонального квадрата не существует, то это можно доказать рассмотрев все покрытия.

[Nataly-Mak]

whitefox в сообщении #758686 писал(а):

Затем полным перебором проверяется -- существует ли пандиагональный квадрат, два покрытия которого совпадают с выбранными (то есть можно ли из данного полумагического квадрата получить пандиагональный).

Поясните, как это проверяется.

Цитата:

Д. Кнут разработал свой алгоритм для нахождения всех покрытий. Если для N=7 S=733 падиагонального квадрата не существует, то это можно доказать рассмотрев все покрытия.

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

Цитата:

Начинает она свою работу со случайного выбора пары ортогональных покрытий (что эквивалентно случайному выбору полумагического квадрата).

Вы хотите сказать, что из любых двух ортогональных точных покрытий можно сделать полумагический квадрат? Пример можно?

[whitefox]

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

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

Пусть нам даны два ортогональных покрытия.

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

Возьмём произвольное разбиение из первого покрытия и произвольное из второго. Их общий элемент поместим в левый верхний угол квадрата.

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

Этим полумагический квадрат определяется однозначно. Все прочие его клетки заполняются автоматически.

[Nataly-Mak]

Это поняла.
А как вы проверяете, можно ли из полумагического квадрата получить пандиагональный?

P.S. Чтобы закрепить то, что вроде поняла, приведите, пожалуйста, два ортогональных покрытия, я попробую сделать полумагический квадрат.
Хотя... сейчас у себя поищу.