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

[Zealint]

Nataly-Mak, это задача известная и я уже говорил, что для случая степеней простых чисел давно известно решение, дающее $c^2\times c^2$. Однако из этого не следует, что конкурс превращается в поиск готовых алгоритмов. Дело в том, что для других составных чисел данная задача является известной нерешённой проблемой. Так что там как раз и нужно сочинить что-то новое. Это один.

Для степеней простых чисел непонятно, как получать квадраты размером,
равным хотя бы $(c^2+1)\times (c^2+1)$. Так что думать как раз нужно именно над этим. Это два.

Ну и три: попробуйте составить квадрат 26x26 для c=5. Это интересно. Готовых нет ни алгоритмов, ни решений.

Короче, я бы не стал так утрировать. И не стал бы требовать от современных математиков решение этой задачи. Её уже очень много лет никто решить не может. Почему Вы считаете, что решение возникнет прямо сейчас на каком-то форуме? Это было бы здорово, но уж очень маловероятно.

-- Вт июн 05, 2012 21:00:27 --

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

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

Да, и существуют 3 человека, которые не сдали квадрат 4x4 для C=2. Меня часто именно такие случаи интересуют... что же замышляют эти люди?

[Nataly-Mak]

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

Короче, я бы не стал так утрировать. И не стал бы требовать от современных математиков решение этой задачи. Её уже очень много лет никто решить не может. Почему Вы считаете, что решение возникнет прямо сейчас на каком-то форуме? Это было бы здорово, но уж очень маловероятно.

Вы ничего не поняли!
Я не прошу на форумах решать конкурсную задачу, которую уже много лет никто решить не может (где вы такое видите?)

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

И вообще задача про уникальные перестановки - это вспомогательная задача, к которй меня привёл алгоритм, найденный мной в статье. Сам алгоритм я прекрасно поняла, квадрат 16х16, построенный по этому алгоритму, здесь показала. Уверена, что и для C=8, 16 этот алгоритм работает.

Ну, а какие задачи мне попробовать решать, в этом я сама как-нибудь разберусь без ваших советов.

Кстати, о давно известном решении для степеней простых чисел первым тут, по-моему, сказал Pavlovsky, а не вы. И как я помню, вы тоже не сразу нашли разбиения для C=9.

Да, а вы знаете решение задачи про уникальные перестановки для n=8 и n=16?
Нет, нет, мне от вас решения не надо! Просто интересно, знаете ли вы его.

-- Вт июн 05, 2012 22:19:22 --

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

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

Посмотрел, действительно где то накосячил.

для C=9 есть 7 разбиений (1,0)(1,1)(1,2)(1,4)(1,5)(1,7)(1,8) нужно найти еще два.

Поскольку я пока не разобрался, как именно Вы считаете эти шаги в случае $p^s$, предлагаю Вам и отыскать ещё два разбиения.

Улыбнуло "предлагаю Вам и отыскать ещё два разбиения"

Ну, вот вы и отыскали ещё два разбиения, а я пока не отыскала.

[Pavlovsky]

Три базовых алгоритма реализовано. Теперь надо думать куда двигаться дальше.
1) Искать решения для С=5, больше С^2
2) Искать решения C^2 для С=6,10
3) Искать вменяемое решение для С=15,21

[Nataly-Mak]

Pavlovsky
хотела бы услышать ответ на вопрос: где вы видите в ортогональных ЛК 8-го порядка уникальные перестановки в количестве 56 штук?
Выше привела два ортогональных квадрата, в них совсем не уникальные перестановки.
Уникальные перестановки я вижу только в одном из 7 квадратов - любом.
Таких перестановок всего 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

В остальных 6 квадратах просто переставляются эти строки, и понятно, что никакой уникальности уже нет, все перестановки пересекаются.

Интересное совпадение количества баллов:

2  Tom Sirgedas 19.684100 06-05-2012 @ 00:00:26
3  Artem Karavaev 19.684100 06-05-2012 @ 09:50:07
4  Valery Pavlovsky 19.684100 06-05-2012 @ 23:19:08
5  Jarek Wroblewski 19.284200 06-04-2012 @ 08:14:00
6  Anton Voropaev 19.284200 06-04-2012 @ 15:38:59

Может, эти баллы и дали три базовых алгоритма
А конкурсанты с 5-6 места ещё не реализовали третий алгоритм и поэтому чуть-чуть не дотягивают до 19,6841. Вот как реализуют, у них тоже будет 19,6841 баллов, да?

И если все конкурсанты эти три базовых алгоритма реализуют, у всех будет 19,6841 баллов
Красивое соревнование - именно в знании базовых алгоритмов.

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

И очевидно что, скажем, реализация алгоритма, изложенно выше Pavlovsky, всем конкурсантам даёт абсолютно одинаковое количество баллов, а именно:
за C = 2, 3, 5, 7, 11, 13, 17, 19 (простые числа) - 8 баллов,
за C = 4, 8, 9, 16 (степени простых чисел) - 4 балла.

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

Шуточное предложение администратору конкурса: снять со всех конкурсантов баллы, полученные готовыми алгоритмами, а также баллы за решения, содранные в Интернете.

Своей головой думать надо, господа!

-- Ср июн 06, 2012 05:57:56 --

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

Все 12 чисел подпадающих под теорему 4.12 я отработал.

6 Valery Pavlovsky 12.000000 06-01-2012 @ 21:45:59

Эта цитата подтверждает мои слова.

Возражения есть?

-- Ср июн 06, 2012 06:05:19 --

А я пока реализовала только часть алгоритма, выложенного Pavlovsky, для C = 2, 3, 5, 7, 11, 13, 17, 19, 4.
Откуда у меня такой результат?

12  Natalya Makarova 16.336600 06-03-2012 @ 14:06:34

[dimkadimon]

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

Шуточное предложение администратору конкурса: снять со всех конкурсантов баллы, полученные готовыми алгоритмами, а также баллы за решения, содранные в Интернете.
Своей головой думать надо, господа!

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

1. Эти алгоритмы далеко не очевидны. Я бы даже не стал их называть "базовами" или "классическими", только 9-13 человека их нашли. Сначала надо понять и разобратся в статье а потом их написать. Разборка в статьях и известных результатах это часть задачи. Это работа ученого в любой науке - сначала он должен разобраться в известных результатов, а потом их улучшать. Мы стоим на плечах научных гигантов.

2. Есть совсем другие алгоритмы которые дают похожие результаты.

3. Я почти уверен что результат С^2 х С^2 для С цветов не оптимален и можно найти лучше решения. Есть гипотеза что существуют (С^2+С-2) х (С^2+С-2) для С цветов.

Остальные доводы вам описал zealint.

[Zealint]

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

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

Хорошо, возражение принимается. Только оно ничего не меняет.

Цитата:

Кстати, о давно известном решении для степеней простых чисел первым тут, по-моему, сказал Pavlovsky, а не вы. И как я помню, вы тоже не сразу нашли разбиения для C=9.

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

Цитата:

Да, а вы знаете решение задачи про уникальные перестановки для n=8 и n=16?

Нет. Термин мне не знаком, задачу никогда не встречал.

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

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

Ничего я не отыскал. Решал другим способом, не тем, который описан в статье. Так что не нужно думать, что все решают задачу ТОЛЬКО так, как написано в чьей-то научной работе.

Цитата:

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

И очевидно что, скажем, реализация алгоритма, изложенно выше Pavlovsky, всем конкурсантам даёт абсолютно одинаковое количество баллов

Да, но из этого не следует, что происходит именно так. Например, я точно знаю, что есть один участник из России, который ни одну статью даже не открывал. У него из степеней простых чисел сдано на максимальный балл все, кроме c=3,4. Но как! Как же он это сделал?? Наверное, как нам подсказывает dimkadimon:

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

2. Есть совсем другие алгоритмы которые дают похожие результаты.

[Nataly-Mak]

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

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

1. Эти алгоритмы далеко не очевидны. Я бы даже не стал их называть "базовами" или "классическими", только 9-13 человека их нашли. Сначала надо понять и разобратся в статье а потом их написать.

Это просто не все конкурсанты статью прочитали
Насчёт неочевидности...
Да, наверное, не все одинаково хорошо умеют разбираться в статьях. Согласна.
Я, к примеру, вообще англоязычные статьи читать не могу. Тем не менее, в другой статье (тоже англоязычной) я нашла алгоритм построения C=4, N=16x16 и прекрасно в нём разобралась. Ничего сложного, всё очевидно!
Точно так же нет ничего сложного для C простых, то, что изложил Pavkovsky по-русски, это я поняла сразу.
А вот для C, являющихся степенью простого числа, Pavlovsky зажал перевод
И поэтому я в этом не разобралась. Но, как уже сказала, нашла алгоритм в другой статье. И теперь у меня загвоздка только за уникальными перестановками, которые составить пока не умею. Но это опять же дело техники, алгоритм-то есть готовый и он работает, проверено (чуть ниже ещё о проверке этого алгоритма).

У вас есть возражения против 12 халявных баллов?
Все, кто читал статью и знает об этом алгоритме, эти баллы набрали сразу же.

Цитата:

Остальные доводы вам описал zealint.

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

А теперь о проверке алгоритма, найденного мной в одной из статей.
Итак, я беру известные мне уникальные перестановки для n=8, добавляю к ним квадрат 8х8, каждая строка которого составлена из одинаковых чисел, и получаю такой базовый прямоугольник 22х8:

1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8
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

Если найти все 56 уникальных перестановок, этот базовый прямоугольник будет иметь размеры 64х8.
Теперь составляю на базе прямоугольника 22х8 8-цветный прямоугольник 22х64 по указанному алгоритму, вот этот прямоугольник:

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

К сожалению, программа Эда не берёт этот прямоугольник для проверки (а жаль!). Картинка в программе при вводе этого прямоугольника получается такая:



Но визуально я не вижу ошибок в этом прямоугольнике! Мне кажется, что он удовлетворяет условию задачи.

Итак, базовый прямоугольник 22х8 я проверила. Всё получилось.

[Zealint]

Цитата:

Своей головой думать надо, господа!

Это верно всегда, но не всегда это следует доводить до абсурда. Как думаете, компьютер изобрёл ровно один человек, прорабатывая всю математику и вычислительную технику с нуля? И паяльник он тоже сам придумал?

Я лично так понимаю смысл конкурса: чтобы хоть кто-то, хотя бы один человек отыскал решение, выходящее за рамки известных алгоритмов. Например, 225 для c=15. Вот, скажем, в моих конкурсах есть задачи, которые для небольших значений входного параметра уже были решены ранее (и ответ можно было отыскать в энциклопедии). Но для того, чтобы её пробить дальше, нужно было сочинять что-то новое или более эффективное. Вот это новое ожидают и здесь.

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

Никаких доводов я там не увидела.

Это плохо. Это значит, что нужно пока перестать Вам что-то объяснять.

-- Ср июн 06, 2012 06:44:18 --

Цитата:

Но визуально я не вижу ошибок в этом прямоугольнике! Мне кажется, что он удовлетворяет условию задачи.

[совет]Почему бы не написать программу, которая проверяет Ваши прямоугольники?[/совет]

[Nataly-Mak]

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

Я лично так понимаю смысл конкурса: чтобы хоть кто-то, хотя бы один человек отыскал решение, выходящее за рамки известных алгоритмов. Например, 225 для c=15. Вот, скажем, в моих конкурсах есть задачи, которые для небольших значений входного параметра уже были решены ранее (и ответ можно было отыскать в энциклопедии). Но для того, чтобы её пробить дальше, нужно было сочинять что-то новое или более эффективное. Вот это новое ожидают и здесь.

У меня тоже были конкурсы, целых два, на этом форуме.
И вот для задач моих конкурсов нет ни готовых алгоритмов, ни готовых решений. И потому их почти никто не решил. Решил всего одну задачу Алексей Чернов (постоянный участник и ваших конкурсов). Это сильнейший в России программист, равных ему я пока не знаю.

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

Никаких доводов я там не увидела.

Цитата:

Это плохо. Это значит, что нужно пока перестать Вам что-то объяснять.

Я в ваших объяснениях совсем не нуждаюсь.

[dimkadimon]

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

У вас есть возражения против 12 халявных баллов?
Все, кто читал статью и знает об этом алгоритме, эти баллы набрали сразу же.

Да есть! Эти балы не халявные. Если бы они были халявные тогда их бы все набрали, но их не все набрали. Даже если их все набирут то это ничего не изменит - просто у всех будет на 12 балов больше, а ранг не изменится. Читать статью не обязательно чтобы набрать эти балы, как я вам уже говорил есть другие методы набрать эти балы. Кстати некоторые из этих "других" методов даже проще чем тем которые написаны в статье и на этом форуме.

[Nataly-Mak]

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

Цитата:

Но визуально я не вижу ошибок в этом прямоугольнике! Мне кажется, что он удовлетворяет условию задачи.

[совет]Почему бы не написать программу, которая проверяет Ваши прямоугольники?[/совет]

В советах тоже не нуждаюсь

-- Ср июн 06, 2012 07:56:07 --

[quote="dimkadimon в [url=http://dxdy.ru/post581372.html#p581372]сообщении #581372
[/url]"]
Эти балы не халявные. Если бы они были халявные тогда их бы все набрали, но их не все набрали.[/quote]

Это дело времени, все проснутся как следует и всё увидят.

Цитата:

Даже если их все набирут то это ничего не изменит - просто у всех будет на 12 балов больше, а ранг не изменится.

Вот я и предлагаю списать со всех эти 12 баллов

Цитата:

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

Тогда почему же вы выступали против обсуждения этого алгоритма здесь?

-- Ср июн 06, 2012 08:12:33 --

Zealint
по поводу уникальных перестановок. Да, термин этот мой, я так назвала эти перестановки. Но придумала их, увы, не я.

Вот в этой статье я нашла эти перестановки и алгоритм построения 4-цветного квадрата 16х16:
http://bit-player.org/2009/the-17x17-challenge

Показываю уникальные перестановки из этой статьи для n=4:


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

[Nataly-Mak]

Наверное, следующее утверждение очевидно:

если в правильном C-цветном квадрате NxN удалить любую строку и любой столбец, получится правильный C-цветный квадрат (N-1)x(N-1).

[правильный - удовлетворяющий условию конкурсной задачи]

Пример

это 4-цветный квадрат 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

Удаляю из этого квадрата наугад одну строку и один столбец, получаю 4-цветный квадрат 15х15:

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

Очень полезное свойство!

А в топике "Уникальные перестановки" по-прежнему ноль ответов

[Nataly-Mak]

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

Ввожу вот такое решение С=4, N=256:

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

Программа Эда выдаёт такое решение:

@,A,B,C,@,A,B,C,@,A,B,C,@,A,B,C,
,B,C,@,A,B,C,@,A,B,C,@,A,B,C,@,
,C,@,A,B,C,@,A,B,C,@,A,B,C,@,A,
,@,A,B,C,@,A,B,C,@,A,B,C,@,A,B,
,A,B,C,A,B,C,@,B,C,@,A,C,@,A,B,
,A,B,C,B,C,@,A,C,@,A,B,A,B,C,@,
,A,B,C,C,@,A,B,A,B,C,@,B,C,@,A,
,B,C,@,@,A,B,C,C,@,A,B,B,C,@,A,
,B,C,@,B,C,@,A,@,A,B,C,C,@,A,B,
,B,C,@,C,@,A,B,B,C,@,A,@,A,B,C,
,C,@,A,@,A,B,C,A,B,C,@,C,@,A,B,
,C,@,A,A,B,C,@,C,@,A,B,@,A,B,C,
,C,@,A,C,@,A,B,@,A,B,C,A,B,C,@,
,@,A,B,@,A,B,C,B,C,@,A,A,B,C,@,
,@,A,B,A,B,C,@,@,A,B,C,B,C,@,A,
,@,A,B,B,C,@,A,A,B,C,@,@,A,B,C

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



Почему в окне программы написано, что 3 цвета, когда здесь фактически 4 цвета? Это сбивает с толку!

-- Ср июн 06, 2012 14:25:10 --

По поводу достраиваемости квадратов...

Сейчас взяла вот это решение C=5 N=289, найденное в Интернете:

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

Легко достроила в программе Эда до решения C=5, N=324:

@,B,@,C,C,A,D,A,A,B,A,A,@,@,B,C,D,D,
,@,C,C,A,D,C,B,B,A,A,@,@,D,C,D,D,A,
,C,C,A,D,B,B,B,A,A,@,@,D,C,D,D,A,@,
,C,A,D,C,B,C,A,B,@,@,D,C,D,D,A,@,B,
,A,D,C,B,B,A,A,@,@,D,C,D,D,A,@,B,@,
,D,C,B,B,A,A,@,@,D,C,D,D,A,@,B,@,C,
,C,B,B,A,A,@,@,D,C,D,D,A,@,B,@,C,D,
,B,B,A,A,@,@,D,C,D,D,A,@,B,@,C,D,C,
,B,A,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,
,A,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,
,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,B,
,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,B,A,
,@,D,C,D,D,A,@,B,@,C,D,C,C,B,B,A,A,
,D,C,D,D,A,@,B,@,C,D,C,C,B,B,A,A,B,
,C,D,D,A,@,B,@,C,D,C,C,B,B,A,A,B,@,
,D,D,A,C,B,@,C,D,C,C,B,B,A,A,B,@,A,
,D,A,@,B,C,C,D,C,C,B,B,A,A,B,D,A,@,
,A,@,B,@,C,D,C,B,B,D,A,A,C,D,A,@,A

Этот пример показывает, что есть решения, которые достраиваются очень легко.

Я пока не пробовала достраивать квадраты 25х25 для C=5, их ещё надо снова искать в Интернете, если они там есть. То есть надо найти варианты отличные от того, какой есть у меня, этот действительно с ходу не достраивается, но полным перебором я его не проверяла.

-- Ср июн 06, 2012 14:46:06 --

И далее рещение C=5, N=324 легко достраивается до решения C=5, N=361

@,B,@,C,C,A,D,A,C,B,A,B,@,@,B,C,D,D,D,
,@,C,C,A,D,B,B,B,A,A,@,@,A,C,D,D,A,@,
,C,C,A,D,B,B,A,A,A,@,@,D,C,D,D,B,@,B,
,C,A,D,B,A,B,C,A,@,@,D,B,D,A,C,D,B,@,
,B,D,C,B,C,A,B,@,@,D,C,D,D,A,@,B,@,C,
,A,C,B,B,A,A,@,@,D,C,D,D,A,@,B,@,C,D,
,C,B,B,A,B,@,@,D,C,D,D,A,@,A,@,C,B,C,
,B,B,A,A,@,@,D,C,D,D,A,@,B,@,B,D,C,C,
,B,A,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,
,A,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,B,
,A,@,@,D,C,D,D,A,@,B,@,C,D,C,C,B,B,A,
,@,@,D,C,D,D,A,@,B,@,C,D,C,A,B,B,A,A,
,@,D,C,D,D,A,@,A,@,C,D,C,C,B,B,A,A,B,
,D,C,D,D,A,@,B,@,C,D,C,C,B,B,A,A,B,D,
,C,D,D,A,@,C,@,C,D,C,C,B,B,C,A,B,@,A,
,D,D,A,C,B,@,B,D,C,C,B,B,A,A,B,@,D,@,
,D,A,@,B,C,C,D,B,C,B,D,A,A,B,D,A,@,A,
,A,@,B,@,C,D,C,C,B,D,A,A,C,D,A,@,A,B,
,@,B,@,C,D,C,C,B,D,A,A,C,D,A,@,A,D,B

До какого максимального квадрата это решение можно достроить?

[dimkadimon]

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

Почему на картинке в программе в первом столбце только один символ? Почему квадрат не изображается в нормальном виде со всеми заполненными ячейками?

Вы неправильно ввели квадрат в программу. Надо вводить все цифры одной строчкой через запитую.

[Nataly-Mak]

Большое спасибо!

Попробовала так ввести. Действительно, всё получилось очень хорошо, квадрат нормальный, количество цветов указано верно.