Prime Sums

[Nataly-Mak]

Например, структура 2,14,8,6,6, оценка Q=1760 (при естественном разбиении).
Схема:

0 2 0 3 0 3
3 1 3 2 3 2
0 2 0 3 0 3
3 1 3 2 3 2
1 3 1 4 1 4
3 1 3 2 3 2

Не даёт решения 1760?

Я использовала эту схему при поиске решения 1758, но разбиение было не естественное, точнее: разбиений мне whitefox прислал 14 штук. Попробовала первое разбиение, мимо. Тогда взяла и попробовала сразу 14-ое И тут улыбнулась удача.

-- Пн янв 07, 2013 12:58:05 --

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

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

А кто-нибудь доказал, что результат 1758 для N=6 неулучшаем

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

Жаль, что бросили. Вот самые интересные моменты у нас остаются за бортом. Это плохо.

У меня программа полного перебора для "шестёрки" работает не так скоро, как у svb ("минуты-секунды"). Однако всё же работает; у меня наоборот: в случае отсутствия решения программа работает долго, а в случае его наличия находит за пару минут

[svb]

Pavlovsky

Цитата:

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

Запустил сейчас проверку случайной схемы 887 для поиска 1760. Через несколько секунд найдено 11 простых линий.

[Nataly-Mak]

svb
надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.

[svb]

Nataly-Mak

Цитата:

надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.

В том то и дело. Даже 1758 я получаю с трудом - как повезет
А тут кроме схемы еще накладывается выбор распределения, которых запредельное число

[Pavlovsky]

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

Через несколько секунд найдено 11 простых линий.

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

Цитата:

Выставлялось максимум половина линий

Это не потому что мой алгоритм не может выставить 11 линий. Просто он бросает перебор, когда видит что дальше смотреть бесполезно.

[svb]

Pavlovsky

Цитата:

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

Так то оно так, но зато у меня нет ограничения по выбору простых чисел
А вот, что проверять, пока не вижу.

[Nataly-Mak]

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

Nataly-Mak

Цитата:

надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.

В том то и дело. Даже 1758 я получаю с трудом - как повезет
А тут кроме схемы еще накладывается выбор распределения, которых запредельное число

Тогда я ничего не понимаю.
Вы пишете, что при конкретно выбранной схеме-разбиении у вас программа полного перебора для "шестёрки" работает "минуты-секунды".
Так в чём проблемы?
Здесь выкладывали все уникальные схемы для "шестёрки", или, по крайней мере, большинство. И разбиений совсем не запредельное число! Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.

[svb]

Nataly-Mak

Цитата:

Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.

Но я беру схему с оценкой 887(1777) и количество разбиений получается запредельным, и для каждого распределения имеется 11 простых линий.

[Pavlovsky]

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

но зато у меня нет ограничения по выбору простых чисел

А кто мешает сформировать все допустимые наборы простых чисел? Если использовать изощренные способы проверки допустимости, то для N=6,7 их будет очень немного.

[Nataly-Mak]

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

Nataly-Mak

Цитата:

Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.

Но я беру схему с оценкой 887(1777) и количество разбиений получается запредельным, и для каждого распределения имеется 11 простых линий.

А почему надо брать только схему с оценкой 887/1777? Что мешает рассмтривать схемы с другими оценками? Ведь при этом количество разбиений перестаёт быть запредельным.

Вот по поводу приведённой мной чуть выше структуры 2,14,8,6,6 с оценкой Q=1760 очень интересная информация из письма whitefox:

Цитата:

Последние два решения получены по различным, но изоморфным схемам:

0,2,0,3,0,3
3,1,3,2,3,2
0,2,0,3,0,3
3,1,3,2,3,2
1,3,1,4,1,4
3,1,3,2,3,2

0,2,0,3,0,3
3,1,3,2,3,2
1,3,1,4,1,4
3,1,3,2,3,2
0,2,0,3,0,3
3,1,3,2,3,2

со структурой 2,14,8,6,6 и с максимальной оценкой 1760.

С точностью до изоморфизма существует только одна схема со структурой
2,14,8,6,6 и только одна двойственная ей схема со структурой 6,6,8,14,2.
Этими двумя классами изоморфных схем исчерпываются все схемы с
максимальной оценкой 1760.

Для структуры 2,14,8,6,6 существует только 14 разбиений с оценкой 1758,
аналогично и для структуры 6,6,8,14,2.
Вот эти разбиения:

для 2,14,8,6,6

(Оффтоп)

36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 5 7 6 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 7 6 8 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 12
13 11 10 9 8 6 7 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 11
13 12 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 13 12
14 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 20 21 19 18 17 16 15 14 13
12 11 10 9 8 6 7 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 20 21 19 18 17 16 15 14 12
13 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 19 21 20 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 21 20 22 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 34 35 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 6 7 5 4 3 2 1
36 34 35 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 12
13 11 10 9 8 7 6 5 4 3 2 1
36 34 35 33 32 31 30 29 28 27 26 25 24 23 22 20 21 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 33 35 34 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
35 34 36 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1

для 6,6,8,14,2

(Оффтоп)

36 35 34 33 31 30 32 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 29 31 30 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 30 31 29 28 27 26 24 25 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 25 24 26 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 23 25 24 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 30 31 29 28 27 26 25 24 23 22 21 20 19 18 16 17 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 24 25 23 22 21 20 19 18 16 17 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 17 16 18 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 15 17 16 14 13
12 11 10 9 8 7 6 5 4 3 2 1
36 35 34 33 32 30 31 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 2 3 1
36 35 34 33 32 31 30 29 28 27 26 24 25 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 2 3 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 16 17 15 14 13
12 11 10 9 8 7 6 5 4 2 3 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 3 2 4 1
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 1 3 2

Именно этими разбиениями я и воспользовалась при нахождении решения 1758.
А если искать решение 1760, то разбиение будет для каждой схемы всего одно - естественное.

[Pavlovsky]

N=6 четное. Там есть еще дополнительное условие на наборы простых чисел! Наборов простых чисел получается совсем немного. Для четных N у меня программа выдает наборы простых чисел разбитые на три группы. Отдельно простые числа для прямых диагоналей, обратных диагоналей и остальное для строк и колонок. Что сильно сокращает перебор при работе основоного алгоритма.

[Nataly-Mak]

Вот оно - решение 1758 с приведённой выше структурой 2,14,8,6,6 и с 14-ым разбиением из приведённой цитаты whitefox (схема первая в цитате):



Я не проверяла другие разбиения; как только нашла решение, сразу перешла к другим задачам.

whitefox писал здесь, что если бы не удалось найти решение 1758 по схемам с оценкой 1760, пришлось бы искать его по схемам с максимальной оценкой 1768, и тогда разбиений было бы намного больше.

[svb]

Pavlovsky

Цитата:

А кто мешает сформировать все допустимые наборы простых чисел?

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

Nataly-Mak
Чем дальше оценка схемы лежит от искомого результата, тем больше шансов найти решение - это почти экспериментальный факт.

Pavlovsky

Цитата:

N=6 четное. Там есть еще дополнительное условие на наборы простых чисел! Наборов простых чисел получается совсем немного. Для четных N у меня программа выдает наборы простых чисел разбитые на три группы. Отдельно простые числа для прямых диагоналей, обратных диагоналей и остальное для строк и колонок. Что сильно сокращает перебор при работе основоного алгоритма.

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

[Nataly-Mak]

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

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

Стоп! Если я не ошибаюсь, Pavlovsky говорил прямо противоположное

-- Пн янв 07, 2013 14:07:10 --

Вот здесь смотрим:

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

Но я бы поработал над выбором схемы. Схема 2,14,8,6,6 имеет теоретическую оценку 1760. Что далековато от 1752. Надо поискать схему теоретическая оценка которой близка к 1752. Увы мои алгоритмы поиска схем заточены на поиск схем близких к оптимальной. Схемы с теоретической оценкой рядом с 1752 искать отказываются.

Кстати, Vovka17 обещал выложить решение 1752. Мне очень интересно, какая в этом решении схема.

[Pavlovsky]

Для четных N

Цитата:

Зачетных прямых диагоналей должно быть N/2, зачетных обратных диагоналей тоже должно быть N/2. Если квадрат раскрасить в черно-белые цвета, как шахматную доску. То зачетные диагонали должны быть одноцветными (либо черными, либо белыми). Отсюда сумма зачетных прямых диагоналей должна равняться сумме зачетных обратных диагоналей.

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

-- Пн янв 07, 2013 15:15:41 --

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

С точностью до изоморфизма существует только одна схема со структурой
2,14,8,6,6 и только одна двойственная ей схема со структурой 6,6,8,14,2.
Этими двумя классами изоморфных схем исчерпываются все схемы с
максимальной оценкой 1760.

Если по этим схемам искать решение 1760. Для схемы со структурой 2,14,8,6,6 нет допустимых наборов простых чисел. Для схемы со структурой 6,6,8,14,2 существует 4 допустимых набора простых чисел. Основной алгоритм максимум чего выжал это 6 выставленных линий.