Статья адресована читателям, которые имеют опыт решения задач перечислительной комбинаторики, а также тем, кому нравятся трудные задачи по программированию.
Речь пойдёт о сражении, которое длится уже более 150 лет. Математики давно начали войну с шахматными фигурами, и, пожалуй, наиболее упорной фигурой в этой битве является ферзь. Последние 50 лет на помощь математикам приходят компьютеры, однако и этого оказывается недостаточно.
Существует большое количество задач, связанных с этой самой сильной фигурой. Например, задача о доминировании ферзей: какое наименьшее число ферзей требуется, чтобы они держали под контролем все поля доски? В общем случае речь идет не о доске 8 x 8 (для которой ответ 5), а о доске размером n x n. Дальнейшее обобщение может быть связано с переходом к трехмерному пространству, где ферзи ставятся на кубическую доску (и бьют в любом из 26 направлений). Но мы рассматриваем класс задач связанных с перечислением возможных расстановок ферзей.
Задача о расстановке ферзей на шахматной доске, пожалуй, является одной из наиболее известных труднорешаемых задач. В одном из возможных вариантов она звучит следующим образом: сколькими способами можно расположить n ферзей на шахматной доске размером n x n так, чтобы они не били друг друга? Эту задачу предлагают и в школе на уроках информатики (для n=8) и при приёме на работу; однако для достаточно больших значений параметра n это «упражнение» является уже серьезной проблемой мирового масштаба.
Изначально задача была сформулирована как обычная головоломка: требуется расположить 8 ферзей на стандартной доске 8 x 8 так, чтобы они не били друг друга и представить все такие расстановки (их, кстати, всего 92). Ею занимались многие известные математики, включая Гаусса. Обобщение задачи на произвольный размер доски было предложено ещё в далёком 1850 году, а активные поиски алгоритмов для её решения начались с 1960-х, то есть с бурным развитием вычислительной техники. На примере этой задачи демонстрировалась работа таких классических алгоритмических подходов как поиск с возвратом, метод «разделяй и властвуй», constraint programming и др. И правда удивительно: формулировка настолько проста, что понятна и первокласснику, но попытка отыскать решение порождает огромное множество новых идей и методов.
Собственно, а зачем нужна такая задача? Какой смысл в том, чтобы гонять несчастных ферзей по доске, да ещё и соревноваться в том, кто быстрее это сделает для как можно больших значений n? На самом деле в науке существует целый класс так называемых «общих проблем», не все из которых имеют прямые приложения, однако за их решение либо платят много денег, либо попытка продвинуться хоть на один шаг невозможна без развития целой научной теории или дополнения к уже известному разделу науки. Так, решая задачу для n=26, учёные разработали ряд специальных методов в теории групп, на которых затем защитили диссертации несколько человек. Само решение так называемой Q(26) посчитали на видеокартах 11 июля 2009 г. Подробнее об этом говорится на странице авторов (англ).
Последовательность Q(n) зарегистрирована в энциклопедии целочисленных последовательностей под номером A000170 (англ).
Попытки решить задачу дальше упираются в вычислительную мощность имеющихся машин. В принципе, на компьютере типа Roadrunner (с производительностью свыше одного петафлопса) можно продвинуться дальше, но рано или поздно найдётся такое значение n, с которым никакой суперкомпьютер не справится, а вывести явную формулу никто пока не смог. Рассматривается сильная гипотеза о том, что существует константа C, такая, что число расстановок есть величина порядка n!/Cn. Считается, что эта константа примерно равна 2.54, но теперь, когда ответ для n=26 известен, константу уточнили, и она считается равной 2.48. В любом случае, значительного прорыва в этом направлении пока ожидать не приходится.
По указанной причине интерес представляет попытка решить более простую задачу: расставить k ферзей на доске n x n, где k – фиксированное число, не зависящее от n. Например, когда k=1, то число расстановок, очевидно, равно n2. Для k=2 ответ равен n(n-1)(n-2)(3n-1)/6. Примерно полтора месяца назад мне удалось вывести явную формулу для k=5 (для k=3 и k=4 формулы уже были известны), однако, пока я эту формулу упрощал (хотелось красиво сделать), один товарищ из Чехии тоже её вывел и опубликовал в неупрощённом виде. Ответным шагом теперь может быть только явная формула для k=6. Именно эту формулу мы пытаемся вывести в рамках конкурса на одном из моих сайтов. Его подробное описание и текущие результаты здесь. В данный момент конкурс скорее похож на соревнование: кто найдёт ответ для как можно большего значения n. Отличный способ проверить свои силы, так как практика показывает, что до n=15 почти никто не добирается. К сожалению, конечно. [ Дополнение 10.05.2010. В настоящий момент конкурс завершён, формула получена ].
Доказано, что когда количество ферзей фиксировано, а доска имеет переменный размер, то знаменатель производящей функции имеет (возможно, комплексные) корни, равные по модулю единице. Это обстоятельство позволяет нам угадать производящую функцию, зная ответы для некоторых подряд идущих n=1,2,3… Например, для задачи о пяти ферзях, мне потребовалось посчитать ответы до n=38 (степень знаменателя равна 37). Для шести ферзей, видимо, степень будет чуть меньше 80 (следует из моих эмпирических соображений).
Существуют и другие варианты задачи, например, когда доска не квадратная, а прямоугольная или в форме тора (то есть выход ферзя за границу доски равносилен появлению его с противоположной стороны). Также интересными являются варианты, когда каждый ферзь бьёт ровно одного другого ферзя. Знакомые физики утверждают, что такие задачи имеют реальные физические приложения, однако мне они неизвестны.
Многие люди, работающие в промышленности (или в другой области, менее связанной с фундаментальными исследованиями) продолжают считать такого рода упражнения бесполезной тратой времени. Более полезно – считают они – сделать красивый и понятный интерфейс, а будет ли это работать эффективно – вопрос второстепенный. В данном случае это не совсем правильно. Решение подобных задач позволяет научным сообществам показывать друг другу свои навыки, уровень своей научной школы, а также демонстрировать прочие показатели успешности. А смысл этого в том, что когда возникает действительно полезная для общества задача похожего типа, то её, как правило, дают решать наиболее продвинутому в этой области коллективу учёных. С другой стороны, даже если та или иная задача сама по себе практической ценности не имеет, её решение позволяет развить новые методы в математике и программировании.
Чтобы понять, насколько многолика и важна эта задача, достаточно зайти в упомянутую мной выше энциклопедию целочисленных последовательностей и набрать в поиске слово «Queen». Вам предложат более 250 задач, где встречается ферзь. Причём некоторые из этих задач удивительным образом перекликаются с научными (и не совсем) проблемами, которые никакого отношения к шахматам не имеют.
Список источников
Речь пойдёт о сражении, которое длится уже более 150 лет. Математики давно начали войну с шахматными фигурами, и, пожалуй, наиболее упорной фигурой в этой битве является ферзь. Последние 50 лет на помощь математикам приходят компьютеры, однако и этого оказывается недостаточно.
Существует большое количество задач, связанных с этой самой сильной фигурой. Например, задача о доминировании ферзей: какое наименьшее число ферзей требуется, чтобы они держали под контролем все поля доски? В общем случае речь идет не о доске 8 x 8 (для которой ответ 5), а о доске размером n x n. Дальнейшее обобщение может быть связано с переходом к трехмерному пространству, где ферзи ставятся на кубическую доску (и бьют в любом из 26 направлений). Но мы рассматриваем класс задач связанных с перечислением возможных расстановок ферзей.
Задача о расстановке ферзей на шахматной доске, пожалуй, является одной из наиболее известных труднорешаемых задач. В одном из возможных вариантов она звучит следующим образом: сколькими способами можно расположить n ферзей на шахматной доске размером n x n так, чтобы они не били друг друга? Эту задачу предлагают и в школе на уроках информатики (для n=8) и при приёме на работу; однако для достаточно больших значений параметра n это «упражнение» является уже серьезной проблемой мирового масштаба.
Изначально задача была сформулирована как обычная головоломка: требуется расположить 8 ферзей на стандартной доске 8 x 8 так, чтобы они не били друг друга и представить все такие расстановки (их, кстати, всего 92). Ею занимались многие известные математики, включая Гаусса. Обобщение задачи на произвольный размер доски было предложено ещё в далёком 1850 году, а активные поиски алгоритмов для её решения начались с 1960-х, то есть с бурным развитием вычислительной техники. На примере этой задачи демонстрировалась работа таких классических алгоритмических подходов как поиск с возвратом, метод «разделяй и властвуй», constraint programming и др. И правда удивительно: формулировка настолько проста, что понятна и первокласснику, но попытка отыскать решение порождает огромное множество новых идей и методов.
Собственно, а зачем нужна такая задача? Какой смысл в том, чтобы гонять несчастных ферзей по доске, да ещё и соревноваться в том, кто быстрее это сделает для как можно больших значений n? На самом деле в науке существует целый класс так называемых «общих проблем», не все из которых имеют прямые приложения, однако за их решение либо платят много денег, либо попытка продвинуться хоть на один шаг невозможна без развития целой научной теории или дополнения к уже известному разделу науки. Так, решая задачу для n=26, учёные разработали ряд специальных методов в теории групп, на которых затем защитили диссертации несколько человек. Само решение так называемой Q(26) посчитали на видеокартах 11 июля 2009 г. Подробнее об этом говорится на странице авторов (англ).
Последовательность Q(n) зарегистрирована в энциклопедии целочисленных последовательностей под номером A000170 (англ).
Попытки решить задачу дальше упираются в вычислительную мощность имеющихся машин. В принципе, на компьютере типа Roadrunner (с производительностью свыше одного петафлопса) можно продвинуться дальше, но рано или поздно найдётся такое значение n, с которым никакой суперкомпьютер не справится, а вывести явную формулу никто пока не смог. Рассматривается сильная гипотеза о том, что существует константа C, такая, что число расстановок есть величина порядка n!/Cn. Считается, что эта константа примерно равна 2.54, но теперь, когда ответ для n=26 известен, константу уточнили, и она считается равной 2.48. В любом случае, значительного прорыва в этом направлении пока ожидать не приходится.
По указанной причине интерес представляет попытка решить более простую задачу: расставить k ферзей на доске n x n, где k – фиксированное число, не зависящее от n. Например, когда k=1, то число расстановок, очевидно, равно n2. Для k=2 ответ равен n(n-1)(n-2)(3n-1)/6. Примерно полтора месяца назад мне удалось вывести явную формулу для k=5 (для k=3 и k=4 формулы уже были известны), однако, пока я эту формулу упрощал (хотелось красиво сделать), один товарищ из Чехии тоже её вывел и опубликовал в неупрощённом виде. Ответным шагом теперь может быть только явная формула для k=6. Именно эту формулу мы пытаемся вывести в рамках конкурса на одном из моих сайтов. Его подробное описание и текущие результаты здесь. В данный момент конкурс скорее похож на соревнование: кто найдёт ответ для как можно большего значения n. Отличный способ проверить свои силы, так как практика показывает, что до n=15 почти никто не добирается. К сожалению, конечно. [ Дополнение 10.05.2010. В настоящий момент конкурс завершён, формула получена ].
Доказано, что когда количество ферзей фиксировано, а доска имеет переменный размер, то знаменатель производящей функции имеет (возможно, комплексные) корни, равные по модулю единице. Это обстоятельство позволяет нам угадать производящую функцию, зная ответы для некоторых подряд идущих n=1,2,3… Например, для задачи о пяти ферзях, мне потребовалось посчитать ответы до n=38 (степень знаменателя равна 37). Для шести ферзей, видимо, степень будет чуть меньше 80 (следует из моих эмпирических соображений).
Существуют и другие варианты задачи, например, когда доска не квадратная, а прямоугольная или в форме тора (то есть выход ферзя за границу доски равносилен появлению его с противоположной стороны). Также интересными являются варианты, когда каждый ферзь бьёт ровно одного другого ферзя. Знакомые физики утверждают, что такие задачи имеют реальные физические приложения, однако мне они неизвестны.
Многие люди, работающие в промышленности (или в другой области, менее связанной с фундаментальными исследованиями) продолжают считать такого рода упражнения бесполезной тратой времени. Более полезно – считают они – сделать красивый и понятный интерфейс, а будет ли это работать эффективно – вопрос второстепенный. В данном случае это не совсем правильно. Решение подобных задач позволяет научным сообществам показывать друг другу свои навыки, уровень своей научной школы, а также демонстрировать прочие показатели успешности. А смысл этого в том, что когда возникает действительно полезная для общества задача похожего типа, то её, как правило, дают решать наиболее продвинутому в этой области коллективу учёных. С другой стороны, даже если та или иная задача сама по себе практической ценности не имеет, её решение позволяет развить новые методы в математике и программировании.
Чтобы понять, насколько многолика и важна эта задача, достаточно зайти в упомянутую мной выше энциклопедию целочисленных последовательностей и набрать в поиске слово «Queen». Вам предложат более 250 задач, где встречается ферзь. Причём некоторые из этих задач удивительным образом перекликаются с научными (и не совсем) проблемами, которые никакого отношения к шахматам не имеют.
Список источников
