21. Восемь королев

Во мНОгих случаях никакие предварИТельные расЧЕтЫ не позволяют найти конфигурацию элемеНТов с Заданным Свойствами. Тогда остается единственный путь — перебирать все варианты в НАдежде хотя бы случайно найти желаемую комбинацию. Как рассказывает известный амЕриканский популяризатор Мартин Гарднер, в 1910г. некий Клиффорд У. Адамс решил построить магическИ Шестиугольник. Он взял набор из 19 шестиугольных плиток, написал на них числа от 1 до 19 и начал составлять из них всевозможные шестиугольники, надеясь наткнуться на магический. Этим высокополезным делом он занимался... 47 лет, и только в 1957 г. нашел один такой многоугольник. Затеряв бумажку с решением, и лишь в 1962 г. восстановил решение, и после полувека изысканий опубликовал следующий ответ (рис. 3). Из рисунка видно, что суммы по всем направлеНИям этого мНОгоугольника равны 38. Совершенно неожиданно оказалось, что полученное Адамсом решение единственно - никаких других магических шестиугольников не Существует.

ЗначительНО проще решить перебором следующуЮ задачу: ПостаВИтЬ на шахматную доску наибольшее Число Ферзей (Или, как говорили в старину, королев) так, чтобы ни один из них не мог взятЬ ДРугого. Для читателей НЕзнакомых с шахматной игрой, сообщим, что ферзи могут бить по горизонталям, вертикалям и диагоналям.

Так как на шахматной доске только 8 горизонталей, то ясно, что больше 8 ферзей поставить на доску не удастся. Поэтому попробуем поставить 8 ферзей так, чтобы выполнялось указанное условие. При любой такой расстановке на каждую вертИКаль и каждую горизонталь попадет только один ферзь, а потому можно записать Занятые поля в порядке возрастания номеров вертикалей. Но тогда каждое расположеНиЕ одНОзначно определяется номерами горизонталей занятых полей, т. Е. некоторой перестановкой чисел 1, 2, 3, 4, 5, 6, 7, 8. Например, перестановка 24165873 означает, что на доске заняты поля (1, 2), (2, 4), (3, 1), (4, 6), (5, 5), (6, 8), (7, 7), (8, 3), где (1, 2) — поле, стоящее на пересечении первой вертикали и второй горизонтали и т. д.

Эту задачу можно решить лишь прямым перебором вариантов. Чтобы сократить объем рассматриваемых позиций, поступают так. Сначала ставят ферзя в левый нижНий угол, а затем ставят ферзей на каждую следующую вертикаль на первое снизу поле, не находящееся под боем ранее поставленных ферзей. Если доходят до вертикали, все поля которой биты, то передвигают ферзя на последней из занятых вертикалей, ставя его на следующее поле этой вертикали, НЕ находящеЕСя под боем. Если и ЭТо не помогает, передвигают ферзя по той же вертИКали еще выше. Когда исчерпаны все возможНОсти получить Хоть оДно свободное от боя поле на данной вертикали, переДВигая фЕРзя на предыдущей вертикали, а нужНОй расстаНОвки не найдено, начинают исПРавлять ПОложеНие на вертИКали, расположенНОй еще на один ряд Влево. Через несколько таких шагов получают расстаНОвку Ферзей, которую можно задать последовательностью чисел 1, 5, 8, 6, 3, 7, 2, 4. Продолжая описанный процесс, находим 92 положенИЯ ферзей, обладающих требуемЫМ Свойством.

< Предыдущая		Следующая >