2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 106, 107, 108, 109, 110, 111, 112 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение17.09.2012, 06:27 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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


22/03/08

7154
Саратов
Вчера уже начала писать программу более конкретную для поиска не строго диагонального решения 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 находится строго диагональное.
Надо просто немного изменить программу. Жду автора, который опять в отъезде.

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


22/03/08

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

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

Изображение

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

Изображение

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

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


22/03/08

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

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

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

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

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


25/08/12
171
Germany
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.

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


22/03/08

7154
Саратов
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. Ура! :D

Мы продолжаем работу по составлению БД не строго диагональных решений.
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 диагоналей:

Изображение

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

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


22/03/08

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

Изображение

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

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

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


21/02/10
1594
Екатеринбург
В продолжение темы. 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 штук

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


25/08/12
171
Germany
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

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


19/12/10
1546
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

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


22/03/08

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

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

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

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


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

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

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


22/03/08

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

Код:
1,1,2,2,3,1,2,3,4,5,...

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

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

Код:
1,2,3,4,5,...

Ждём :roll:

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

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

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


01/06/12
1013
Adelaide, Australia
Nataly-Mak в сообщении #621729 писал(а):
Может быть, у кого-то есть не переборное доказательство несуществования не строго диагонального решения C5N25?

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

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


22/03/08

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 106, 107, 108, 109, 110, 111, 112 ... 130  След.

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



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

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


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

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