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

[whitefox]

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

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

Это мираж. Одноцветные строки здесь не причём. Просто существуют сильные прямоугольники которые в принципе не возможно увеличить на две строки.

[Nataly-Mak]

Pavlovsky
напрасно вы мне не верите, что длинные одноцветные строки ничуть не мешают добавлять две строки.
Вот вам ещё один пример (я на этом добавлении двух строк собаку съела
рассмотрела десятки примеров, начиная с малых С и кончая большими):



Здесь справа исходная 4-сильная раскраска 16х5, а слева добавлены две строки и один цвет, в результате получена 5-сильная раскраска 18х5.
Ничуть не помешали длинные одноцветные строки!
Очень хорошо видны ячейки, заменённые в исходной раскраске на цвет Е.

-- Ср сен 05, 2012 19:31:28 --

Посмотрите ещё, к какому 9-сильному прямоугольнику 81х9 добавляет две строки и один цвет alexBlack (это из его статьи прямоугольник):



Вы можете посмотреть в статье, какой у него получился результат - 10-сильный прямоугольник 83х9. Здесь тоже всё очень просто добавляется несмотря на длинные одноцветные строки.

[whitefox]

Pavlovsky
Возьмём Ваш сильный прямоугольник и обратным изоморфным преобразованием приведём его к исходному виду:

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

Теперь сделаем ровно те замены, которые Вы указали. Получим:

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

Можете убедиться, что этот прямоугольник сильный.

[Nataly-Mak]

Занимаюсь диагональными раскрасками.
Увлекательнейшее занятие!

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

А сейчас я составляю базу данных не строго диагональных раскрасок. Вот с такими раскрасками Герберт не работал.
Я составляю такие раскраски вручную в программе Эда.
На данный момент самая большая раскраска у меня C8N32:



А что, по программе такую раскраску легко построить?

Может быть, нам организовать мини-конкурс по диагональным раскраскам?

dimkadimon
как вы на это смотрите?
Это ведь вы организовали самый первый мини-конкурс.

Да, определение строго диагональной раскраски приведено в базе данных.

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

[whitefox]

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

А что, по программе такую раскраску легко построить?

Такую (C8N32) - очень легко:

[Herbert Kociemba]

whitefox в сообщении #615241 писал(а):

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

А что, по программе такую раскраску легко построить?

Такую (C8N32) - очень легко:

Well, C8N32 is not very interesting, there are lots of diagonal tilings, also strictly diagonal, for example

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

[Nataly-Mak]

whitefox в сообщении #615241 писал(а):

Такую (C8N32) - очень легко

Ах!
А C8N64 можете? (не строго диагональную)

-- Ср сен 05, 2012 22:06:30 --

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

Well, C8N32 is not very interesting, there are lots of diagonal tilings, also strictly diagonal, for example

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

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

Вы привели даже строго диагональное решение. Интересное решение. К сожалению, в базу данных строго диагональных решений оно не вошло.

Кстати, а какое существует наименьшее строго диагональное решение для С=8 с N>49?
У нас в базе данных есть только решение C8N57.
А для 49<N<57 существуют решения?

[whitefox]

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

А C8N64 можете? (не строго диагональную)

Увы, нет.

[Nataly-Mak]

Почему?
А до какого N можете? Начиная с N=33 и до ...?

[whitefox]

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

Почему?

По трём причинам:
1. Время (для больших N программа работает слишком долго).
2. Время (у меня не так много сводного времени).
3. Время (у нас у всех осталось мало времени, так как в декабре по календарю майя наступает конец света ).

[Nataly-Mak]

whitefox в сообщении #615276 писал(а):

3. Время (у нас у всех осталось мало времени, так как в декабре по календарю майя наступает конец света ).

Подумаешь - конец света Будем работать в темноте

[whitefox]

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

Подумаешь - конец света Будем работать в темноте

Свечи я уже прикупил.

[Vitaly12]

Может быть я пропустил: на форуме infinitesearchspace где-нибудь говорилось когда должен начаться следующий конкурс?

[Nataly-Mak]

whitefox в сообщении #615280 писал(а):

Свечи я уже прикупил.

Вот и отлично

Конечно, строго диагональное решение, которое привёл Herbert Kociemba, симпатичнее



-- Ср сен 05, 2012 23:28:15 --

Vitaly12 в сообщении #615291 писал(а):

Может быть я пропустил: на форуме infinitesearchspace где-нибудь говорилось когда должен начаться следующий конкурс?

Говорилось, что перерыв будет больше месяца. Точную дату я не видела.

[dimkadimon]

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

dimkadimon
как вы на это смотрите?
Это ведь вы организовали самый первый мини-конкурс.

Вы можете организовать мини-конкурс если хотите. Меня лично диагональные решения не интересуют. Herbert доказал что строго-диагональных решений C^2 x C^2 нет для N=8, 9 и 10. Скорее всего их нет для C>10 тоже. Если я правильно понимаю, не строго диагональные решения это когда используются все 2N-1 диагонали? В таком случае они меня тоже не интересуют потому что их гораздо сложнее искать чем строго диагональные - количество диагоналей увеличивается от N до 2N-1.

Меня интересуют следующие вопросы:

1. Есть ли C5N26? Я почти уверен что есть, потому что можно заполнить 26х26 138-ю единичками.
2. Если найдём C5N26 то можно попытаться найти C5N27. Если его найдём (или докажем что он не существует) тогда можно полностью описать OBS_5.
3. Есть ли C21N401? Я почти уверен что есть, потому что уже нашёл решение с 7-ю ошибками.
4. Есть ли C10N95? Возможно. У меня есть решение с 54-ю ошибками. Дальше можно попробовать улучшить C=12, 14, 18 и 20 похожим образом.
5. Что мы можем найти для C=22? 22 это на 3 больше чем ближайшая простая степень (19), а значит такой класс мы ещё не изучали. Можно ли применить методы alexBlack в этом случае?