Интересное и Юмор - страница 3969

[Konstantin Erin]

лет 10 назад знакомая студентка попросила решить задачу о 8 ферзях на с++ с рекурсивной функцией. Бился 4 часа, испробовал сотню вариантов. Глухо. Она должна скоро придти... И тогда обратился с мольбой к Николаю Угоднику. Произошло чудо - на экране поверх Нортона Коммандера (значит, это было лет 20 назад) появились 2 скобки во весь экран. Взгляд прилип к центру экрана. И уже после вычислил, что внизу было многоточие - в функцию надо было передать параметр... через 15 минут программа была готова

[Vladimir Suschenko]

Дмитрий:

1. Не тупи - "Если решать более общую задачу об N ферзях...." 

2. Для начала хотя бы прочитай условия победы в конкурсе на 1 000 000 долларов. Это трудно, но ты все таки попробуй. Даю подсказку - нужен общий алгоритм решения задачи для любой размерности доски

Уточнение к подсказке - нужен не просто общий алгоритм (таких есть, вероятно даже, не один), а именно алгоритм, позволяющий современным компьютерам решать задачу с большой размерностью доски в реальном времени. Для решения задачи с большим количеством полей имеющимися алгоритмами современным компьютерам слишком до фига лет (и памяти) может понадобиться...

[Alexandr Bryzgalov]

миллион-то получили?

[Дмитрий]

Alexandr Bryzgalov:
миллион-то получили?

Не, сдачи с 2 млн. не было

[Andrey Kisselyov]

Vladimir Suschenko:

Уточнение к подсказке - нужен не просто общий алгоритм (таких есть, вероятно даже, не один), а именно алгоритм, позволяющий современным компьютерам решать задачу с большой размерностью доски в реальном времени. Для решения задачи с большим количеством полей имеющимися алгоритмами современным компьютерам слишком до фига лет (и памяти) может понадобиться...

задача уже решена и не нужно слишком много лет и тем более памяти для ее решения, при любой размерности шахматной доски>=4.

с уважением.

[Дмитрий]

Andrey Kisselyov:
задача уже решена и не нужно слишком много лет и тем более памяти для ее решения, при любой размерности шахматной доски>=4.

с уважением.

Так иди получай млн. Только пакет возьми

[Andrey Kisselyov]

Дмитрий:

Так иди получай млн. Только пакет возьми

если им так надо решение, сами принесут.

с уважением.

[Dr. Trader]

Vladimir Suschenko:

Уточнение к подсказке - нужен не просто общий алгоритм (таких есть, вероятно даже, не один), а именно алгоритм, позволяющий современным компьютерам решать задачу с большой размерностью доски в реальном времени. Для решения задачи с большим количеством полей имеющимися алгоритмами современным компьютерам слишком до фига лет (и памяти) может понадобиться...

Сейчас модно такие задачи решать SAT/SMT солверами. Для максимальной скорости решения нужно задачу выразить булевыми функциями в cnf форме, и дальше как-то по примеру этой статьи http://www.cs.cmu.edu/~hjain/papers/sudoku-as-SAT.pdf

Вот только sat солвер просто даст ответ можно ли решить задачу, в виде да/нет. Понятия не имею как оттуда сам ответ (расположение фигур) вытащить, я эту технологию не умею.

[Roman Shiredchenko]

гришу гляньте...щас..

[Roman Shiredchenko]

На  те

https://www.youtube.com/watch?v=VpOqb-0Ec4w