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

[Nataly-Mak]

dimkadimon
огромное спасибо. Отличные решения.

Особое спасибо за решение C3N9, которое никак не могла вручную построить; много было близких решений, уже с 4 ошибками находила.
Остальные решения проверю на изоморфность с уже имеющимися в БД и внесу, если они не изоморфны.

Завершаю работу над БД для не строго диагональных решений. БД состоит из двух частей, первая часть - для С от 2 до 8, вторая часть - для С=9,10.
Более 200 решений в БД.

Значит, теперь вопрос открыт для не строго диагональных решений C4N16, C5N25 и т.д. (для N=C^2).
И пока не найдено ни одного диагонального решения CXNY для Y>X^2.
Наверное, нет таких

[Nataly-Mak]

Вчера уже начала писать программу более конкретную для поиска не строго диагонального решения C3N9.
И вот какие мысли по поводу...

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

Смотрите:
нам нужно найти для не строго диагонального решения C3N9 характеристическую строку длины 17. Без нарушения общности можно считать, что первый элемент этой строки равен 1.
Характеристическая строка имеет вид:

1,x1,x2,x3,...,x16

Имеем 16 переменных, каждая из которых должна пробежать значения 1,2,3.
Начинаем перебор, первая диагональ:

1,x1,
x1,

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

1,x1,x2,
x1,x2,
x2,

Здесь тоже не может возникнуть запрещённый прямоугольник, т.к. x1,x2 не могут одновременно равняться единице.
Третья диагональ:

1,x1,x2,x3,
x1,x2,x3,
x2,x3,
x3,

Тут уже начинаем проверять возникновение запрещённых прямоугольников.
И так далее.

Я выше приводила пример недостроенного решения C5N26.
Да, тут характеристическая строка длинная - 51. Ну, без учёта первого элемента, который положим равным единице, остаётся 50 элементов. Каждая переменная должна пробежать значения 1,2,3,4,5.
Большой перебор? Да, большой, но, как мне кажется, не запредельный.

whitefox писал мне, что его программа находит вектор (строку) длины 36 почти сразу (этот вектор приведён выше), и вот дальше начинается вязкий перебор.
То есть из 51 диагонали 36 находятся легко!

Теперь смотрите: можно начать перебор с этого вектора, то есть задать в программе конкретные значения первых 36 переменных. Дальше продолжать перебор для оставшихся 15 переменных. Если этот перебор не приведёт к успеху, сделать небольшой откат для 4-5 переменных из первых 36, то есть включить перебор и этих переменных.

Это один из путей. Можно придумать ещё мнго разных путей, чтобы как-то обойти огромный перебор.

-- Пн сен 17, 2012 10:25:02 --

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

Похоже что C3N10 не существует.

Диагональных решений C3N10 точно не существует.
О строго диагональных решениях тут сообщали давно, их не нашли (alexBlack, Zealint).
Я не могу сказать точно, имели ли они в виду только строго диагональные решения.
Ну, и я сделала по программе whitefox полный перебор для этого решения, не найдено ни одного решения.

Цитата:

Похоже что C4N16 не существует, хотя нашёл более 1000 строгих.

А вот о решении C4N16, наверное, можно найти точный ответ.
Программа whitefox шутя делает полный перебор для решения C4N17. Таких диагональных решений она не находит.
Тогда и для решения C4N16 полный перебор должен выполниться без проблем.
Дело только в том (как я уже писала), что его программа работает до первого найденного решения, а первое решение C4N16 находится строго диагональное.
Надо просто немного изменить программу. Жду автора, который опять в отъезде.

[Nataly-Mak]

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

Что касается диагональных решений, то G(3,10) у меня тоже не нашлось. Если нигде не ошибся, можно заполнить максимум 13 диагоналей :13: 0 0 1 0 2 2 1 2 1 1 0 0 2

Понятно, что речь идёт о не строго диагональном решении С3N10, вот оно:



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



Может быть, можно и больше 16 диагоналей раскрасить, если искать характеристическую строку с пропусками.

[Nataly-Mak]

Так, кажется, все всё уже решили
Только я одна продолжаю решать.

Ну, вот не даёт покоя книга, и во сне её пишу. Встала вот среди ночи, никак не спится, и начала уж писать наяву
Ох, трудненько
столько черновых записок, закопалась.
Написала одну главу.
Представляю её на суд форумчан. Для начала
http://www.natalimak1.narod.ru/MONO_SQUARES.doc

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

Эх, мало осталось времени до начала следующего конкурса, не успею всю книгу написать.
Зато почти готово классное Приложение - база данных диагональных решений.
Немного осталось выяснить вопросов, а помощники мои - где?

[Herbert Kociemba]

There are no diagonal solutions for C3N10.
I wrote a program that showed, that it is impossible to paint 8 diagonals with one color.
To paint the 19 diagonals you have the choice 7/6/6 or 7/7/5.
In both cases there are no solutions, you have to use color 4 at least for one diagonal, for example


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

or

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

The program is quite fast, because I do not paint the diagonals and check for errors. Instead I found a way to know directly by examining the differences of the first row if the square is error free.

-- 19.09.2012, 23:30 --

There is no strictly diagonal solution for C5N22, but there are many in the general case, for example

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


This example is not derived from a strict C5N25 diagonal solution by deleting rows and columns.

[Nataly-Mak]

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

There are no diagonal solutions for C3N10.

Да, это верно.
Программа whitefox говорит то же самое.

Цитата:

The program is quite fast, because I do not paint the diagonals and check for errors. Instead I found a way to know directly by examining the differences of the first row if the square is error free.

Это интересно! Вы можете применить такой способ проверки характеристической строки для поиска, например, не строго диагонального решения C5N25?

Цитата:

There is no strictly diagonal solution for C5N22, but there are many in the general case, for example

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


This example is not derived from a strict C5N25 diagonal solution by deleting rows and columns.

Да, программа whitefox тоже нашла такое решение C5N22:

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

Ваше решение тоже внесла в БД. Спасибо.

-- Чт сен 20, 2012 06:16:25 --

Вернулся мой помощник whitefox. Ура!

Мы продолжаем работу по составлению БД не строго диагональных решений.
whitefox сделал новую версию программы, теперь она ищет только не строго диагональные решения. Со строго диагональными решениями работа закончена, БД выложена в окончательной версии.

По новой программе быстренько нашла не строго диагональное решение C3N9, это буквально 1 секунда. Решение получилось неизоморфно решению dimkadimon. Оба решения внесла в БД.
Существует всего 60 неизоморфных диагональных решений C3N9, и только 6 из них не строго диагональные. Поэтому и трудно было построить такое решение вручную.

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

Сейчас запустила поиск не строго диагонального решения C5N25. Жду результат.

-- Чт сен 20, 2012 06:40:23 --

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

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

Что касается диагональных решений, то G(3,10) у меня тоже не нашлось. Если нигде не ошибся, можно заполнить максимум 13 диагоналей :13: 0 0 1 0 2 2 1 2 1 1 0 0 2

Понятно, что речь идёт о не строго диагональном решении С3N10, вот оно...

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

Может быть, можно и больше 16 диагоналей раскрасить, если искать характеристическую строку с пропусками.

Пример Herbert Kociemba подтверждает моё предположение. Если искать характеристическую строку с пропуском, можно окрасить максимум 18 диагоналей:



Всего одну диагональ не удаётся раскрасить!

[Nataly-Mak]

Herbert Kociemba
ваше решение C5N22 легко достраивается вручную описанным выше методом до решения C5N23:



Это оригинальное решение тоже внесла в БД.

Не удаётся достроить вручную до решения C5N24 и тем более до решения C5N25.
Продолжаю поиск не строго диагонального решения C5N25; программа работает уже 2 часа; удастся ли выполнить полный перебор

[Pavlovsky]

В продолжение темы. post608484.html#p608484

По http://cs.anu.edu.au/~bdm/data/latin.html можно найти все неизоморфные ЛК 6х6 (22 штуки), относительно операций перестановки строк, колонок, символов.

(Оффтоп)

012345103254234501325410451032540123
012345103254235410324501451023540132
012345104253235014351420420531543102
012345104523230154325401451032543210
012345104523231054325410450132543201
012345104532235104321450453021540213
012345105234234150340512453021521403
012345105234253410324501431052540123
012345120534234150305412451203543021
012345123450254013305124431502540231
012345130524254130345012403251521403
012345134052201534325401450123543210
012345134520245031351204403152520413
012345135024201453324510450132543201
012345143250254031305124430512521403
012345143502231450350124425031504213
012345143520205413321054450231534102
012345150432245013304521423150531204
012345150432245013304521431250523104
012345153024245130324501401253530412
012345153204231450340521425013504132
012345153420231504340152425013504231

Попробовал их все на предмет возможности построения решения C6N36. Получилось, что это возможно только для трех ЛК.

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


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


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


2 3 4 5
3 2 5 4
4 5 2 3
5 4 3 2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2

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


2 3 4 5
3 2 5 4
4 5 2 3
5 4 3 2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2

Разработчики тестов IQ считают, что интеллект это способность распознавать закономерности в хаосе. Чем же эти ЛК отличаются от остальных?

Повторить эксперимент для С=10 трудно. Неизоморфных ЛК 10х10 208904371354363006 штук

[Herbert Kociemba]

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

Instead I found a way to know directly by examining the differences of the first row if the square is error free.

I will explain this for the case N=10.
In the example

0a00b0000c00d000000 (defining string)

we have p[a]=1, p[b]=4, p[c]=9, p[d]=12

If we have the *same* color at these 4 positions we know that we have errors, because

1. p[b]-p[a] = p[d]-p[c] *and*
2. p[b]-p[a]=3 <10 *and*
3. p[c]-p[a]=8<10

If any of these condition fails, we have no errors .

In general, in a square of size N if there are tree or four entries in the defining string with the same color with
p[a]<p[b]<=p[c]<p[d]

There is an error if an only if

1. p[b]-p[a]=p[d]-p[c]
2. p[b]-p[a]<N
3. p[c]-p[a]<N

Observe, that in the case p[b]=p[c] we then have errors with only 3 diagonals

[whitefox]

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

There is an error if an only if

1. p[b]-p[a]=p[d]-p[c]
2. p[b]-p[a]<N
3. p[c]-p[a]<N

Эту же идею я использовал в своей программе.
Только с двумя улучшениями.

Первое, проверка 2. p[b]-p[a]<N лишняя, так как она полностью покрывается проверкой 3. p[c]-p[a]<N.

Второе, сначала проверяются все случаи когда p[b]=p[c], после этого становится лишней проверка случая p[b]-p[a]=p[c]-p[b]=p[d]-p[c].

Также замечу, что в случае p[b]=p[c] лишней становится и проверка 3. p[c]-p[a]<N

[Nataly-Mak]

Задача:
можно ли из не строго диагонального решения NxN C-coloring получить строго диагональное решение (N-1)x(N-1) C-coloring путём удаления строки и столбца?

Обратная задача:
можно ли из строго диагонального решения NxN C-coloring получить не строго диагональное решение (N+1)x(N+1) C-coloring путём добавления строки и столбца?

Желательно привести конкретные примеры.

[dimkadimon]

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

По http://cs.anu.edu.au/~bdm/data/latin.html можно найти все неизоморфные ЛК 6х6 (22 штуки), относительно операций перестановки строк, колонок, символов.

Здорово этот чувак (Brendan McKay) из моего старого университета ANU. Я его имя часто вижу в разных местах. Как жалко что я с ним не встречался.

[Nataly-Mak]

Вторая попытка найти не строго диагональное решение C5N25.
Вчера программу прервала после 7 часов работы.
whitefox сделал новую версию программы, добавил некоторые оптимизации перебора. Теперь программа работает заметно быстрее, но... пока до конца очень далеко.
Запустила программу в 3.40, более 5 часов уже работает.
Базовый вектор (в терминологии Pavlovsky - характеристическая строка) пока имеет вид:

1,1,2,2,3,1,2,3,4,5,...

(дальше не пишу, важно видеть начало вектора)

whitefox говорит, что полный перебор завершится тогда, когда начало базового вектора будет таким:

1,2,3,4,5,...

Ждём

Что-то уже начинаю сомневаться в существовании этого решения. Но ничьи сомнения в расчёт не принимаются. Нужно строгое доказательство.
Может быть, у кого-то есть не переборное доказательство несуществования не строго диагонального решения C5N25?

Программа работает, а я тем временем пишу книгу, уже 4 главы написала. До конца книги у меня точно так же, как у программы до конца перебора

[dimkadimon]

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

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

Я нашёл 200 случайных строго диагональных. По крайней мере можно сказать что не строго 25х25 диагональные встречаются в 200 реже чем строго диагональные. Это конечно не доказательство...

[Nataly-Mak]

Интересный момент: я почему-то сначала думала, что строго диагональные решения построить сложнее (не в смысле техники построения, то бишь - перебора, а в смысле, что у таких решений требования жёстче).
Оказывается наоборот: строго диагональные решения C4N16 существуют в огромном количестве, а не строго диагонального решения C4N16 не существует ни одного! Вот так дела.