ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 10 из 20
  10  все
Пятничная задачка для ума за 1 миллион $
    #39521406
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм... а вот количество расстановок для N=[1..27]

https://oeis.org/A000170
...
Рейтинг: 0 / 0
14.09.2017, 23:02
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521408
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonХм... а вот количество расстановок для N=[1..27]

https://oeis.org/A000170 кошмар, даже цифр таких не знаю 234'907'967'154'122'528
...
Рейтинг: 0 / 0
14.09.2017, 23:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521410
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
mayton,

Пара фактов по ссылке:
- кол-во решений пропорционально n!, т.е. найти все решения - задача неподъемная. Возможно, нужно найти количество решений?
- исходники программы расчета Q27 на FPGA: https://github.com/preusser/q27
...
Рейтинг: 0 / 0
14.09.2017, 23:14
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521411
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
234 квадриллиона вроде.
...
Рейтинг: 0 / 0
14.09.2017, 23:19
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521413
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
scfmayton,

Пара фактов по ссылке:
- кол-во решений пропорционально n!, т.е. найти все решения - задача неподъемная. Возможно, нужно найти количество решений?

В топике решали другую задачу. Притянуть за уши NP алгоритм к более лёгкой форме.

исходники программы расчета Q27 на FPGA: https://github.com/preusser/q27
Что нам это даёт? У нас возможне не хватит кремния и металла на планете чтобы
построить вычислительный кластер для этой задачи.
...
Рейтинг: 0 / 0
14.09.2017, 23:22
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521531
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonВ топике решали другую задачу. Притянуть за уши NP алгоритм к более лёгкой форме.


Вряд ли получится.

Но можно попробовать немного ускорить известные алгоритмы:
1. подсчета количества решений (с неполным учетом симметрий),
2. подсчета всех завершений расстановки на полях малого размера или почти завершенных,
3. нахождения одного завершения на большом поле.
...
Рейтинг: 0 / 0
15.09.2017, 09:19
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521828
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
maytonscfmayton,

Пара фактов по ссылке:
- кол-во решений пропорционально n!, т.е. найти все решения - задача неподъемная. Возможно, нужно найти количество решений?

В топике решали другую задачу. Притянуть за уши NP алгоритм к более лёгкой форме.

исходники программы расчета Q27 на FPGA: https://github.com/preusser/q27
Что нам это даёт? У нас возможне не хватит кремния и металла на планете чтобы
построить вычислительный кластер для этой задачи.
да ща всё будет
...
Рейтинг: 0 / 0
15.09.2017, 13:39
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39521937
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
tip78, к нему очередь будет, в к-рой расстановка фишек будет стоять в хвосте.
...
Рейтинг: 0 / 0
15.09.2017, 15:52
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522042
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вы ещё раз внимательно посмотрите на число решений для вектора из 27 ферзей.
В уме экстраполируте на вектор из 1000. Даже не виде числа. Просто прикиньте порядок.

А потом высказывайте восхищение или неодобрение китайским дата центром.
...
Рейтинг: 0 / 0
15.09.2017, 19:01
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522235
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
mayton, туго с сарказмом у вас, бросайте вы эти задачки ))
эта задачка требует чудес
даже если квантовый комп помножит её на 10, она всё-равно упрётся, потому что другого алгоритма не будет.
...
Рейтинг: 0 / 0
16.09.2017, 18:12
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522270
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ладно. Вижу тут резиденты камеди клаба собрались. Ну ОК.

По инерции продолжаю мемфорсить индексирование и тор.

Открытые вопросы.
- перейти от декартовой системы координат к тору. Посмотреть профиты.
- балансировка доски. Плостность размещения фигур. Координаты - код Грея.
Поискать минимизированную функцию расстановки.
...
Рейтинг: 0 / 0
16.09.2017, 23:00
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522288
ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ex1276
Гость
Так есть смысл заморачиваться нахождением нескольких уникальных решений для доски 1000*1000 ?
...
Рейтинг: 0 / 0
17.09.2017, 01:07
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522296
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ex1276,

известен алгоритм поиска случайного решения.

С вероятностью почти 1 его первая сотня решений для большой доски - уникальные.
...
Рейтинг: 0 / 0
17.09.2017, 08:19
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522298
Ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ex1276
Гость
Aleksandr Sharahovex1276,

известен алгоритм поиска случайного решения.

С вероятностью почти 1 его первая сотня решений для большой доски - уникальные.

Можно ли где-то ознакомиться с этим алгоритмом или его принципами?
Способен ли он достраивать позиции с несколькими выставленными ферзями?
...
Рейтинг: 0 / 0
17.09.2017, 09:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522310
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Ex1276Aleksandr Sharahovex1276,

известен алгоритм поиска случайного решения.

С вероятностью почти 1 его первая сотня решений для большой доски - уникальные.

Можно ли где-то ознакомиться с этим алгоритмом или его принципами?
Способен ли он достраивать позиции с несколькими выставленными ферзями?

Я уже давал тут эту ссылку http://www.fizyka.umk.pl/~milosz/AlgIILab/10.1.1.57.4685.pdf
В википедии тоже есть ссылка статью этих авторов.

В принципе работает. Как будет время причешу и выложу.
...
Рейтинг: 0 / 0
17.09.2017, 10:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522319
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В гитхабе нашел одну из реализаций. С рандомными начальными установками. И с последовательной
минимизацией конфликтов.

Для 40х40 находит 1 рандомное решение за 25 секунд. Не могу подтвердить что это реализация
предложенная университетом Юта. Но очень похоже.
 
Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q
...
Рейтинг: 0 / 0
17.09.2017, 11:19
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522320
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonВ гитхабе нашел одну из реализаций. С рандомными начальными установками. И с последовательной
минимизацией конфликтов.
Для 40х40 находит 1 рандомное решение за 25 секунд. Не могу подтвердить что это реализация
предложенная университетом Юта. Но очень похоже.


У меня менее 40 сек на одно решение на поле 10^5x10^5.
...
Рейтинг: 0 / 0
17.09.2017, 11:26
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522321
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давай причёсывай... Чесун.. :) Ждем.
...
Рейтинг: 0 / 0
17.09.2017, 11:28
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522357
Михаил Фото
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Михаил Фото
Участник
Занятно
...
Рейтинг: 0 / 0
17.09.2017, 15:13
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522362
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Как завершить расстановку ферзей (N queens completion problem)


Выложил здесь http://guildalfa.ru/alsha/node/35
...
Рейтинг: 0 / 0
17.09.2017, 15:24
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522371
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, какая польза от одних сорцов?
Выложи бинарь. Не все-ж имеют твой компиллер.

Заодно люди протестят твой результат. Вдруг ты обманул
...
Рейтинг: 0 / 0
17.09.2017, 15:54
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522376
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton, придется поверить на слово )

У моего бинаря форма как приборная панель самолета - там дофига места занимает экспериментальная часть для всех задач с ферзями, причем что-то писалось еще при царе горохе.

Ломать не хочу, да и непонятно зачем. К тому же бинарь на сайте - дурной тон.
...
Рейтинг: 0 / 0
17.09.2017, 16:07
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522392
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Треш конечно. Делфи-Паскаль я имею в виду. Кроме того... эти длинные названия...
Ну я понимаю зачем они нужны в бизнес-приложениях. Ордер. Опцион. Цена. Комиссия. Но в алгоритмических
я-бы вводил { i,j,k } как параметры циклов. Это естесственно для математики и алгоритмов. Счетчики там...
флаги.
...
Рейтинг: 0 / 0
17.09.2017, 16:30
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522396
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonТреш конечно. Делфи-Паскаль я имею в виду. Кроме того... эти длинные названия...
Ну я понимаю зачем они нужны в бизнес-приложениях. Ордер. Опцион. Цена. Комиссия. Но в алгоритмических
я-бы вводил { i,j,k } как параметры циклов. Это естесственно для математики и алгоритмов. Счетчики там...
флаги.

Ну так флаг в руки )
Получится короче и непонятнее.
...
Рейтинг: 0 / 0
17.09.2017, 16:37
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39522400
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У Кнута и Седжвика - еще непонятнее и вообще, математика - непонятный язык.
Короткие обозначения...
...
Рейтинг: 0 / 0
17.09.2017, 16:51
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 10 из 20
  10  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]