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

[Zealint]

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

Zealint в сообщении #580589 писал(а):

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

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

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

Надо числа добавлять одновременно в 26-ую строку и в 26-ой столбец, так будет больше шансов, что ошибки уберутся. Вы так делали?
Полный перебор вариантов здесь возможен?

Разумеется. Скажем так: мой квадрат принципиально нерасширяем (могу доказать строго). Нужно составить другой квадрат, который был бы расширяем, но это по сложности эквивалентно тому, чтобы сразу найти решение для 26x26.

[Nataly-Mak]

Zealint в сообщении #580604 писал(а):

Скажем так: мой квадрат принципиально нерасширяем (могу доказать строго). Нужно составить другой квадрат, который был бы расширяем, но это по сложности эквивалентно тому, чтобы сразу найти решение для 26x26.

Ну, по-моему сложность для квадрата 25х25 всё-таки меньше сложности для квадрата 26х26 для одного и того же значения C.
Хорошо, ваш квадрат не допускает возможность достраивания. Но! Ваш квадрат не единственный. Есть несколько других квадратов 25х25 для C=5 (просматривая сайты, видела такие квадраты). Надо попробовать все такие квадраты.

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

[dimkadimon]

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

Связь с латинскими квадратами мне вообще пришла в голову в первую же минуту старта. Как я уже говорила, сразу ввела 20 латинских квадратов, набрала 14 баллов и покрасовалась на первом месте
Любой латинский квадрат порядка n даёт решение задачи n^2 для C=n.

И не обязательно Латинский... например можно получить решение СхС вот так:

1,1,1.....1,
2,2,2,....2,
....
С,С,С,....С

[Nataly-Mak]

Это совсем тривиальное решение, такое и вводить было как-то неловко
Латинский квадрат всё же посолиднее.

Да, вы не ответили на вопрос о 5-цветном прямоугольнике 8х28.
Какое отношение к конкурсной задаче имеют виды раскрасок? Я в описании задачи ничего про виды раскрасок не вычитала, есть только условие для раскраски, оно должно выполняться. В данном прямоугольнике это условие выполняется, проверила.

[dimkadimon]

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

Да, вы не ответили на вопрос о 5-цветном прямоугольнике 8х28.
Какое отношение к конкурсной задаче имеют виды раскрасок? Я в описании задачи ничего про виды раскрасок не вычитала, есть только условие для раскраски, оно должно выполняться. В данном прямоугольнике это условие выполняется, проверила.

Читайте Def 4.1

[Nataly-Mak]

Это в статье надо читать?
Я поняла, что в статье есть какие-то три вида раскрасок.
Но где про эти виды сказано в описании задачи? Я пропустила? Дело в том, что я перевожу описание в Гугле, могла, конечно, и пропустить.

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

[Zealint]

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

Хорошо, ваш квадрат не допускает возможность достраивания. Но! Ваш квадрат не единственный. Есть несколько других квадратов 25х25 для C=5 (просматривая сайты, видела такие квадраты).

Я именно это и сказал:

Цитата:

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

Цитата:

Надо попробовать все такие квадраты.

Ну, для начала надо тогда составить их все. Пока не уверен, что это хорошая идея.

[Nataly-Mak]

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

[dimkadimon]

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

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

А что значит все имеющиеся? Ведь невозможно найти их все - их слишком много! Я нашёл только два метода получения 25х25 из 5ти цветов. Первый это который в статье, то есть который из латинских квадратов. А второй моего изобретения, но думаю что результат похож на первый.

В статье описывается strong c-coloring, то есть сильная раскраска из с цветов. Это когда нет ни одного прямоугольника в котором две левые вершины одного цвета и две правые вершины одного цвета. Например вот 2х4 2-coloring

1212
1221

но он не является strong 2-coloring из за самого левого 2х2.

[Nataly-Mak]

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

Хорошо, ваш квадрат не допускает возможность достраивания. Но! Ваш квадрат не единственный. Есть несколько других квадратов 25х25 для C=5 (просматривая сайты, видела такие квадраты). Надо попробовать все такие квадраты.

Что в этом предложении непонятно? Сказано, что существует несколько таких квадратов и предложено проверить их все, то есть все имеющиеся в наличии. Просматривая сайты, я точно видела 2-3 таких квадрата; не знаю, каким методом они построены, потому что не анализировала их. Но думаю, что есть всё-таки различные квадраты.

Есть другие идеи? Выкладывайте, если не жалко

[Pavlovsky]

Как в предыдущем конкурсе, добавили колонку "Количество человек повторивших рекорд". Любопытная картина.

В алгоритме для С простое число разобралось 13 человек.
В алгоритме для С простое число в степени разобралось 9 человек.

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

[dimkadimon]

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

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

Это алгоритм для С=р^к+1, где р простое число и к>=1.

[Nataly-Mak]

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

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

Смешное получается соревнование - кто знает больше готовых алгоритмов!
Интересны решения, полученные не по известным алгоритмам.
Я бы на месте организаторов конкурса решения, полученные по известных алгоритмам (типа C=13, N=169x169 и т.п.) вообще не засчитывала.

Я в алгоритме для С, являющихся степенью простого числа, не разобралась. Точнее не так: в алгоритме разобралась (нашла его в статье http://bit-player.org/2009/the-17x17-challenge ), квадрат для C=4, N=16x16 построила, в статье пример приведён для C=4), а вот найти комплект уникальных перестановок для C=8 не могу.
Запостила утром задачу на трёх форумах (в том числе и на этом) и... тишина. Похоже, задачка-то сама по себе (безотносительно к алгоритму) крутенькая. Что-то все математики молчат

Вот он, квадрат 16х16, который я построила по этому алгоритму:

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

Уверена, что этим методом можно построить и 8-цветный квадрат 64х64, и 16-цветный квадрат 256х256, а может быть, и 9-цветный квадрат 81х81. Но вот где комплект уникальных перестановок для n=8 и для n=16? Нету!

Вот комплект уникальных перестановок для n=4:

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

[я назвала такие перестановки уникальными]

Для n=8 мне удалось написать только 2 группы уникальных перестановок:

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

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

Ещё осталось составить 6 групп перестановок, следующая группа начинается с числа 3, потом группа перестановок, начинающихся с числа 4, и т.д. Думаю, что тут полная аналогия с перестановками для n=4.

Ну, положим, разобралась бы я в этом алгоритме, построила ещё решения для C=8, 9, 16. И что? Какой интерес в использовании готовых алгоритмов? Не вижу никакого интереса, чисто техническая работа.

Вот вспомогательная задача про уникальные перестановки мне гораздо больше понравилась!
Что-то решить её никто не может пока. Это для n=8, а для n=16 вообще мрак. Там же астрономическое количество всех перестановок! Ну, если выявить правило составления уникальных перестановок, тогда никакой сложности не будет.

Вообще интерес к этому конкурсу у меня стремится к нулю. Искать готовые алгоритмы нет никакого желания.

Здесь запостила задачу об уникальных перестановках:
topic59550.html

Ответов ноль
И ещё на двух форумах запостила. Там тоже тишина. На одном форуме нашли 24 уникальных перестановки. Я их и больше могу найти по программе, написанной для одной группы (для перестановок, начинающихся с числа 2). Но вот если их все найти (полный комплект), то их наверное будет точно 64. Вот в чём фишка!

(Оффтоп)

Знакомому одному написала задачку. Он сначала ответил: "Так это же тривиальные перестановки!" Я ему пишу: "Так давайте мне эти тривиальные перестановки". Что-то пока не даёт
Может быть, они и действительно тривиальные. Не возражаю. Для тех, кто знает правило их составления, они тривиальные. Я это правило пока не знаю.

[Pavlovsky]

Nataly-Mak
Возми полный набор латинских квадратов 8х8, получишь 8*7=56 перестановок.

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

[Nataly-Mak]

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

Nataly-Mak
Возми полный набор латинских квадратов 8х8, получишь 8*7=56 перестановок.

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

Цитата:

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

Так если вы знаете решение этой задачи, выкладывайте.
Это пока я ещё разберусь с системами Штейнера или Киркмана, конкурс закончится к тому времени
Ну, и пусть не будет у меня квадратов 64х64, 81х81 и 256х256, нисколько не расстроюсь.
Вообще подумываю бросить эту задачу.

-- Вт июн 05, 2012 21:01:56 --

Кстати, в ЛК 8-го порядка перестановки не уникальные в смысле данного мной определения уникальных перестановок. Вот, например, первые два ортогональных ЛК 8-го порядка:

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

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

Очевидно, что здесь полно пересечений.