Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 [16] 17 18 19 20   вперед  Ctrl
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
Уточнение:
3. ... с учетом *полной* симметрии (вращение и зеркало).
Если только зеркало, то уникальность не нужно проверять.
27 сен 17, 19:59    [20827657]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
ex1276,

Какая польза в выделении ладейных матриц? Они уже учтены в общем ферзевом алгоритме. И нам от них нет пользы.
27 сен 17, 20:08    [20827679]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Member

Откуда:
Сообщений: 4
mayton
Какая польза в выделении ладейных матриц? Они уже учтены в общем ферзевом алгоритме. И нам от них нет пользы.


По ощущению, каким бы способом мы не проверяли доску на свободные вертикали-горизонтали, быстрее чем через комбинаторную перестановку вектора N (описывающего как раз ладейные матрицы) - проверку сделать не получится.

Но рассудит нас только алгоритм. Буду рад ошибиться
27 сен 17, 21:47    [20827769]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
Да это верно. Мы будем комбинировать ладей. Но если ладья №254 вдруг стала на диагональ с ладьей №255
то мы можем прервать итерацию. Нам нет смысла достраивать оставшихся 745 ладей для финала итерации.
Тоесть расстановка ладей прервана.
27 сен 17, 22:07    [20827793]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
exp98
mayton
Как хранить найденные матрицы? Если база - то оптимально положить вектор ферзей в строку
Да может банально в 4 столба? id, num, row, col ? для начала. К полю по его номеру доступаться не комильфо. Тем более рекуррентно доступаться.
Вопрос другой, как долго хранитель будет хранить?

Я думаю что хранить удобно денормализованно. В виде вектора номеров горизонталей. По верикали - просто
последовательность поэтому ее можно поскипать.

Например для доски 10х10:

IDQueenVector
02,4,6,8,10,1,3,5,7,9


И я бы добавил лидирующие нули для того чтобы сделать запись позиционной. Тогда и разделители можно убрать.

IDQueenVector
002040608100103050709


Для доски 10х10 будет соотв. два знакоместа под номер горизонтали. А для доски 1000х1000
надо будет три знака 000..999

Почему мне захотелось убрать запятые и сделать позиционность? Ну... КМК для решения задачи
"остаточных ферзей" нам нужно будет искать по шаблону все расстановки в которых
требуемые места забиты шаблоном а все остальные - метасимволом % или _ (в терминологии SQL).

Пример:
create table queen10x10(
 id number primary key,
 queenvector varchar(20) not null,
 constraint queen_unq unique (queenvector)
);
....

select * from queen10x10 where queenvector like '02__06__10__03050709';


По поводу зеркал... ну... ХЗ. Цена вопроса - размер. Если не жалко - то хранить. Если жалко - то
преобазовывать при поиске в набор шаблонов.
27 сен 17, 23:50    [20827901]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
Для чего нужны расстановки в базе данных?
28 сен 17, 00:28    [20827940]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
Пока не знаю. А для чего нужен этот топик?
Вы знаете... в математике самый запрещенный вопрос - "для чего".

Ни для чего. Просто - поток мозгового сознания контролирует топик.
28 сен 17, 08:22    [20828099]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Member

Откуда:
Сообщений: 4
Коллеги, призываю к вашему опыту.

Понимаю, что не хватает мастерства в программировании.
Не могу найти/сделать быстрый алгоритм генерации N-перестановок. Все варианты не нравятся.

Пишу на дельфи, на входе N и вектор текущего решения S[1..N]
Алгоритм, естественно, нерекурсивный.

Пример: S = 12345, N=5
Генерируем: 12354, 12534, 12543 и тд. все N!-1 перестановок.

Хочется изящное простое решение, может кто его знает?
28 сен 17, 11:32    [20828631]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
tip78
Member

Откуда: Москва
Сообщений: 444
ex1276
Хочется изящное простое решение, может кто его знает?

гугл знает 100-пудово
28 сен 17, 11:36    [20828644]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
tip78
Member

Откуда: Москва
Сообщений: 444
https://www.google.ru/search?q=N!-1 перестановки алгоритм
28 сен 17, 11:37    [20828646]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
ex1276
Коллеги, призываю к вашему опыту.

Понимаю, что не хватает мастерства в программировании.
Не могу найти/сделать быстрый алгоритм генерации N-перестановок. Все варианты не нравятся.

Пишу на дельфи, на входе N и вектор текущего решения S[1..N]
Алгоритм, естественно, нерекурсивный.

Пример: S = 12345, N=5
Генерируем: 12354, 12534, 12543 и тд. все N!-1 перестановок.

Хочется изящное простое решение, может кто его знает?


Найдешь быстрее, компенсирую разницу )) http://guildalfa.ru/alsha/node/26
28 сен 17, 11:44    [20828679]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
tip78
Member

Откуда: Москва
Сообщений: 444
как правильно смотреть на задачу про ферзей

представьте пароль, который надо узнать:
j9320i09kimvmwl,dpo23kf98ij(FJ(HUGH4ujg3jfifjiokk4ghbcnhbeuhb34y8hUFHuhUh843hf83uhfuHFUHuigh34hik1kjwnefjknvr
его можно узнать только методом перебора, иначе запутаешься в проверенных значениях
но очень хочется узнать его Сразу и Весь
за "целый" миллион
(а пароль открывает двери для всего на свете...)

зы: нигде в природе не видел подобных решений в принципе
зыы: и зеркалирование им тут не подойдёт )
28 сен 17, 13:15    [20828900]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
Чорт ! Одни делфисты
28 сен 17, 13:18    [20828906]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
tip78
как правильно смотреть на задачу про ферзей
представьте пароль, который надо узнать ... его можно узнать только методом перебора ...но очень хочется узнать его Сразу и Весь
Так и хочется ответить, что гладко было на бумаге, да забыли про овраги.
Тем не менее, наука умеет много гитик. Наводка на реальность. Сделали Вин-95. Там тоже надо было вводить пароль однако ...

quot ex1276] навскидку: 12345... - единичная матрица, оно же самое маленькое число. Тупо суммируем с единичкой, с переносом, по модулю N.
Сорри, если чево не так.
28 сен 17, 13:46    [20828978]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
tip78
представьте пароль, который надо узнать:
Ещё одна гитика из жизни. На уроке программирования чел. доказывает, чтобы упорядочить числа, надо сравнить каждое с каждым. Иначе как ты узнаешь кто из них больше? Преп намекнул, что сравнение транзитивно ...

Могу согласиться только, что зеркалирования недостаточно.
28 сен 17, 13:58    [20829006]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
ex1276, выше мой вариант не проходит, последовательность меняет монотонность ... хватит с меня.
28 сен 17, 14:30    [20829070]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
Из ссылки, данной на ИБМу, вытащил расстановки для N=9 (и кажется одну забыл) написано: решений = 46 / 352.
136824975 = (1)(23648795)
+
137285946 = (1)(23796584)
138692574 = (1)(23875946)
146392857 =
146825397 =
147925863 =
148397526 =
157938246 =
157942863 =
159642837 =
168374295 =
174835926 = (1)(27965348)
174839625 =
241796358 = (12473)(598)(6)
247139685 = (124)(37695)(8)
248396157 =
249731685 =
249753168 =
257936418 =
257948136 =
258136974 =
258196374 =
258693147 =
258693174 =
259418637 = (125)(39768)(4)
261379485 = (8)(12695743)
261753948 =
261958473 =
263184975 =
269358417 =
275194683 =
279631485 =
281479635 =
285396417 =
286931475 = (128749536)
358296174 = (1387)(2594)(6)
358297146 = (138425967)
359247186 = (13967)(254)(8)
362951847 = (1326)(/4978)(5)
368159247 = (1384)(2697)(5)
368519724 =
369741825 =
372859164 =
386192574 = (136287594)
427918536 = (2)(14968375)

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

Раскладываем правильную перестановку матрицы в суперпозицию циклов.
9 = разложение в сумму чисел (что-то мог пропустить)
+
9 +0
1+8
2+7
2*х +у
3+6
3+5+1
4+5
3+3+3
3+3+ * +*
4+4+1
Вещь такая. Наличие 2 - брутальное транспонирование 2-х элементов - неправильная м-ца
Наличие от двух 3 - скорее всего не пройдёт из-за диагоналей
3+6 - кажется просто теоретически невозможным
Наличие от двух 1 - фишки на главной диагонали.

Остаются классы
9
1+8
3+5+1
4+4+1

1) Не они ли дают тот самый блочный метод?

2) В классе у разложений одинаковый порядок р в силу цикличности разложений
class  p  count(p)
9  ?  ?
1+8   ?  ?                 -- их меньше чем для 9 ?
3+5+1  3*5=15   ?  
4+4+1   4*4=16  ? 
3) Наличие от двух 3 (от 3-х 4 и т.п.) - на больших размерах наверняка существуют.

Есть мнения?
28 сен 17, 19:23    [20830052]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
Вот и базячка пригодится. Чтоб ваши гипотезы обкатать. И не на жлобском поле 9х9.
28 сен 17, 19:53    [20830089]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
mayton
Вот и базячка пригодится. Чтоб ваши гипотезы обкатать. И не на жлобском поле 9х9.


Простые гипотезы можно проверять, задавая начальное положение для большого N>=50000.
Практически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.
28 сен 17, 20:31    [20830154]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35512
Увы мне увы... Душа требует водки а мозк новых задач с ферзями и конями.
28 сен 17, 21:54    [20830239]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
mayton
жлобском поле 9х9.
Замечу, что данный топик порождён как раз на основе жлобских размеров. Как и многое другое в теории чисел.

Вчерашний труд завершил (за что наверняка получу пендаля от начальства), пока каждую приходится копи/вставкой в силу несовершенства запроса.
Замечен французский перевёртыш
174839625 = (1)(27 69 5348)
174835926 = (1)(27 96 5348)

N=9, 46/352
357142869 = (13786254)(9) ...
+
136824975 = (1)(23648795)
137285946 = (1)(23796584)
138692574 = (1)(23875946)
146392857 = (1)(2436)(5978)
146825397 = (1)(24897365)
147925863 = (1)(24937865)
148397526 = (1)(2438)(5967)
157938246 = (1)(2537)(4968)
157942863 = (1)(25493786)
159642837 = (1)(2546)(3978)
168374295 = (1)(26438957)
174835926 = (1)(27965348)
174839625 = (1)(27695348)
241796358 = (12473)(598)(6)
247139685 = (124)(37695)(8)
248396157 = (12438597)(6)
249731685 = (12476)(395)(8)
249753168 = (1247)(3986)(5)
257936418 = (12537498)(6)
257948136 = (125496837)
258136974 = (12538794)(6)
258196374 = (12594)(387)(6)
258693147 = (12597)(3846)
258693174 = (125946387)
259418637 = (125)(39768)(4)
261379485 = (12695743)(8)
261753948 = (1263)(4798)(1)
261958473 = (12687493)(5)
263184975 = (1264)(5879)(3)
269358417 = (1268)(3974)(5)
275194683 = (12764)(359)(8)
279631485 = (395)(12746)(8)
281479635 = (1283)(5769)(4)
285396417 = (128)(35974)(6)
286931475 = (128749536)
358296174 = (1387)(2594)(6)
358297146 = (138425967)
359247186 = (13967)(254)(8)
362951847 = (1326)(4978)(5)
368159247 = (1384)(2697)(5)
368519724 = (13826945)(7)
369741825 = (139547826)
372859164 = (1327)(4869)(5)
386192574 = (136287594)
427918536 = (2)(14968375)
Просто интересно, кто не понимает, что за выражениями (1327)(4869)(5) стоит произведение матриц, причём "неправильных" в целом и оно коммутативно?
29 сен 17, 10:36    [20831019]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Member

Откуда:
Сообщений: 4
Aleksandr Sharahov
Практически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.


Вы попробуйте предустанавливаемых ферзей ставить ближе к центру. Например в центральном квадранте.
Интересно сможет ли алгоритм найти решения хотя бы при 100 центральных ферзях на поле 50 000.
29 сен 17, 12:28    [20831400]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
ex1276
Member

Откуда:
Сообщений: 4
Может нам устроить тогда гонку размерности решений.
Надо придумать способ представить решение в кратком, наглядном и удобоваримом для интернета виде.
Может так:

N-размерность, дата, автор решения, алгоритм, время поиска в чч:мм:cc
X1,X2,X3,X4...XN

Хотя решение на 50 000 займет 250 Кб, а на 1 млн = 6 Мб.
29 сен 17, 12:38    [20831435]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
ex1276
Aleksandr Sharahov
Практически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.


Вы попробуйте предустанавливаемых ферзей ставить ближе к центру. Например в центральном квадранте.
Интересно сможет ли алгоритм найти решения хотя бы при 100 центральных ферзях на поле 50 000.


Попробовал на поле 50000х50000 в центральный квадрат 25000х25000 случайно ставить 12500 ферзей.
Завершение нашлось во всех 10 проведенных тестах.
29 сен 17, 13:32    [20831612]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1103
Ошибки точно нет? другие подтверждают подобное?
29 сен 17, 13:49    [20831688]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 [16] 17 18 19 20   вперед  Ctrl
Все форумы / Программирование Ответить