Новый конкурс программистов

[Nataly-Mak]

Если убрать в программе выход по первой же найденной комбинации, получается очень много вариантов 33-ей комбинации. Вот, например, первые 20 вариантов:

1  5  2  3  9  1  10  10  2  4 
 1  5  9  9  2  3  10  10  7  8 
 2  1  6  2  6  9  9  2  7  8 
 2  1  6  5  5  9  10  2  7  8 
 2  1  10  2  9  6  9  2  7  2 
 2  1  10  5  5  9  7  2  7  4 
 2  1  10  5  5  9  10  2  7  4 
 2  1  10  5  5  9  10  2  7  8 
 2  5  5  3  5  9  10  1  7  8 
 2  5  5  3  5  10  3  1  7  8 
 2  5  5  9  5  9  10  1  7  8 
 2  5  6  3  4  5  10  7  1  8 
 2  5  6  3  6  5  10  7  1  8 
 2  5  6  5  4  5  10  7  1  8 
 2  5  7  5  4  8  3  1  7  8 
 2  5  10  3  5  9  10  1  7  8 
 2  5  10  5  5  5  10  5  1  4 
 2  5  10  5  5  5  10  5  1  8 
 2  5  10  5  5  9  10  1  7  8 
 2  6  10  5  1  4  9  5  1  8

И для каждого из этих вариантов будет море вариантов 34-ой комбинации и т. д.

[Alexu007]

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

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

Случайная генерация не дала хорошего результата.

алгоритм:

- заполняем строку длинной N случайными цифрами 1...С
- добавляем следующую (случайную) строку, проверяем две строки на соответствие условиям задачи
- если да - добавляем следующую строку, если нет - меняем предыдущую.
- если в течение 200 000 переборов нет улучшения - начинаем сначала

удалось заполнить только квадрат С5, N8*8, для N9*9 заполняет только максимум 8 строк.

Так же попробовал создавать случайные квадраты 5*5 из неповторяющихся в столбцах и строках чисел (как для судоку), формировать из 5 таких разных квадратов полосу 5*25 и далее растягивать её до 25*25 по алгоритму Nataly-Mak, но результата это не дало.

[Nataly-Mak]

Alexu007 в сообщении #585228 писал(а):

Случайная генерация не дала хорошего результата.

Ожидаемый результат.

Цитата:

Так же попробовал создавать случайные квадраты 5*5 из неповторяющихся в столбцах и строках чисел (как для судоку), формировать из 5 таких разных квадратов полосу 5*25 и далее растягивать её до 25*25 по алгоритму Nataly-Mak, но результата это не дало.

Надо создвать полосу 5х25 из неперескающихся комбинаций.
Хотя полоса 5х25 существует и из уникальных перестановок (их 20 штук, плюс 5 строк из одинаковых чисел), т. к. существует полный комплект из 4 попарно ортогональных ЛК 5-го порядка.

И вообще алгоритм построения решения C=5, N=25x25 здесь давным-давно выложен Pavlovsky.

[Alexu007]

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

Надо создвать полосу 5х25 из неперескающихся комбинаций.

Надо. А как? В смысле - рассчитывать на компе, а не подбирать что-то там руками.

[Nataly-Mak]

Alexu007 в сообщении #585238 писал(а):

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

Надо создвать полосу 5х25 из неперескающихся комбинаций.

Надо. А как? В смысле - рассчитывать на компе, а не подбирать что-то там руками.

Для С=5 всё легко решается именно руками

Найдите полный комплект из 4 попарно ортогональных латинских квадратов 5-го порядка (это легко сделать, в Интернете есть такой комплект).
Этот комплект даст вам 20 уникальных перестановок чисел 1,2,3,4,5.
Добавьте к этому набору из 20 перестановок 5 комбинаций из одинаковых чисел, и полоса 5х25 готова.
Комбинации из одинаковых чисел - это такие:

1 1 1 1 1
2 2 2 2 2
и т. д.

Например, в моей статье есть полный комплект из 4 попарно ортогональных ЛК 5-го порядка.

[Pavlovsky]

Стал десятым участником конкурса, нашедшим решение 36х36 для С=6. Если нигде не напутал, то нашел достаточно эффективный алгоритм для С=2к с оценкой С^2. На очереди решение 100х100 для С=10.
Идеи алгоритма почерпнуты в книге Ф.Картеси "Введение в конечные геометрии".

[Nataly-Mak]

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

Если нигде не напутал, то нашел достаточно эффективный алгоритм для С=2к с оценкой С^2. На очереди решение 100х100 для С=10.

Вот! Так что моя гипотеза о существовании решения C=12, N=144x144 вполне здравая

-- Пт июн 15, 2012 11:30:23 --

3 Tom Sirgedas 19.842900 06-07-2012 @ 07:11:18
4 Il brigante Pennastorta 19.842900 06-08-2012 @ 16:28:33
5 Valery Pavlovsky 19.842900 06-15-2012 @ 11:02:58

Не, ну как им это удалось? А?

Они построили для всех C совершенно одинаковые решения NxN?
А иначе как могло получиться такое совпадение общего количества баллов?

А как они построили одинаковые решения? Ответ простой. Использовали все известные алгоритмы.
Если алгоритм для C=6, N=36x36 был неизвестен, то до него легко додуматься, почитав статьи и книги.
Алексей Чернов додумался до этого алгоритма почти сразу же, на второй или третий день конкурса. Вот ещё 9 человек додумались.

А я вот пока не додумалась, потому что читать ещё не научилась
Нет, я тоже додумалась до некоего алгоритма, но для моего алгоритма нужен набор из 36 непересекающихся комбинаций, а я не могу никак его найти. 31 комбинацию нашла, а дальше ни тпру, ни ну

[Nataly-Mak]

Попробовала идею смешанного достраивания.
Цель всё та же: получить 36 непересекающихся комбинаций из чисел 1,2,3,4,5,6.

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

Такая идея. Реализована не до конца, но промежуточный результат получен, вот он - 54 полуфабриката комбинаций:

1 2 5 6 4 4
3 3 x x 6 4
x 6 6 x 1 x
6 1 2 4 x x
x 6 2 x 2 6
3 x 3 1 x 5
5 4 3 3 x 4
1 x x x 5 6
1 x 4 x 2 1
2 x 3 x x 3
x 5 4 x x x
x x 5 2 6 x
x 5 1 1 2 4
5 x 5 4 3 6
3 4 x x 4 1
5 3 6 x 5 3
x 6 x 3 4 5
1 1 1 3 1 x
4 2 4 1 3 x
2 2 x 2 x x
4 1 x x 5 5
x 4 1 2 x 3
6 x 6 1 x 6
x 3 2 3 x x
x 2 x 4 6 2
2 x 1 x 4 2
6 2 5 x x x
x 3 3 5 3 2
1 5 2 x x 2
2 1 6 6 2 x
4 4 x 5 1 x
4 x 2 2 x 1
6 5 5 x 1 5
x 6 1 x x 3
3 5 x 2 5 x
4 3 5 x 2 x
5 1 x x x 1
x 5 x x x 6
x x 4 4 5 4
x 5 6 3 6 1
1 6 x 2 3 x
3 x 5 5 x 3
5 x 2 1 1 x
6 x 1 x 6 x
x 2 3 x 1 1
x x x 4 1 3
1 4 6 4 x 5
4 x 6 x x 2
5 x 4 6 6 5
x 1 3 2 4 6
x x 1 x 3 5
x 4 x 6 x x
x x x 6 3 x
x x x 5 x 4

[могла ошибиться при переписывании; пересечений быть не должно, проверялось по программе]

Вот такая головоломка

Весьма и весьма любопытно, удастся ли из этих 54 полуфабрикатов непересекающихся комбинаций получить 36 полных непересекающихся комбинаций.

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

Но программу писать... лень, при 36-градусной жаре мозги расплавились совсем

И по-прежнему для меня отстаётся открытым вопрос: существует ли этот самый набор из 36 непересекающихся комбинаций? Может быть, это только моя фантазия
Но! Из 31 комбинации ведь существует набор! Скорее всего, и из 36 комбинаций тоже существует.

-- Пт июн 15, 2012 15:28:36 --

Развиваю идею.
Например, возьмём всего 10 комбинаций с пропущенными числами:

5 4 3 3 x1 4
x2 5 1 1 2 4
5 x3 5 4 3 6
5 3 6 x4 5 3
1 1 1 3 1 x5
4 2 4 1 3 x6
x7 3 3 5 3 2
2 1 6 6 2 x8
6 5 5 x9 1 5
x10 5 6 3 6 1

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

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

[Scryer]

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

Стал десятым участником конкурса, нашедшим решение 36х36 для С=6. Если нигде не напутал, то нашел достаточно эффективный алгоритм для С=2к с оценкой С^2.

Поздравляем! Я с нетерпением жду свой ​​цвет = 10 N = 100x100!

Очень эффективный алгоритм является сюрпризом.

-- 15.06.2012, 07:48 --

Nemiroff в сообщении #585223 писал(а):

(Оффтоп)

Неплохая стратегия: ...

Я согласен. комментарии dimkadimon интересны и полезны. Я приветствую его намеки.

[Pavlovsky]

Scryer в сообщении #585464 писал(а):

Я с нетерпением жду свой ​​цвет = 10 N = 100x100!

Увы решение 100х100 не построилось. Будем думать дальше.

[Nataly-Mak]

Scryer в сообщении #585464 писал(а):

Я согласен. комментарии dimkadimon интересны и полезны. Я приветствую его намеки.

Хм... по намёкам dimkadimon вы уж давно нашли бы решение C=10, N=100x100
Чего же вы ждёте?
По крайней мере, dimkadimon указанным способом нашёл решение C=10, N=93x93.

Хотя... кто его знает, как он нашёл своё решение. Может быть, совсем не таким способом

[dimkadimon]

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

Стал десятым участником конкурса, нашедшим решение 36х36 для С=6. Если нигде не напутал, то нашел достаточно эффективный алгоритм для С=2к с оценкой С^2. На очереди решение 100х100 для С=10.
Идеи алгоритма почерпнуты в книге Ф.Картеси "Введение в конечные геометрии".

Ух ты здорово!!! С нетерпением жду новых рекордов!

[Nataly-Mak]

Алексей Чернов снова на первом месте!

1 Alex Chernov 19.932400 06-15-2012 @ 20:53:28
2 Nick Gardner 19.899900 06-14-2012 @ 16:35:43
3 Tom Sirgedas 19.842900 06-07-2012 @ 07:11:18

У него наверняка есть оригинальные решения, которые нельзя получить по известным алгоритмам. Молодец!

Вот его пока никем не повторенные рекорды:

18 308 94864  Alex Chernov @ 22:07:18 on 06-06-2012 1
20 382 145924  Alex Chernov @ 22:11:32 on 06-06-2012 1
21 384 147456  Alex Chernov @ 17:45:54 on 06-08-2012 1

[Nataly-Mak]

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

Увы решение 100х100 не построилось.

Ну вот, а я уже ладошки приготовила для аплодисментов

А какое максимальное решение вам удалось построить для C=10?
Как я понимаю, рекордного результата 93х93 вы пока не достигли.

У меня C=10, N=82x82.
Почти уверена, что достраиванием можно прибавить хотя бы единичку к этому решению, то есть получить результат N=83x83.

Но я не реализовала этот метод. Вообще ничего не реализовала пока
Работаю только на математических идеях, как написал один конкурсант.

У меня нет даже программы проверки решений. А зачем она мне? Квадраты я проверяю в программе Эда или прямо на конкурсе, ввожу решение, если в нём ошибка, конкурсная программа это сразу говорит, решение не принимается. Тогда ищу ошибку.
А прямоугольники проверять и не обязательно.

Кстати, здесь был намёк, как решать задачу для C=10. Говорят, что полезный намёк
Для меня, увы, бесполезный.

Я пыталась найти набор непересекающихся комбинаций из чисел 1,2,3,...,10 уже давно, но у меня это не получается. Нужен, по крайней мере, набор из 83 комбинаций, меньше мне уже ничего не даёт.

-- Сб июн 16, 2012 08:50:24 --

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

Три базовых алгоритма реализовано. Теперь надо думать куда двигаться дальше.

О каких трёх алгоритмах вы здесь говорили?
Пусть:
1. для С простых чисел;
2. для С, являющихся степенью простого числа.

А какой третий?

Предположу, что это алгоритм, о котором сказал dimkadimon:
C=p^k+1, p - простое число, k>=1.
Этот алгоритм даёт много решений: С=6, 10, 12, 14, 18, 20.

Как утверждает dimkadimon, для C=6 этот алгоритм даёт решение N=31x31 (такое решение я получила другим путём).

А для других С какие решения даёт этот алгоритм?
Справедлива формула для решений: C^2-C+1?

dimkadimon говорил о каких-то исключениях из этой формулы, но я ничего не поняла. Какие исключения?
Верно, у него, например, для C=10 решение N=93x93, но, как я поняла, это он получил не по данному алгоритму, а как-то своим методом.
А формула для C=10 в этом алгоритме даёт N=91x91. Правильно ли я понимаю? Всё как в тумане, всё засекречено

Если вы об этом алгоритме говорили, так он известен, или его каждый сам изобрёл?

Под "известен" я понимаю то, что он опубликован в какой-то статье.

[Nataly-Mak]

Цитата:

Thanks to your suggestions I've been able to implement one of the three keyalgorithms (the one for prime numbers NxN). And I would like to thank you forexplaining the idea from grid.pdf!I think almost all the competitors are using a similar method to constructthe other solutions (C=6 etc).After reading the forum I've got a few ideas I'm going to try out... I'mstill for from the perfect solutions on C=6, 8, 16 etc. Almost 15 people havesolved those numbers :(

Как я понимаю, здесь тоже говорится о трёх ключевых алгоритмах (of the three keyalgorithms).

Цитата с форума конкурса.