fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 42, 43, 44, 45, 46, 47, 48 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.08.2013, 11:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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. Надо брать другой шаблон и переписывать программу.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.08.2013, 18:34 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #758355 писал(а):
whitefox, Pavlovsky
выложить БД? Чтобы вам не строить, когда уже есть готовая.

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.08.2013, 20:58 


02/11/12
141
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.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.08.2013, 21:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Выкладываю свою программу поиска решений для 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.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.08.2013, 23:24 
Заблокирован
Аватара пользователя


22/03/08

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

Изображение

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 07:29 
Заблокирован
Аватара пользователя


22/03/08

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

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

Изображение

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 08:21 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #758633 писал(а):
Но даже если мы возьмём массив, состоящий точно из 49 чисел, всё равно выполнить полный перебор 23 свободных переменных (одну свободную переменную в этом случае можно зафиксировать) нереально (при всех оптимизациях программы, о которых вы писали выше).


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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 08:23 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

Pavlovsky в сообщении #758637 писал(а):
И у меня нет даже идей куда вставить случайный выбор ...

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

Код:
FOR I5=K5 TO K5

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 09:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 12:34 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #758647 писал(а):
Осталось всего чуть-чуть: найти недостающие цепочки в последних двух покрытиях с выполнением всех нужных условий.


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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 13:08 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

(Оффтоп)


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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 13:13 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #758647 писал(а):
встречная идея...
Не находим БД.
Сразу начинаем со второго пункта: находим 4 точных покрытия.

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 13:18 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 13:30 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #758685 писал(а):
Если имеются, тогда покажите мне, пожалуйста, как вы будете строить из этих двух покрытий полумагический квадрат. То бишь - как проверять, что из этих двух ортогональных покрытий можно сделать полумагический квадрат.

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение29.08.2013, 13:34 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 42, 43, 44, 45, 46, 47, 48 ... 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group