Ученые из Сент-Эндрюсского университета в Шотландии бросили вызов лучшим программистам мира: найти решение старинной шахматной задачи о восьми ферзях и заработать миллион долларов.
Суть заключается в следующем: на стандартной шахматной доске в 64 клетки (8х8) необходимо расставить восемь ферзей таким образом, чтобы ни один из них не атаковал другого.
Эта фактически математическая задача впервые была опубликована в 1850 году. Уже подсчитано, что на стандартном поле существует 4.426.165.368 различных комбинаций расположения фигур, но только 92 ведут к правильному решению.
Когда задачу предложили компьютеру, он без труда справился с ней. Но тогда ученые решили усложнить задачу, увеличив поле до 1000х1000 клеток и, соответственно, и число фигур на доске. И тут компьютер оказался бессилен – просто завис.
В статье, опубликованной в журнале Сент-Эндрюсского университета по проблемам искусственного интеллекта, отмечается: "Решение обеспечит большой вклад в мир науки. Создание подобного алгоритма позволит решить не только шахматную задачу, но и ответить на ряд других вопросов, которые оказывают влияние на всю нашу жизнь, причем каждый день. Стоит ли это миллиона долларов? Конечно, стоит. И приз будет вручен с благодарностью от всего человечества".
Кстати, подобный мировой "математический вызов" уже состоялся. В 2000 году математический институте Клэя в Массачусетсе объявил награду в 7 млн долларов за решение "задачи тысячелетия", над решением которой ученые умы бились более 100 лет.
Победителем стал российский математик Григорий Перельман, сумевший доказать гипотезу Пуанкаре.
Теперь же все, кто хочет своим умом заработать миллион долларов, могут попробовать сделать это. Все, что для этого требуется, - помочь ученым разработать программный алгоритм, который смог бы решить задачу. Или же доказать, что решения не существует.
Задача 8 ферзей, которая сегодня существует и как online флеш-игра, была придумана шахматистом Максом Базелем в 1848 году и обнародована двумя годами позже. Всего оригинальных решений найдено 12. Общее количество возможных (с учетом применения операции симметрии) вариантов – 92.
Первым опубликовал ответ на эту задачу в 1850 году Франц Нак. С тех пор многие ученые решали и исследовали эту задачу, предлагая собственные варианты решения.
Так, известный немецкий математик, механик и физик Карл Гаусс очень любил эту головоломку и находил 72 варианта возможной расстановки. Он творчески подошел к процессу поиска ответа – разные комбинации 8 ферзей достигались с помощью интересного приёма… поворота доски на 90, 180 и 270 градусов соответственно.
Задача достаточно сложная, но как минимум один вариант как правильно расставить ферзей находится довольно быстро и называется явным. Самое популярное правильное расположение достигается следующей расстановкой ферзей: a2, b4, c6, d8, e3, f1, g7, h5.
В более "математическом" виде задача может быть сформулирована несколькими способами, например, так: "Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы".
Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:
• Построить одно, любое решение задачи.
• Аналитически доказать, что решение существует.
• Определить количество решений.
• Построить все возможные решения.
• Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путем прямого перебора всех возможных вариантов расстановки. Но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объем перебора.
Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали.
Даже такое простое правило способно существенно уменьшить число возможных расположений: 16.777.216 (то есть 88) вместо 4.426.165.368.
Один из типовых алгоритмов решения задачи - использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий пытаются поставить на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад - переставляется ранее установленный ферзь.