8 ферзей на шахматной доске варианты
Задача «8 ферзей»
«8 ферзей» – отличная задача-головоломка для развития логического мышления. Эта online флеш-игра является своеобразной современной формулировкой известной шахматной задачи, придуманной шахматистом Максом Базелем в 1848 г.
Любители шахмат наверняка слышали об этой самой популярной математической игре на шахматной доске. Поиск ответа на вопрос о том, как же все-таки расставить 8 ферзей в этой задаче, будет полезным для всех, кто хочет развивать свои интеллектуальные способности, находить решения нестандартных задач, продумывать ходы в поисках ответа.
Правила. Задача о 8 ферзях имеет своим единственным условием задание расставить на стандартной шахматной доске (64 клетки, 8х8) 8 фигур – ферзей, (или королев, если угодно), таким образом, чтоб ни одна из них не была под боем другой.
Полезные советы или в поисках решения
Всего оригинальных решений 12. Общее количество возможных (с учетом применения операции симметрии) вариантов – 92. Первым опубликовал ответ на эту задачу в 1850 г. Франц Нак. С тех пор многие ученые решали и исследовали эту задачу, предлагая собственные варианты решения. Так, известный немецкий математик, механик и физик Карл Гаусс очень любил эту головоломку и находил 72 варианта возможной расстановки. Он творчески подошел к процессу поиска ответа – разные комбинации 8 ферзей достигались с помощью интересного приёма… поворота доски на 90, 180 и 270 градусов соответственно. Такое вот нетривиальное решение этой головоломки.
Задача достаточно сложная, но как минимум один вариант как правильно расставить ферзей находится довольно быстро и называется явным. Самое популярное правильное расположение достигается следующей расстановкой ферзей: a2, b4, c6, d8, e3, f1, g7, h5. Схема данной расстановки изображена на первом рисунке, оставшиеся три способа расставить ферзей были найдены при вращении шахматной доски.
Другие комбинации постарайтесь найти самостоятельно. Успехов!
Тренируемые навыки
При поиске ответа на задачу тренируются следующие навыки:
-
– способность находить нестандартные решения интеллектуальных задач, действовать не на основе изобретенного алгоритма, адаптивно ведя поиск ответа; – вид умственной деятельности и избирательное направление восприятия, без которых концентрация на предмете невозможна;
- логическое мышление – вид мыслительного процесса, при котором знание достигается путем применения в рассуждении понятий и логических конструкций.
Любите подобные загадки, игры, головоломки и тесты? Получите неограниченный доступ ко всем интерактивным материалам на сайте, чтобы развиваться эффективнее.
Отзывы и комментарии
Желающие познакомится с основами решения этой задачи в математической комбинаторике и программировании могут прочитать статью в Википедии. Своими успехами, найденными вариантами расстановки и мыслями о данной игре вы можете поделиться ниже.
Разбираемся, что же там нового открыли в задаче о ферзях
Пару месяцев назад появилась занятная статья с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.
Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)
Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:
- Отличная статья ---пресс служба университета--->невразумительный пресс-релиз.
- Пресс релиз ---занятный перевод--->непонятная статья на гиктаймс
Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.
Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.
О чём пойдёт речь:
История задачи
Латинский квадрат
Задача известна еще с древности (
средних веков), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:
Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.
Задача о восьми ферзях
Задачу придумал в 1848 году шахматный композитор Макс Беззель: суть задачи в том, чтобы расставить 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга. С тех пор многие математики, например Гаусс, работали над задачей, а алгоритмисты и программисты, такие как Дейкстра, придумали множество подходов к поиску и подсчету решений.
В задаче, о которой мы будем говорить, не 8 ферзей, а N и доска, соответственно, не обычная шахматная, а NxN.
Три типа задачи "о ферзях"
Есть три наиболее популярных постановки задачи о ферзях
Расстановка N ферзей
Задача формулируется очень прямолинейно.
Дано: пустая доска NxN, например 8х8
(в принципе понятно, что достаточно просто указать N, но так наглядней)
Найти: расстановку максимально возможного числа ферзей
Т.е. на вход число — размер доски, а на выход позиции ферзей (одного решения).
Подсчет числа решений
Задача ставится тоже достаточно просто:
Дано: размер пустой доски N
Найти: H число возможных расстановок N ферзей на доске
Например, размер доски N = 1, тогда число возможных расстановок H = 1.
N = 8 => H = 92.
Дополнение до N ферзей
Вот тут формулировка чуть-чуть коварней:
Дано: размер доски N и M позиций уже установленных ферзей
Найти: позиции оставшихся N — M ферзей
Визуально все как на КПДВ:
(картинка также из оригинальной статьи)
Вариации задачи
В подобной вариации решения существенно отличаются (белые не бьют белых, а черные черных: в случае путаницы — см. комментарии тут):
(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного — но не обоих сразу; взято из статьи)
Модели и сложность задач
Пришло время собственно обсудить: а как это вообще все решать и насколько быстро это вообще можно сделать?
Линейный поиск для классической задачи
Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: Зачем нам всем нужен SAT и все эти P-NP (часть первая) и вторая вот тут. Однако, задача решается без перебора вариантов! Т.е., для доски любого размера можно всегда расставить ферзей один за одним лесенкой:
Существует целый ряд алгоритмов расстановки, например см. вот эту статью или даже вот тут в Вики.
Отсюда вывод, для N = 1 и N > 3 решение всегда есть (см. алго), а для N = 2 или N = 3
всегда нет (тривиально следует из доски). Это значит, что задача разрешимости для N ферзей (где нужно сказать есть решение или нет) решается тривиально за константное время (ну ок, конструктивно за линейное — расставить/проверить).
Самое время перепроверить прочитанное, читаем типичный заголовок "задачу о N ферзях признали NP-полной задачей" — у вас замироточили глаза?
Как считать число решений на практике
Решение: выписываем табличку и по n, возвращаем а(n)
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528
Однако, если у вас какая-то хитрая разновидность задачи и все-таки нужно посчитать решения (а их количество неизвестно и раньше их никто не посчитал), то лучший вариант прототипа обсуждается чуть ниже.
Дополнение до N и Answer Set Programming
Тут начинается самое интересное: в чём же состоит новый результат статьи? Задача о дополнении до N ферзей — NP-полна! (Интересно, что про NP-полноту дополнения латинского квадрата было известно ещё в 1984-ом году.)
Что это означает на практике? Самый простой способ решишь эту задачу (или вдруг, если нам нужно её вариацию) — использовать SAT. Однако, мне больше нравится следующая аналогия:
SAT — это ассемблер для комбинаторных NP-задач, а Answer Set Programming (ASP) — это С++ (у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP, была придумана в 1988ом году Михаилом Гельфондом и Владимиром Лифшицем, работавших тогда в университетах Техаса и Стэнфорда соответственно).
Если говорить упрощенно: ASP — это декларативный язык программирования ограничений (constraints в англоязычной литературе) с синтаксисом Prolog. То есть мы записываем, каким ограничениям должно удовлетворять решение, а система сводит всё к варианту SAT и находит нам решение.
Детали решения здесь не столь важны, и Answer Set Programming достоин отдельного поста (который лежит у меня в черновике уже неприлично долго): поэтому разберем концептуальные моменты
Строка 1 < queen(X,Y) : column(Y) >1 :- row(X). — называется choice rule, и она определяет, что является допустимым пространством поиска.
Последние три строки называются integrity constraints: и они определяют каким ограничениям должно удовлетворять решение: не может быть ферзя в одном и том же ряду, не может быть ферзя в одной и той же колонке (опущено, в силу симметрии) и не может быть ферзя на одной и той же диагонали.
Безусловно, если впервые писать на ASP, то первая модель не выйдет невероятно эффективной и быстрой, но скорее всего будет быстрее перебора с возвратом, написанным на скорую руку. Однако, если понять основные принципы работы системы, ASP может стать "regexp для NP-полных задач".
Проведем простой численный эксперимент с нашей ASP моделью. Я добавил 5 коварных ферзей в модель и запустил поиск решения для N от 1 до 150 и вот, что вышло (запущено на обычном домашнем ноутбуке):
Итого, наша ASP модель примерно в течении минуты может найти решения задачи о дополнении при N <= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.
Решение задачи о 8 Ферзях с помощью массива
Каждый, наверное, сталкивался с задачей расстановки 8 ферзей на шахматной доске.
Рассмотрим решение данной задачи с использованием массива.
Итак, имеем одномерный массив состоящий из 8 элементов. Индексные значения — это строки, а значения в архиве по соответствующим индексам — это столбец шахматной доски соответственно.
Для того, чтобы мы оставили Ферзя в покое и начали перемещать следующего, должны отсутствовать иные Ферзи:
1. по вертикали
2. по диагоналям
3. по горизонтали
Третий пункт в данном методе решения этой задачи можно исключить сразу, так как два Ферзя в одной строке мы изначально не рассматриваем.
На рисунке показано, какие поля попадают под «бой» (Q — устанавливаемый Ферзь, q — поля на которых не должно быть других.)
Из чего получаем, что нам необходимо для исключения вертикали сравнить равенство номер столбцов, а для исключения диагоналей сравнить модуль разницы столбцов с разницей строк у устанавливаемого и проверяемого Ферзей.
Вот что мы в итоге получаем:
public class Ferzi2 < static int[] chessboard = ; static int index = 0; static int version = 0; public static void main(String[] args)
Задача о восьми ферзях
Содержание
Формулировка [ ]
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:
- Построить одно, любое решение задачи.
- Аналитически доказать, что решение существует.
- Определить количество решений.
- Построить все возможные решения.
- Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N×N клеток (при этом при 1<N<4 задача не имеет решения).
Мы же подробнее рассмотрим классический “шахматный” случай для доски 8*8.
Особенности решения [ ]
Программа, реализующая этот алгоритм на QBasic.
Алгоритм на QBasic Результаты работы программы (вывод)Список позиций, выдаваемый программой, является списком решений исходной задачи:
Интересно отметить, что эти 92 расположения разбиваются на 12 групп: 11 групп по 8 и одну из 4 расположений. Положения внутри групп получаются из одного положения путём преобразований симметрии: отражения от вертикальной и горизонтальной осей, отражения от диагоналей доски и поворотов на 90, 180 и 270 градусов. Пары расположений, симметричные относительно горизонтальной оси, имеют сумму номеров равную 93, то есть для каждой группы эта сумма равна 93×4.
Ниже приведен только класс, непосредственно реализующий алгоритм решения.
Время выполнения алгоритма [ ]
График зависимости времени от размера (экспоненциальный)
Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core2 Q6600 @ 2.4 ГГц):
| Размер | Решений | Время (мс) |
|---|---|---|
| 4 | 2 | 1 |
| 5 | 10 | 2 |
| 6 | 4 | 2 |
| 7 | 40 | 2 |
| 8 | 92 | 3 |
| 9 | 352 | 6 |
| 10 | 724 | 16 |
| 11 | 2 680 | 69 |
| 12 | 14 200 | 376 |
| 13 | 73 712 | 2 311 |
| 14 | 365 596 | 15 411 |
| 15 | 2 279 184 | 108 587 |
| 16 | 14 772 512 | 812 945 |
Здесь приведена программа, решающая задачу для размеров доски от 1 до 17. Программа измеряет и выводит время работы алгоритма.
Вариант решения на CВремя выполнения алгоритма [ ]
Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core i5-2410M @ 2.3 ГГц):
| Размер | Решений | Время (с) |
|---|---|---|
| 1 | 1 | 0.000 003 |
| 2 | 0 | 0.000 001 |
| 3 | 0 | 0.000 001 |
| 4 | 2 | 0.000 004 |
| 5 | 10 | 0.000 008 |
| 6 | 4 | 0.000 025 |
| 7 | 40 | 0.000 091 |
| 8 | 92 | 0.000 347 |
| 9 | 352 | 0.001 508 |
| 10 | 724 | 0.008 023 |
| 11 | 2 680 | 0.031 750 |
| 12 | 14 200 | 0.114 120 |
| 13 | 73 712 | 0.538 676 |
| 14 | 365 596 | 3.267 996 |
| 15 | 2 279 184 | 21.486 720 |
| 16 | 14 772 512 | 147.388 255 |
| 17 | 95 815 104 | 1 088.978 601 |
| 18 | 666 090 624 | 8 776.579 792 |
Вариант решения для доски размера до 10-11 на Oracle 11 SQL [ ]
Использован усовершенствованный метод поиска с возвратом:
На доске есть четыре типа ресурсов: вертикали, горизонтали, левые и правые диагонали. Каждая поставленная фигура на доску «потребляет» одну горизонталь, одну вертикаль, и две диагонали. Соответственно, следующего ферзя мы будем пробовать ставить на ту клетку, для которого есть оставшиеся незанятые горизонталь, вертикаль и диагонали. Этим существенно сокращаем время перебора.
8 ферзей на шахматной доске. Математика, логика, игра
Задачу о восьми ферзях на шахматной доске пробовали решить, вероятно, все, кто знает, как ходит ферзь. Эта довольно сложная математическая и игровая головоломка была изучена и описана знаменитыми математиками в середине 19 века. Найдены были 92 решения задачи и доказано, что других вариантов быть не может.
Напомню условия задачи: на шахматной доске необходимо расставить 8 ферзей таким образом, чтобы они не смогли убить друг друга . Мне довелось изучать азы шахматной игры в Доме пионеров, и мой первый тренер ставил перед новичками такую задачу уже на первых занятиях , едва показав правила передвижения фигур.
Естественно, с первой попытки никто задачу не решал. Как, впрочем, и со второй, пятой или двадцатой. Тренер решения не давал сравнительно долго, и месяц-два мы на занятиях занимались его поиском.
Те, кто находил ответ в шахматных книгах, пытались выдать решение за самостоятельное, - тогда преподаватель предлагал найти ещё как минимум три-четыре варианта ответа. Мы, не задумываясь, вновь приступали к поиску решений и, настоящее чудо, - самостоятельно делали математическое открытие, находили ответы.
Это были уже не совсем шахматы: для нахождения ответа надо было просто подключить логику, а не искать ответ "методом тыка", - простым перебором вариантов расстановки ферзей. Кстати, примерное количество вариантов механического перебора вариантов составляет 40000 - это сделать сложно, долго и скучно. А суть "открытия" в следующем: достаточно было повернуть доску три раза под прямым углом - и вот они, три новые позиции с правильным ответом. Ещё одно решение: расстановка на доске зеркального отражения фигур.
Главное не в том, что мы узнали решение задачи, а в том, что нам понравилось мыслить логически, самостоятельно формулировать сложные логические выводы . Так тренер прививал нам интерес к логике, математике через великолепную игру - шахматы.
Попробуйте решить эту задачку с ребёнком : вы многое узнаете о его способностях к логическому мышлению, увидите внутренний настрой к преодолению трудных задач. Пусть он не сможет найти решение, - достаточно увидеть вспыхнувшие интересом глаза ребёнка . Если они загорелись, - пора отдавать его в шахматную секцию.
"Задача о восьми ферзях" и миллион долларов
В мире шахмат «задача о восьми ферзях» известна с 1850 года. Условие ее состоит в следующем: необходимо расставить 8 ферзей таким образом, чтобы они не имели возможности «напасть» друг на друга в один ход. По мнению специалистов, данная задача имеет много общего с программированием.
Исследователи из британского Университета Сент-Эндрюс под руководством профессора Яна Гента предложили программистам найти простое решение этой старинной шахматной головоломки. Задача — написать программу, которая сможет решать «Задачу о ферзях» для больших досок с достаточной скоростью. Победителя ожидает солидный приз размером 1 млн. долларов.
Причина такой высокой награды проста — по расчетам математиков, эта задача невыполнима. Подсчитано, что на 64-клеточной (8 х 8) доске количество возможных расположений восьми ферзей равно 4 426 165 368, а число «правильных» расположений в соответствии с условиями задачи – всего 92. Однако, если доска будет иметь конфигурацию 1000 х 1000 клеток, компьютерные программы просто зависнут, не осилив гигантское количество вариантов.
По мнению профессора Гента, если будет написана компьютерная программа, которая сможет решать эту сверхзадачу с достаточной скоростью, ее можно будет адаптировать для решения многих важных проблем — в частности, для дешифровки самых сложных криптографических алгоритмов.
Задача о 16 ферзях.
Давайте сегодня немного отдохнем от решения задач, а попробуйте решить шахматную головоломку.
Вы наверное слышали задачу о 8 ферзях, которых нужно расставить на доске так, чтобы они не находились под боем друг друга? Это классическая задача была решена еще в XIX веке и до сих пор остается актуальной и интересной. Сформулирована она очень просто, но в ней заложен математический потенциал, чем и объясняется большой интерес к этой задачи. Сможете вспомнить как их расставить?
Взято с Яндекс.Картинок Взято с Яндекс.КартинокДавайте теперь усложним задачу. Возьмем вдвое больше ферзей (16) и расставьте их так, чтобы ни на одной прямой не стояло больше двух ферзей. При чем прямыми считаются не только вертикали,горизонтали и диагонали, но и вообще любые линии, проходящие через центры полей.
Как расставить на доске 16 ферзей, так чтобы на каждой линии стояло не более двух фигур?
Ответы можете прислать в виде фотографии или картинки, понравилась задача ставьте лайк, делитесь с друзьями задачей в социальных сетях.
8 ферзей на шахматной доске
Восемь ферзей на шахматной доске — головоломка, которая адресована начинающим игрокам для развития пространственного мышления и аналитических способностей. Автором задачи стал теоретик шахмат Макс Беззель (1824-1871). Условия головоломки были сформулированы в 1848 году: игроку предстояло расположить на классической шахматной доске восемь ферзей так, чтобы ни одна из фигур не находилась под боем любой другой. Задача усложняется геометрией ферзевых ходов, которые осуществляются не только по вертикали или горизонтали, но и в диагональном направлении.
Классическая версия головоломки может формулироваться в нескольких вариантах:
- найти любое допустимое решение;
- выявить все возможные варианты решений;
- доказать возможность решения задачи.
Модифицированная версия головоломки Беззеля используется при обучении школьников основам программирования и математического анализа. Ученикам предлагается расставить N фигур на доске N×N клеток. В качестве N выступает любое целое число. Многочисленные исследования показали, что при значениях переменной, равным 2, 3 или 4, задача становится нерешаемой.
Смотрите также: Что означает слово шахматы?Допустимые варианты решения
За 170 лет шахматистам удалось найти 12 базовых решений для головоломки Беззеля. Они рассматриваются в качестве основных во всех учебниках по шахматной теории. Учет правил симметрии позволит расширить число доступных решений до 92: расположение фигур относительно друг друга будет неизменным, варьируются только координаты клеток с ферзями.
Как расставить 8 ферзей на доске
Головоломка Беззеля рассматривается тренерами как задача средней сложности: подходящее решение могут обнаружить новички за несколько минут. Наиболее известная расстановка фигур отражена в таблице.
| Номер ферзя | Координаты |
| Первый | h5 |
| Второй | f1 |
| Третий | d8 |
| Четвертый | b4 |
| Пятый | g7 |
| Шестой | e3 |
| Седьмой | c6 |
| Восьмой | a2 |
Три дополнительных варианта можно получить с помощью последовательного поворота доски по предложенному Гауссом принципу. Аналогичным образом действует зеркальное отражение расстановки фигур.
Смотрите также: Шахматы для дошкольниковРешение задачи о восьми ферзях полезно для формирования навыков счета ходов, анализа текущей позиции на доске и поиска быстрого ответа на комбинацию соперника. Новичкам рекомендуется искать варианты расстановки фигур без использования ухищрений в виде поворотов игрового поля. В этом случае все обнаруженные решения станут результатом интеллектуальных усилий игрока.
Модифицированные условия задачи Беззеля часто используются в математических секциях или на уроках информатики. Так, осваивающие основы программирования ученики могут создать скрипт для поиска решений при фиксированном или произвольном значении переменной N, обозначающей количество расставляемых на доске фигур и размеры игрового поля.
Глава 8. Задача о восьми ферзях
Задача о восьми ферзях, как и задача о ходе коня, является одной из самых знаменитых математических задач на шахматной доске. Если задачей о коне занимался Леонард Эйлер, то задача о ферзях привлекла внимание другого великого математика - Карла Гаусса.
Сколькими способами можно расставить на шахматной доске восемь ферзей так, чтобы они не угрожали друг другу, т. е. никакие два не стояли на одной вертикали, горизонтали и диагонали?
Рис. 43. Восемь ферзей, не угрожающих двуг другу на шахматной доскеЛюбопытно, что многие авторы ошибочно приписывают задачу о восьми ферзях и ее решение самому Гауссу. На самом деле первым ее сформулировал в 1848 г. немецкий шахматист М. Беццель. Доктор Ф. Наук (слепой от рождения) нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс увлекся задачей и нашел 72 решения, которые сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук (он привел их в упомянутой газете от 21 сентября 1850 г.). Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом, который в своих книгах немало места уделил рассматриваемой задаче.
Доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей).
В принципе, расставляя на доске восемь ферзей всевозможными способами, мы в конце концов найдем все устраивающие нас расстановки. Однако этот путь чересчур долог и скучен. Можно ограничиться только решениями соответствующей задачи о ладьях и отобрать среди них такие, в которых никакая пара ладей не стоит па одной диагонали. Но и в этом случае перебор довольно велик (понадобятся, как мы знаем, более 40000 попыток). Таким образом, при решении задачи «вручную» (а именно так поступали в прошлом веке) вынужденный перебор расстановок должен быть хорошо продуман. Известно много способов организовать более или менее разумный поиск искомых расположений ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике (в основном в прошлом столетии и начале нынешнего). В наш век вычислительных машин задача такого сорта не смогла бы вызвать столь живой интерес. Ведь достаточно составить несложную программу для ЭВМ - и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.
Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски вокруг центра на 90, 180 и 270° по часовой стрелке (поворот на 360° приводит к исходной позиции). Из данной расстановки ферзей новую можно получить также зеркальным отражением доски относительно одной из пунктирных прямых на рис. 43 (1-я позиция)35. Например, из первой расстановки на этом рисунке при повороте доски на 90° мы получаем третью, а при отражении относительно линии, разделяющей королевский и ферзевый фланги, - четвертую. При помощи других поворотов и отражений можно получить еще пять решений.
В случае а) исходное решение называется дважды симметрическим, в случае б) - симметрическим, а в случае в) - простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует. Алгебраическую интерпретацию решений каждого класса можно найти у Окунева.
Множество (набор) расстановок восьми ферзей называется основным,если они, во-первых, не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи этих преобразований. Известно, что всякий набор основных решений задачи содержит ровно 12 позиций (расстановок восьми ферзей). Приведем одип из таких наборов:
| 1) | a4, b1, c5, d8, e6, f3, g7, h2; |
| 2) | a4, b2, c5, d8, e6, f1, g3, h7; |
| 3) | a4, b2, c7, d3, e6, f8, g1, b5; |
| 4) | a4, b2, c7, d3, e6, f8, g5, h1; |
| 5) | a3, b5, c2, d8, e6, f4, g7, h1; |
| 6) | a3, b7, c2, d8, e5, f1, g4, h6; |
| 7) | a4, b7, c3, d8, e2, f5, g1. h6; |
| 8) | a6, b4, c2, d8, e5, f7, g1. h3; |
| 9) | a4, b8, c1, d5, e7, f2. g6, h3; |
| 10) | a4, b2, c7, d5. e1. f8. g6, h3; |
| 11) | 1-я позиция на рис. 43; |
| 12) | 2-я позиция на рис. 43. |
Первая расстановка на рис. 43 любопытна тем, что здесь никакие три ферзя не стоят на одной прямой, проведенной через центры полей (имеются в виду не только вертикали, горизонтали и диагонали доски* но и прямые с другими углами наклона).
Числовая запись расстановок ферзей иногда бывает очень удобной. Например, для нахождения расстановок при фиксированном расположении ферзя на a1 достаточно из всех 92 позиций, записанных в числовой форме, отобрать такие, у которых первая координата равна 1. Если фиксировано положение ферзя на d3, то следует выделить позиции, у которых на четвертом месте стоит число 3, и т. д.
Запишем числа 1, 2, …, 8 сначала по возрастанию, а потом по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки, например (3, 7, 2, 8, 5, 1, 4, 6):
| + | 1, | 2, | 3, | 4, | 5, | 6, | 7, | 8 | + | 8, | 7, | 6, | 5, | 4, | 3, | 2, | 1 |
| 3, | 7, | 2, | 8, | 5, | 1, | 4, | 6 | 3, | 7, | 2, | 8, | 5, | 1, | 4, | 6 | ||
| 4, | 9, | 5, | 12, | 10, | 7, | 11, | 14 | 11, | 14, | 8, | 13, | 9, | 4, | 6, | 7 |
Полученные суммы образуют два набора чисел: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Возникает следующая задача.
Какие перестановки чисел 1, 2,…, 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все числа различны?
Задача о восьми ферзях заинтересовала Гаусса именно в связи с этой чисто арифметической задачей. Оказывается, между решениями задачи о ферзях и решениями описанной арифметической задачи существует взаимно однозначное соответствие. Другими словами, каждая расстановка восьми ферзей, не угрожающих друг другу, дает решение арифметической задачи - и наоборот. Для выбранной перестановки оба набора состоят из различных чисел, и это не случайно - она соответствует первой позиции на рис. 43.
Нетрудно видеть, что при поворотах n отражениях доски одни решения получаются из других при помощи простых арифметических операций над координатами полей, занятых ферзями. Исследование этих операций позволяет обнаружить дополнительные свойства решений (некоторые из которых приведены у Окунева).
При n = 6k + 2 предыдущий прием уже не проходит, и ферзей приходится расставлять более «хитрым» способом. Расположим их ходом коня со второй вертикали по
(n/2 - 2)-ю, начиная с третьей горизонтали, и далее с
Читайте также: