Около шахмат

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

Одна из тем, которые я всегда старался максимально подробно разжевать своим бывшим ученикам, - переборные алгоритмы. Обычно я их иллюстрировал разнообразными околошахматными задачами. Когда-то для такого "перекоса" в изучении этой темы были самые серьезные мотивы: если плохо написать перебор, то самая пустяковая программа работала бы несколько часов. Сейчас персоналки стали гораздо шустрее, да и многозадачность сильно выручает, так что мои любимые задания перешли в разряд любительских упражнений. Иными словами - в материалы для рубрики "Досуги".

Сюжет 1

Сколькими способами можно расставить 8 ферзей на шахматной доске так, чтобы они не били друг друга?

Легенда приписывает формулировку и решение этой задачи "королю математиков" Гауссу. Именно он первым перебрал все способы - их оказалось 92. Любопытно, что и сейчас авторы учебников очень любят демонстрировать метод бектрекинга (перебора с возвратом) именно на этой задаче. Так что желающим предлагается попробовать свои силы. Это не так сложно, как кажется.

Но есть и продолжение сюжета: а сколько существует способов, принципиально отличающихся друг от друга, то есть не переходящих один в другой при поворотах и отражениях? Я не сомневаюсь, что каждый из вас смог бы ответить на этот вопрос, внимательно изучив 92 картинки-решения. А не слабо научить это делать программу? Можете считать, что "картинки" у вас уже есть.

Не очень сложно доказать, что если N не делится ни на 2, ни на 3, то задача о расстановке ферзей для доски NxN всегда имеет хотя бы одно решение. Поэтому естественным обобщением сюжета будет найти число решений для досок с произвольным N>4.

Наконец, вот еще малоисследованный вариант той же задачи: сколько ферзей можно поместить на кубическую доску NxNxN так, чтобы они не били друг друга? Будем считать, что ферзи в пространстве бьют не только по вертикалям и диагоналям в каждой плоскости, но и вдоль диагоналей куба.

Сюжет 2

Какое наименьшее число ферзей можно расставить на шахматной доске так, чтобы они держали под контролем все поля доски?

Эта задача (известная под названием "задача о доминировании ферзей") тоже хорошо известна, и ответ в ней - 5. Вариантов расположения существует довольно много, а вот сколько именно? А если опять-таки рассматривать варианты с точностью до поворотов и симметрий? А для произвольного размера доски? Например, для доски 11x11 тоже хватает пяти ферзей, а для доски 35x35 хватает 19 ферзей. (А вот хватит ли восемнадцати - вроде бы неизвестно). А как обстоит дело для трехмерных досок?

Вместо ферзя можно брать и другие фигуры (слона, коня, ладью, короля). Для каждой из них можно посчитать "число независимости" и "число доминирования", а также количество решений в каждом случае. Иногда этот результат можно получить чисто теоретически, без перебора, иногда перебор все-таки необходим. Более-менее полная сводка результатов приведена в книге Евгения Гика "Математика на шахматной доске", а также в некоторых других книгах и статьях того же автора.

Сюжет 3

Как обойти конем шахматную доску, не побывав ни на каком поле дважды и вернувшись в исходную клетку?

Совершенно заслуженно выражение "ход конем" означает в русском языке очень хитроумный и нетривиальный замысел. Вот и задача обхода доски является довольно крепким орешком, на котором обламывают зубы даже некоторые профессионалы. Нет, конечно, найти какой-то один обход не так сложно. Например, легко можно нарисовать на бумаге маршрут обхода конем доски 4x4, а потом разорвать 4 этих маршрута вблизи центра доски и склеить из них один маршрут. Есть и другой известный способ: сначала обойти "кайму" доски шириной в две клетки, а потом - центральные 16 клеток.

Но меня в этом сюжете интересует (и всегда интересовало) не реализация конкретного обхода, найденного фактически вручную, а совершенно другое. Например, пусть обход уже начат - конь уже побывал на нескольких клетках. Можно ли завершить этот обход? Если да, то как действовать? Очевидно, что здесь задача совершенно не зависит от конкретного размера и даже от формы доски. Точно такую же задачу можно поставить на совершенно произвольном графе. Единственное, что нам здесь нужно от коня и доски - это знать, какие клетки для коня являются "соседними", а какие - нет.

Вот как раз в этой задаче полный перебор всех вариантов недоступен даже для нынешних компьютеров, так что приходится искать иные пути. Собственно, хорошие идеи давно известны. Например, известно такое правило: конь всегда должен перескакивать на клетку, для которой количество возможных ходов с нее является наименьшим. А если таких клеток несколько? Однозначного рецепта, как видите, нет…

Сюжет 4

Шахматный король путешествует из одного угла доски MxN в противоположный. При этом он может пройти не по всем клеткам, но ни на какую клетку не должен становиться дважды.

Это еще одна известнейшая задача об обходе доски. Число решений (не самопересекающихся королевских маршрутов) очень быстро растет с ростом размеров доски. Например, на доске 3x3 их всего 12, для доски 4x4 их уже 184, а для 4x8 - 163496. Попробуйте написать программу, которая решала бы задачу о нахождении а) всех таких маршрутов; б) только их количества.

Сюжет 5

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

Попробуйте поиграть в такую игру, для начала можно взять даже не все восемь пешек, а всего по четыре или даже по три с каждой стороны. Если эта игра вам понравится и не покажется сильно простой, попробуйте написать программу, которая будет играть (грамотно играть, а не просто двигать пешки!) за одну из сторон. Когда напишете - присылайте мне, и мы попробуем устроить турнир таких программ.

Пишите письма, заходите на WWW-страничку.