----- На следующий день -----
Что означает название?
Ферзь в шахматах может ходить по горизонтали, вертикали и диагонали. Как разместить 8 ферзей на доске 8x8 так, чтобыЛюбые два ферзя не находятся в одном и том же горизонтальном, вертикальном или диагональном направлении.?
Возьмем каштан Зеленые клетки на картинке ниже — это «заблокированные области» ферзя на шахматной доске, и в эти клетки нельзя ставить других ферзей:
Зеленые квадраты на картинке ниже — это «заблокированные области» двух ферзей на доске, и другие ферзи не могут быть помещены в эти квадраты:
Итак, как следовать правилам и разместить эти 8 ферзей одновременно? Давайте посмотрим на ответ Сяо Хуэя.
————————————
Что такое задача восьми ферзей?
Задача восьми ферзей — старая задача, поставленная шахматистом в 1848 году: расставить восемь ферзей на шахматной доске 8×8 так, чтобы они не могли атаковать друг друга, то есть никакие два ферзя не могут находиться в одной и той же позиции. решить ту же строку, тот же столбец или ту же косую черту?
Многие математики в лице Гаусса последовательно изучали эту проблему. Позже, когда появился компьютер, эту задачу было легко решить с помощью расчетов по компьютерной программе.
Как решить задачу о восьми ферзях?
Так называемый рекурсивный поиск с возвратом по существу является методом перечисления. Этот метод начинает с первого ряда шахматной доски и пытается разместить первого ферзя.После успешного размещения он рекурсирует на один уровень, а затем следует правилам, чтобы разместить второго ферзя на втором ряду шахматной доски. Если текущая позиция не может быть размещена, переместитесь на одну клетку вправо и повторите попытку Если размещение прошло успешно, продолжайте рекурсию на один уровень и поместите третьего ферзя...
Если слой видел все сетки и не может быть успешно размещен, то вернитесь к предыдущей королеве, переместите предыдущую ферзь вправо на одну сетку, а затем выполните рекурсию. Если все восемь ферзей расставлены и соблюдены правила, то получается одно из правильных решений.
Звучит немного абстрактно, давайте подробно рассмотрим процесс рекурсивного поиска с возвратом.
1.первый уровеньрекурсивно, попробуйПервая строкаместопервая королева:
2.Второй этажрекурсивно, попробуйвторая линияместовторая королева(Первые два поля заблокированы первым ферзем и могут попасть только на третье поле):
3.третий этажрекурсивно, попробуйТретий рядместотретья королева(Первые четыре поля заблокированы первым и вторым ферзями и могут попасть только на пятое поле):
4.четвертый этажрекурсивно, попробуйчетвертый рядместочетвертая королева(Первое поле заблокировано вторым ферзем и может попасть только на второе поле):
5.пятый этажрекурсивно, попробуйПятая линияместопятая королева(Первые три поля заблокированы ферзем впереди и могут попасть только на четвертое поле):
6. Поскольку все сетки «зеленые», нет возможности разместить ферзя в шестом ряду, поэтому возвращаемся назад и переставляемпятая королеваприбытьвосьмой. :
7. Пока нет возможности разместить ферзя в шестом ряду, а пятый ряд тоже пробовали, поэтому я вернулся кчетвертый ряд, переставитьчетвертая королеваприбытьседьмой квадрат. :
8. Продолжайте размещать пятого ферзя и так далее...
Реализация кода задачи восьми ферзей?
Решение задачи восьми ферзей можно разделить на два уровня:
1.Найдите первое правильное размещение, то есть обход в глубину.
2.Найти все правильное размещение, то есть обход в ширину.
Из-за приоритета места в этой статье мы расскажем только о том, как найти первый правильный метод размещения.
При изучении реализации кода нам необходимо решить несколько задач:
1. Как изображена шахматная доска?
Очень просто, его можно представить двумерным массивом длины 8.
Поскольку здесь используется массив int, начальное значение int равно 0, что означает отсутствие хода. Когда помещается ферзь, значение соответствующего элемента изменяется на 1.
Здесь первое измерение двумерного массива представляет собой абсциссу, второе измерение представляет собой ординату и начинается с 0. Например, chessBoard[3][4] представляет состояние четвертой строки и пятого столбца шахматной доски.
2. Как определить, соответствует ли расположение ферзя?
Определите метод проверки, укажите точку размещения нового ферзя и оцените, соответствует ли он требованиям, по наличию других ферзей в вертикальном и наклонном направлениях.
3. Как сделать рекурсивный возврат?
Рекурсивный поиск с возвратом является ядром этого алгоритма, а логика кода несколько сложна.
4. Как вывести результат?
Эта задача очень проста, просто пройдите через двумерный массив и выведите его напрямую.
5. Как связать эти методы вместе?
Он вызывается в три шага в основной функции:
Шаг 1: Инициализация
Шаг 2: Рекурсивно поместите ферзя
Шаг 3: Наконец, выведите результат.
где Queen8 — это имя всего класса.
Окончательный вывод выглядит следующим образом:
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000
Несколько дополнений:
1. Из-за недостатка места в этой статье рассказывается только о том, как найти первое правильное размещение восьми ферзей. Если вам интересно, вы можете внести небольшие изменения в код в тексте, чтобы узнать коды для всех восьми ферзей.
2.Этот комикс предназначен исключительно для развлечения, пожалуйста, цените свою текущую работу как можно больше и не подражайте поведению Сяохуэй.
----КОНЕЦ----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента