2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 28, 29, 30, 31, 32, 33, 34 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 10:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И 34х34 есть!!

-- Сб июн 23, 2012 11:51:08 --

И 35х35 есть!

Обратите внимание, как быстро достраиваю :-)

Вот теперь действительно остался последний шажочек.
Неужели не достроится? Быть такого не может!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 10:55 
Аватара пользователя


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


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

PS Сергей почему не учавствуете в конкурсе? Зачем отличные решения складывать под подушку?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Всё! Последний рубеж пройден, решение C=6, N=36x36 получено!

А дьявольски красивое получилось решение. Ну, пока не буду показывать :-)

Конечно, диагональное красивее, но у меня пока диагонального нет.

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

Pavlovsky
вы сообщали, что в книге Картеси описывается построение диагональных решений.
И вы даже экспериментировали с этим методом, но ничего хорошего не нашли.

А вот, оказывается, существует весьма интересное диагональное решение 36х36 для C=6.
Не исключено, что существует и диагональное решение 100x100 для C=10.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:23 
Аватара пользователя


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

А почему неверно??

В первом, приведенном Наталией решении, в один цвет красятся разорванные диагонали.
Во втором, приведенном Наталией решении, в один цвет красятся диагонали. То есть разорванная диагональ может быть покрашена в два цвета.

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

-- Сб июн 23, 2012 13:26:14 --

Nataly-Mak в сообщении #588132 писал(а):
Pavlovskyвы сообщали, что в книге Картеси описывается построение диагональных решений. И вы даже экспериментировали с этим методом, но ничего хорошего не нашли.А вот, оказывается, существует весьма интересное диагональное решение 36х36 для C=6.Не исключено, что существует и диагональное решение 100x100 для C=10.


В своих планах исследования я уже снял с этого направления пометку "малоперспективно".

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:34 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #588131 писал(а):
Сергей почему не учавствуете в конкурсе? Зачем отличные решения складывать под подушку?
Пока особых успехов нет. С грехом пополам только что разобрался с GF(16), т.е. вышел на результат 13. Пора переходить к составным C - для C=6 просто перебор был быстрым. Картинки, правда, удалось получить красивыми даже для всех простых C, что и завораживает. Это не чистые диагонали, но явно просматривается диагональная структура.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:43 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Мне удалось достраиванием только что полученного решения 36х36 получить прямоугольник 37х36 6-coloring! И тоже весьма интересный прямоугольник получился.

Кто-нибудь пробовал получить решение 37х37 для C=6?

-- Сб июн 23, 2012 12:52:05 --

Кстати, я стала 14-ым участником, одолевшим решение C=6, N=36x36:

Код:
6 36 1296  Alex Chernov @ 23:02:26 on 05-31-2012 14

svb
вы вступите в игру, когда наберёте 19,99 баллов? :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:56 
Аватара пользователя


21/02/10
1594
Екатеринбург
Цитата:
5 Artem Karavaev 19.823100 06-23-2012 @ 10:44:21

Artem Karavaev вышел за пределы джентельменского набора решений!

Код:
14  Sigi S 18.946100 06-21-2012 @ 23:36:50
15  Natalya Makarova 18.908400 06-23-2012 @ 14:02:34


Дамский набор решений тоже радует. :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:04 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
13 Wes Sampson 18.979700 06-10-2012 @ 07:54:57
14 Sigi S 18.946100 06-21-2012 @ 21:36:50
15 Natalya Makarova 18.908400 06-23-2012 @ 12:02:34
16 Martin Richardt 18.521200 06-17-2012 @ 16:24:47
17 Aicke Hinrichs 18.431700 06-22-2012 @ 00:52:34
18 Markus Egli 18.430000 06-11-2012 @ 15:51:59
19 Roy van Rijn 18.324600 06-22-2012 @ 12:00:09
20 Rodolfo Niborski 18.030100 06-20-2012 @ 10:42:01

Все эти конкурсанты находятся в зоне 18 баллов с хвостиком.
Высокий порог! За ним идёт последняя зона - 19 баллов с хвостиком.

-- Сб июн 23, 2012 13:12:47 --

Pavlovsky в сообщении #588153 писал(а):
Дамский набор решений тоже радует. :D

Pavlovsky
если бы вы были джентльменом и помогли даме разобраться с теоремой 4.12 (под помощью я имею в виду чисто техническую помощь - нормальный перевод текста на русский язык; никакие подсказки мне не нужны!), то дама, возможно, имела бы джентльменский набор решений.

Но вы, увы, не джентльмен :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:13 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #588132 писал(а):
Не исключено, что существует и диагональное решение 100x100 для C=10.


Если будем расскрашивать разорванные диагонали в один цвет. Тогда решение определяется первой строкой. Это 10^100 вариантов. Цифра завораживает, даже если удастся:

1) Определить условия корректности первой строки без необходимости строить остальной квадрат.
2) Будут хорошие отсечения.
3) Просто повезет быстро построить корректную первую строку.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:21 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #588159 писал(а):
1) Определить условия корректности первой строки без необходимости строить остальной квадрат.

Так ведь всё и определяется именно первой строкой.
Только вот в одних случаях эта строка имеет длину n, а в других случаях длину 2n-1 (n - сторона квадрата).

Я пока не поняла, в каких случаях первое, а в каких - второе.
Моя гипотеза такая: для чётных n строка имеет длину n, а для нечётных n - строка имеет длину 2n-1.

В имеющихся у меня примерах для n=16 строка имеет длину 16, для n=17 строка имеет длину 33.

Предполагаю, что для C=6 в квадрате 36х36 всё определяется первой строкой квадрата длиной 36. Далее идёт нормальный циклический сдвиг по строкам.

Если моя гипотеза верна, то для C=10 всё будет определяться первой строкой квадрата 100х100 длиной 100. Даже если это так, найти правильную первую строку очень сложно.

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

-- Сб июн 23, 2012 13:37:02 --

Цитата:
Моя гипотеза такая: для чётных n строка имеет длину n, а для нечётных n - строка имеет длину 2n-1.

Нет, неверная гипотеза. Это зависит, наверное, не от стороны квадрата, а от количества цветов.

Посмотрела все диагональные решения для C=5, во всех надо искать строку длиной 2n-1.

Тогда такая гипотеза:
для С чётных строка длиной n, для С нечётных строка длиной 2n-1.

-- Сб июн 23, 2012 14:16:30 --

Почти диагональное решение 22х22 7-coloring:

Изображение

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 13:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И почти диагональное решение 23х23 8-цветное:

Изображение

Мне очень нравятся диагональные решения :D

Ну, хорошо. Для C=4 и С=5 я здесь привела диагональные решения из статьи.
Для С=6 у svb такое решение под подушкой :D

А для С=3 существует диагональное решение? Скажем, 9х9 или 10х10.

-- Сб июн 23, 2012 14:53:03 --

А вот оно! :-)

Изображение

Стоп!
Наврала. Это решение 4-цветное.
Я сделала в программе Эда уменьшение количества цветов с 4-х до 3-х, думала, что всё автоматически и уменьшилось. А сейчас рассмотрела внимательно, здесь по-прежнему 4 цвета.

-- Сб июн 23, 2012 15:16:18 --

Пока для C=3 получилось только диагональное решение 6х6:

Изображение

-- Сб июн 23, 2012 15:27:38 --

Это решение в числах:

Код:
1,3,3,2,1,1,
3,3,2,1,1,2,
3,2,1,1,2,1,
2,1,1,2,1,2,
1,1,2,1,2,3,
1,2,1,2,3,3

Здесь происходит циклический сдвиг строки из 11 элементов:

Код:
1,3,3,2,1,1,2,1,2,3,3

Гипотеза вроде бы подтверждается, здесь С нечётное.

Кто может представить диагональное решение для C=3 бОльшего размера?

-- Сб июн 23, 2012 15:37:43 --

И наконец диагональное решение для С=2 4х4:

Изображение

В числах:

Код:
1,1,2,2,
1,2,2,1,
2,2,1,1,
2,1,1,2

Здесь нормальный циклический сдвиг по строкам.
Опять гипотеза подтверждается!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 14:41 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak писал(а):
Кто может представить диагональное решение для C=3 бОльшего размера?

Код:
A,A,B,A,B,C,C,B,C,
A,B,A,B,C,C,B,C,A,
B,A,B,C,C,B,C,A,A,
A,B,C,C,B,C,A,A,B,
B,C,C,B,C,A,A,B,A,
C,C,B,C,A,A,B,A,B,
C,B,C,A,A,B,A,B,C,
B,C,A,A,B,A,B,C,C,
C,A,A,B,A,B,C,C,B,

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 14:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
О!
Спасибо! Очень красиво.
Сейчас перепишу в числах, проанализирую. Мне почему-то с символами совсем не нравится работать, я привыкла работать с числами.

А 10х10 нету?

Хотя вроде видно, что в этом решении происходит нормальный циклический сдвиг по строкам.

Значит, моя гипотеза неверна.

svb
а для C=5 есть диагональное решение, в котором происходит нормальный циклический сдвиг по строкам?
Среди решений, приведённых в статье, такого решения нет (со стороной квадрата 17, 18, 19, 20).

Предположу, что максимальное диагональное решение для C цветов имеет размер C^2xC^2.
Вот для C=3 9x9 представили, а 10х10 уже нет?
Для С=4 16х16 есть в статье.
Для С=5 25х25 и для C=6 36x36 есть у svb.
Для C=2 4x4 я представила.

А для C=7 49x49 у кого-нибудь есть диагональное решение?

Нет, выкладывать, конечно, не надо. Просто сообщите, что есть :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 16:04 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #588211 писал(а):
а для C=5 есть диагональное решение, в котором происходит нормальный циклический сдвиг по строкам?
Среди решений, приведённых в статье, такого решения нет (со стороной квадрата 17, 18, 19, 20).

Предположу, что максимальное диагональное решение для C цветов имеет размер C^2xC^2.
Вот для C=3 9x9 представили, а 10х10 уже нет?
Для С=4 16х16 есть в статье.
Для С=5 25х25 и для C=6 36x36 есть у svb.
Для C=2 4x4 я представила.

А для C=7 49x49 у кого-нибудь есть диагональное решение?

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 16:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А у вас есть какие-то оптимизации перебора? Ну, скажем, отсечение вариантов по каким-то критериям.
К тому же здесь ещё говорили о некоторой закономерности в первой строке - расстояния между одинаковыми цветами.
Вы всё это используете уже?

Вообще очень и очень интересный алгоритм. И работает он, видимо, для всех С.
Вот у нас уже есть для С=2,3,4,5,6. При этом решения по максимуму получаются C^2xC^2 (моё предположение).

Весьма заманчиво, однако :wink:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 28, 29, 30, 31, 32, 33, 34 ... 130  След.

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



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

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


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

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