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

[Nataly-Mak]

Всё отлично получилось с диагональным решением C10N91, вышила крестиком



dimkadimon
идея в тумане
Какой строкой, например, у вас определяется диагональное решение C5N25?
Тут раньше писали о характеристической строке, которая в данном случае будет длины 25. Это довольно длинная строка.

Хотя svb писал, что его программа построения диагональных решений находит решения для С=25,36 мгновенно. Но, как я поняла, у него присутствует перебор.
В алгоритме Герберта нет никакого перебора, всё однозначно определяется CDS.

[Herbert Kociemba]

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

Herbert Kociemba
как я понимаю, вы написали программу построения решения C10N91.
Спасибо!

К сожалению, не понимаю этот язык программирования
Я тоже немного автоматизировала процесс построения; у меня программка на языке QBASIC.

Мне интересен вопрос построения диагональных решений C^2xC^2.
Есть ли у вас идеи?
Как, например, быстро построить решения C4N16, C5N25 и т.д.?

It is written in C++ and should be possible to understand even if you only program in QBASIC. The % operator in C++ is the MOD operator in QBASIC .

Diagonal solutions exist for C4N16, C5N25, C6N36 and C7N49, but *not* for C8N64, C9N81, C11N121 and presumably not for any C>11.
To find for example a diagonal solution for C4N16 you have to find 4 difference sets with 4 elements each. In each difference set all differences have to be different mod 16, and all 16 elements are contained in these 4 sets.
For example
ds1= {0,1,3,7},ds2={2,4,13,14},ds3={5,6,10,12},ds4={8,9,11,15}
But I think there is no elegant way to derive the solution from a single difference set in this case.

[Nataly-Mak]

Herbert Kociemba в сообщении #610748 писал(а):

It is written in C++ and should be possible to understand even if you only program in QBASIC. The % operator in C++ is the MOD operator in QBASIC .

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

цвет А - (1,3,7,8,19,22,32,55,64,72), это задано в вашей таблице
цвет В - (21,23,27,28,39,42,52,75,84)
цвет С - (29,31,35,36,47,50,60,83,9)
и т.д.

А дальше простое заполнение квадрата согласно этому распределению цветов.

Цитата:

Diagonal solutions exist for C4N16, C5N25, C6N36 and C7N49, but *not* for C8N64, C9N81, C11N121 and presumably not for any C>11.
To find for example a diagonal solution for C4N16 you have to find 4 difference sets with 4 elements each. In each difference set all differences have to be different mod 16, and all 16 elements are contained in these 4 sets.
For example
ds1= {0,1,3,7},ds2={2,4,13,14},ds3={5,6,10,12},ds4={8,9,11,15}
But I think there is no elegant way to derive the solution from a single difference set in this case.

Спасибо.
Значит, в этих случаях нужно несколько комплектов разностей.

[Nataly-Mak]

Herbert Kociemba в сообщении #610748 писал(а):

For example
ds1= {0,1,3,7},ds2={2,4,13,14},ds3={5,6,10,12},ds4={8,9,11,15}

И соответствующая характеристическая строка:

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

Найти 7 комплектов из 7 элементов, чтобы построить диагональное решение C7N49, задача непростая, как мне думается.
Кто-нибудь построил диагональное решение C7N49?

-- Пн авг 27, 2012 06:11:03 --

Herbert Kociemba в сообщении #610748 писал(а):

Diagonal solutions exist for C4N16, C5N25, C6N36 and C7N49, but *not* for C8N64, C9N81, C11N121 and presumably not for any C>11.

Herbert Kociemba
Вы ничего не сказали о диагональном решении C10N100. Оно существует?

-- Пн авг 27, 2012 06:55:17 --

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

Я искал именно с нормальным циклическим сдвигом - для 5-25 и 6-36 решения есть. Для 7-49 перебор очень большой, но решение может быть.

Решение C7N49 существует, как сообщил Herbert Kociemba.

-- Пн авг 27, 2012 07:04:57 --

Ещё пример диагонального решения C4N16:
ds1={1,5,7,8}, ds2={2,11,13,14}, ds3={9,10,12,16}, ds4={3,4,6,15}

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



А вот диагональных решений для С=5 у меня нет для N>20.
По алгоритму Герберта строится решение C5N21, это сейчас построю.

Диагональное решение C5N25 пока не видела.

[Nataly-Mak]

Решение C5N21:
CDS (21,5,1) 3,6,7,12,14 (Herbert Kociemba)



Поскольку существует диагональное решение C5N25, существуют и диагональные решения для N<25 (22, 23, 24), может быть, с неправильным циклическим сдвигом.

А вот вопрос существования диагональных решений для N>C^2 остаётся открытым.
Пока не было найдено ни одного такого решения.

-- Пн авг 27, 2012 09:02:04 --

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

Так что, кто ещё не включился, включайтесь. Если не в первую, то во вторую десятку можно попасть запросто.

-- Пн авг 27, 2012 09:26:30 --

alexBlack в сообщении #589166 писал(а):

По крайней мере для одного вида решений для простых C очевидно, что при добавлении одного цвета можно увеличить размер на (C+1). Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу. При добавлении двух цветов размер можно увеличить уже на (C+1)+k. На текущий момент я знаю как
сделать k=8.

Вот это сообщение... сколько было творческих мучений, и не только у меня
Оказалось не "не так очевидно", а очень очевидно

В самом деле:
пусть C=9, строим 9-сильную раскраску 81х10; добавляем к ней строку

10,10,10,10,10,10,10,10,10,10

получаем 10-сильную раскраску 82х10. Ну и процесс завершён, из этой раскраски элементарно получаем решение 92х100 10-coloring, в котором содержатся и решение 1-го класса C10N91, и решение 2-го класса C10N92.

А вот про добавление двух цветов - это для меня пока большая тайна
Предполагаю, что именно так alexBlack получает свои решения для С=15,21.

Например, для С=13 добовляем два цвета, это будет 15-цветная раскраска; на момент написания сообщения alexBlack получал увеличение размера на (С+1)+8, то есть он имел решение C15N191.

[Herbert Kociemba]

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

Вы ничего не сказали о диагональном решении C10N100. Оно существует?

Sorry I forgot. There is no difference set of size 10 for N=100. So no solution exists.
But I have difference set solutions for C3N9, C4N16,C5N25,C6N36 and C7N49.

-- 27.08.2012, 10:29 --

And there are also diagonal solutions for example for

C5N24, characteristic line 1,3,1,2,5,2,5,4,1,3,2,3,3,2,2,4,3,4,4,5,5,1,4,5
C5N23, 5,2,3,5,5,4,3,2,2,1,1,2,4,4,5,1,4,3,4,3,3,5,2

or C6N35: 2,2,5,2,6,3,3,2,5,3,5,5,2,4,6,1,3,4,3,4,2,1,4,1,3,6,5,6,1,4,4,6,1,5,6


But I did not try to find solutions systematically.

[Nataly-Mak]

Herbert Kociemba в сообщении #611081 писал(а):

There is no difference set of size 10 for N=100. So no solution exists.

А как вы оцениваете возможность существования любого решения C10N100?
Сейчас на конкурсе найдено решение C10N94. Это максимум?

Цитата:

And there are also diagonal solutions for example for

C5N24, characteristic line 1,3,1,2,5,2,5,4,1,3,2,3,3,2,2,4,3,4,4,5,5,1,4,5
C5N23, 5,2,3,5,5,4,3,2,2,1,1,2,4,4,5,1,4,3,4,3,3,5,2

or C6N35: 2,2,5,2,6,3,3,2,5,3,5,5,2,4,6,1,3,4,3,4,2,1,4,1,3,6,5,6,1,4,4,6,1,5,6

Спасибо, это интересные решения.

Ещё такой вопрос: существует ли прямоугльник 84х10 10-strong coloring?
Я писала об этом тут:
http://infinitesearchspace.dyndns.org/c ... res?page=2

(сообщение "Hypothesis", 13/08/2012)

В данной теме ещё есть несколько сообщений по этой проблеме, например, здесь:
post605201.html#p605201

Более полная информация выложена на моём сайте:
http://www.natalimak1.narod.ru/ORT9X10.doc

[Nataly-Mak]

Диагональное решение C5N24 (Herbert Kociemba)



Красивое решение!

[Herbert Kociemba]

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

А как вы оцениваете возможность существования любого решения C10N100?

To be exactly, no diagonal solution exists. But I doubt that there is any other solution to C10N100. I also doubt, that except for small C=p^k there are solutions N>p^2k.

Concerning strong coloring, I did not deal at all with it during the contest. Strong coloring is a very significant restriction and I do not think it usually gives better results than other methods.

[Nataly-Mak]

Цитата:

Cyclic Difference Sets with k<=100

v k lambda n Status Comment
7 3 1 2 EXISTS
13 4 1 3 EXISTS
11 5 2 3 EXISTS
21 5 1 4 EXISTS
16 6 2 4 NO Lander Theorem 4.31
31 6 1 5 EXISTS
15 7 3 4 EXISTS

Herbert Kociemba
что означает n в вашей таблице CDS?

Ещё вопрос: что мы имеем для lambda=2 или 3? Это даёт какие-то решения для нашей задачи?

[dimkadimon]

Herbert Kociemba в сообщении #611148 писал(а):

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

А как вы оцениваете возможность существования любого решения C10N100?

To be exactly, no diagonal solution exists. But I doubt that there is any other solution to C10N100. I also doubt, that except for small C=p^k there are solutions N>p^2k.

Concerning strong coloring, I did not deal at all with it during the contest. Strong coloring is a very significant restriction and I do not think it usually gives better results than other methods.

Herbert, how did you check that no diagonal C10N100 existс? I would have thought that an exhaustive search would be too expensive. We require 10 sets with 10 values each, ranging from 0 to 99. This is essentially 100! How do you prune down that search space?

-- 27.08.2012, 21:34 --

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

Ещё вопрос: что мы имеем для lambda=2 или 3? Это даёт какие-то решения для нашей задачи?

Для lambda=2 мы получаем CDS где каждая разница встречается ровно 2 раза. Не вижу как такие CDS можно использовать, ведь тогда в решение появляются запрешенные прямоугольники.

[Herbert Kociemba]

dimkadimon в сообщении #611201 писал(а):

Herbert, how did you check that no diagonal C10N100 existс? I would have thought that an exhaustive search would be too expensive. We require 10 sets with 10 values each, ranging from 0 to 99. This is essentially 100! How do you prune down that search space?

All 90 possible differences must be different mod 100 in one set with 10 values. I just have a recursive procedure which adds one number after the other and use an array which keeps track of the diffences which have appeared so far. This seems to prune quite effecitively, because it takes only 5 seconds to show that there is no difference set of size 10 (if my program has no bug), let alone 10 difference sets. So the proof is easy here.
When searching for difference sets I always assume, that the first number is 0 and the second number is d (d=1,2,..), and d is the smallest distance between 2 successive numbers (mod N). So the third number has to be at least 2d+1. From these "basic" sets all other difference sets can be obtained by adding some number (mod N), a sort of cyclic shifting.

It is more difficult, if difference sets exist, for example for C8N64, where there are 2048 difference sets of size 8. But it is impossible to find 8 of them which do not overlap. To check all possibilities here took a few hours.

[dimkadimon]

Диагональных решений нет для C=10 и N>91, потому что я не смог найти CDS для N>91. А вот решение C9N80 возможно есть - я нашёл несколько подходящих CDS, например:

0 4 32 46 47 49 55 68 73
0 1 14 36 48 52 55 57 63
0 7 9 13 24 25 58 61 66
0 1 12 16 18 25 39 44 47
0 4 6 29 32 53 67 68 75

[Pavlovsky]

Сдается мне, что CDS это все таже погоня за миражами. Мои эксперименты построения сильноокрашенных прямоуголников диагональными алгоритмами показали.
1) Для С=p^s существует диаганльное решение сильноокрашенного прямоугольника.
Пример характеристическая строка для С=9.

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

Из примера виден алгоритм построения решения. Последняя строка заполняется числом 9. Все колонки являются циклической перестановкой, перестановки 1,2,3,4,5,6,7,8. Похоже здесь не обошлось без конечных полей.

2) Для С=p^s + 1. очевиден алгоритм наращивания из решения С=p^s.
Примеры.
а) характеристическая строка для С=6.

1,1,4,1,6,5,
2,2,6,2,1,5,
3,3,1,3,2,5,
4,4,2,4,3,5,
6,6,3,6,4,5,
1

Явно видна характеристичекая строка для С=5 (первые 4 строки). Некоторые диагонали заменены на число 6 и за счет этого добавлена строка 5.

б) характеристическая строка для С=10
1,1,7,1,6,9,3,7,6,1,
2,2,8,2,7,9,4,8,7,2,
3,3,1,3,8,9,5,1,8,3,
4,4,2,4,1,9,6,2,1,4,
5,5,3,5,2,9,7,3,2,5,
6,6,4,6,3,9,8,4,3,6,
7,7,5,7,4,9,1,5,4,7,
8,8,6,8,5,9,2,6,5,8,
10,10,7,10
В этом примере характерестическая строка для С=9 видна невооруженным взглядом.

[Nataly-Mak]

Pavlovsky
я что-то притупилась малость

Объясните, пожалуйста, какое отношение имеет построение сильноокрашенных прямоугольников диагональными алгоритмами к обсуждаемому здесь построению полных диагональных решений С-coloring?

Здесь приведён пример построения диагонального решения C10N91 по CDS
1,3,7,8,19,22,32,55,64,72
Это вместо характеристической строки длиной 91!

Никто ни за какими миражами не гоняется. Обсуждается замечательный алгоритм построения диагональных решений.

У вас есть что-то добавить к этому алгоритму? Вы можете добавить другие CDS, для других С и N?