156. О восьми королевах

На шахматной доске, состоящей из 64 клеток, расставить восемь королев так, чтобы ни одна из них не могла бить другую. Другими словами: на восьми клетках шахматной доски поставить восемь королев так, чтобы каждые две из них не были расположены ни на одной линии, параллельной какому-либо краю, и ни на одной из прямых, параллельных какой-нибудь диагонали доски.

Этой задачей занимался знаменитый немецкий математик Гаусс.

Покажем некоторые решения этой задачи и приведем затем таблицу всех 92 ее решений.

На прилагаемом рис. 146 содержится одно из решений.

Рис. 146

Обозначим это решение восемью цифрами (68 2 4 1 7 5 3), где каждая цифра означает высоту королевы в каждой колонне доски, т. е. 6 показывает, что королева находится в первой колонне на шестой клетке, считая снизу, 8 - что королева находится во второй колонне на восьмой клетке, считая снизу, и т, д. Мы и впредь вертикальные ряды клеток будем называть колоннами, а горизонтальные - линиями. Линии мы тоже будем обозначать числами от 1 до 8 и считать их снизу вверх. Таким образом, записанное нами выше первое решение с помощью одного ряда чисел было бы правильнее записать так:

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

Рис. 147

Чтобы получить это соответственное решение численно из первого, достаточно расположить колонки таблички (А) так, чтобы цифры первой строки шли в убывающем порядке:

(В) 8 7 6 5 4 3 2 1

2 6 1 7 4 8 3 5

Цифры второй строки полученной таким способом таблички образуют соответственное первому решение (В) (26174835).

Следующие два рисунка (рис. 148 и 149) представляют второе и третье решения, соответственные рис. 146. Их можно получить, заставляя шахматную доску вращаться еще на четверть и еще на четверть окружности в направлении, обратном движению часовой стрелки. Можно вывести также, подобно предыдущему численное обозначение, положения III (рис. 148) из положения II (рис. 147), а положения IV (рис. 149) из положения III. Но можно и прямо положение III получить из I, а положение IV - из II.

Рис. 148

Рис. 149

Для этого поступаем так. Решения рис. 146 и 147, обозначены у нас рядами цифр:

Напишем эти цифры в обратном порядке:

и вычтем каждую из этих цифр из 9, получим

Это и будут численные обозначения решений на рис. 148 и 149.

Таким образом, в общем случае некоторые решения задачи о королевах дают место еще трем соответственным решениям.

На рис. 150 дано другое решение задачи. Особенность его заключается в том, что из него получается только одно соответственное решение (рис. 151). В самом деле, если повернуть шахматную доску на полуокружность, то получаем опять то же расположение. Ряд цифр (46827 135), изображающий это решение, отличается тем, что, сложенный с рядом, состоящим из тех же цифр, но написанным в обратном порядке, дает (99999999).

Рис. 150

Рис. 151

Возьмем какое-нибудь решение задачи о восьми королевах и перевернем на рисунке порядок колонн, т. е. 1-ю сделаем 8-й, 2-ю сделаем 7-й и т. д. Или, что сводится к тому же, напишем числовое обозначение решения в обратном порядке - мы получим решение, обратное данному. Легко убедиться, что это решение отличается от всякого из соответственных решений.

Рис. 152

Опуская способы отыскания самых простейших решений задачи, дадим эти решения на рис. 152. Каждое из решений I - XI дает, как выше объяснено, 4 соответственных и 4 обратных, т. е. всего 8 решений, последнее же, XII, дает только 4 решения, Всего, следовательно, получается 92 решения, которые исчерпывают все решения задачи. Вот таблица всех этих решений:

Таблица всех решений задачи о восьми королевах

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

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