$1 млн за разгадку шахматной головоломки

Университет Сент-Эндрюс в Великобритании предложил вознаграждение в размере $1 млн тому, кто сможет разгадать старинную шахматную загадку.

Речь о «задаче о восьми ферзях», опубликованной шахматистом Максом Базелем в 1850 году: расставить на стандартной шахматной доске в 64 клетки 8 ферзей таким образом, чтобы ни один из них не атаковал другого. Количество вариантов решения – около 4.5 млрд.

Тем не менее, человек способен эмпирически решить эту задачу – когда-то ее успешно решил немецкий математик Карл Гаусс, известный, в частности, функцией нормального распределения Гаусса. При усложнении условий - увеличении размера поля и количества фигур, с головоломкой справляется компьютер. Однако когда размер доски увеличивается до 1000 на 1000 клеток, программа зависает.

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

Если алгоритм будет создан, появится возможность решения многих важных проблем экономики, представляемых в виде задач из топологии с помощью методов комбинаторики, связанных с перебором огромного числа сочетаний, к примеру – задачи «китайского почтальона».

Во всех из них требуется создать комбинаторную конфигурацию - произвести размещение из множества n элементов по k. Это – перестановки, сочетания, композиции или, к примеру, разбиение (представление) числа n в виде неупорядоченной суммы целых положительных чисел.

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