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

[Pavlovsky]

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

Ах! А цвет С и не вписывается в оставшиеся 27 ячеек Не так всё просто, оказывается.

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

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

Подквадраты 7х7 надо раскрашивать в 5 цветов.Получается, K(1)>=9,8, то есть не меньше 10 единичек надо в этот подквадрат впихнуть.Но даже если удастся построить первый подквадрат 7х7 (а это, скорее всего, удастся), как строить следующий, чтобы он не вступал в конфликт с первым подквадратом?

Никто не общеал легкой жизни. Для сокращения перебора и обеспечения совместимости подквадратов 7х7, можно добавить регулярности , по вкусу. Строить подкавдраты специального вида. Скажем брать только такие подквадраты 7х7, чтобы подквадраты A и B в одной строке или одной колонке не давали запрещенных прямоугольников.

AB
или
A
B

[svb]

Забавно. Глядя на вас попробовал вручную заполнять 26x26. Пятью цветами заполнил весь квадрат, кроме одной клетки!

[Nataly-Mak]

Один подквадрат 7х7 раскрашивается в 5 цветов элементарно, с ходу получается, например, такое диагональное решение:

7,7,A,A,B,C,C,D,E,B,A,A,B,C,C,D,C,B,A,A,B,C,C,D,C,B,A,A,B,C,E,D,C,B,A,A,B,B,E,D,C,B,A,A,A,B,E,D,C,B,A

Но вот как раскрасить 16 таких подквадратов, чтобы они потом хорошо собрались (без конфликтов) в квадрате 28х28?

Хорошая задачка

-- Пн июл 09, 2012 09:29:53 --

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

Забавно. Глядя на вас попробовал вручную заполнять 26x26. Пятью цветами заполнил весь квадрат, кроме одной клетки!

Я тоже пробовала вручную заполнить Детские игры!

И сколько даёт ошибок (минимум) эта ваша пустая клетка?
У dimkadimon всего 2 ошибки в квадрате 26х26 оставалось.

Вы уже в одном шаге от мирового рекорда!
Впишите в пустую клетку крестик (я видела такой квадрат то ли C4N17, то ли C4N18 в какой-то статье) и опубликуйте квадрат на форуме конкурса, например.

Так напишите срочно программу "вытряхивания" ошибок (если вы её ещё не написали). Неужели всего 2-3-4 ошибки не "вытряхнутся"? А, скорее всего, и не "вытряхнутся". Фатальные ошибки!

[Pavlovsky]

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

Забавно. Глядя на вас попробовал вручную заполнять 26x26. Пятью цветами заполнил весь квадрат, кроме одной клетки!

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

[Zealint]

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

Забавно. Глядя на вас попробовал вручную заполнять 26x26. Пятью цветами заполнил весь квадрат, кроме одной клетки!

Да, знакомая картина, я такой в самом начале построил. Эта клетка у меня даёт 5 ошибок.

[svb]

Zealint

Цитата:

Да, знакомая картина, я такой в самом начале построил. Эта клетка у меня даёт 5 ошибок.

При любом цвете.

[Nataly-Mak]

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

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

У меня и сейчас эта программа работает
Добиваю проверку.

Ну, конечно, далеко не для всех исходных параметров заполняются 35 ячеек.

[Pavlovsky]

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

Для сокращения перебора и обеспечения совместимости подквадратов 7х7, можно добавить регулярности , по вкусу. Строить подкавдраты специального вида. Скажем брать только такие подквадраты 7х7, чтобы подквадраты A и B в одной строке или одной колонке не давали запрещенных прямоугольников.

Продолжу. Скажем если построить 5-strong (по строкам и по колонкам) подквадрат 7х7. Циклически поменять в нем цвета. Получится 5 подквадратов 7х7. Причем они будут обладать свойством

Цитата:

A и B в одной строке или одной колонке не давали запрещенных прямоугольников

Теперь остается заполнить матрицу 4х4 этими 5-ю подквадратами. Так чтобы в нем не было конструкции
A B
C D
Дающей запрещенные прямоугольники.

[Nataly-Mak]

И C5N28 у вас почти готов

Да, подквадраты 7х7 строить проще, чем подквадраты 13х13. Зато подквадратов 13х13 надо всего 4, а подквадратов 7х7 надо 16.
Кроме того, следует сначала получить решение C5N26, а уж потом C5N28.
Может быть, и C5N26 не существует.

-- Пн июл 09, 2012 11:36:56 --

Jarek выходит на 4-ое место.
Сильный конкурсант! Претендент на призовое место.

Стал пятым участником, нашедшим C10N93.

А я так и не нашла это решение

[Nataly-Mak]

Ну и я построила за 5 минут C5N26 с одной пустой ячейкой:



Пять ошибок любым цветом. От известного решения C5N25 строится элементарно в программе Эда.

У меня есть решение с 66 ошибками, со 154 ошибками. Ещё неизвестно, какое лучше: в котором 5 ошибок (фатальных) или в котором 66, 154 ошибки.

[Pavlovsky]

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

От известного решения C5N25 строится элементарно в программе Эда.

Без программы Эда, для С=5, элементарно строится квадрат 30х30 с вырезанным углом 5х5.
В общем случае. Для С=p^s строится квадрат размером C^2+C. С вырезанным углом СхС.

[Nataly-Mak]

И ничто не даёт решения C5N26.

26-ую строку (или 26-ой столбец) можете добавить без программы Эда?
[или без своей программы достраивания]

-- Пн июл 09, 2012 15:10:13 --

Вот он - квадрат 30х30 5-coloring с вырезанным подквадратом 5х5:

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

Любителям красоты

(Оффтоп)

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

[Pavlovsky]

Даже ежики умеют достраивать С колонок, получая прямоугольник C^2x(C^2+C). Не менее легко достроить С строк и получить прямоугольник (C^2+С)xC^2. Более того можно эти процедуры совместить. Тем самым получив квадрат размером C^2+C, с вырезанным углом СхС.

[Nataly-Mak]

Pavlovsky
этот квадрат с вызезанным углом svb ещё в прошлом году показал
Вы о чём сейчас ёжикам рассказываете?

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

Ну, вот взяла сейчас квадрат svb 30x30 с вырезанным углом 5x5, обрезала его до квадрата 26х26 и получила то самое решение с одной пустой ячейкой. Но ведь с пустой ячейкой квадрат не годится

-- Пн июл 09, 2012 15:35:09 --

Кстати, вот в этом решении с одной пустой ячейкой есть хоть один цвет, занимающий более 135 ячеек? Можно от него начинать плясать?
Я посчитала цвета А и В, насчитала только 134 ячейки для каждого цвета, дальше не стала считать.

Кажется, неправильно посчитала, трудно визуально считать.
Ещё раз пересчитала, получилось вроде по 135 ячеек. Получается так: каждый из 5 цветов занимает 135 ячеек, итого 675 ячеек, одна ячейка пустая.
Следовательно, плясать от этого решения нельзя.

[Pavlovsky]

Программа Эда показывает количество для каждого цвета. Судя по картинке, у вас всех цветов ровно по 135.