Задача о ходе коня. Задача о восьми ферзях.

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

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

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

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

Задача о ходе коня – задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу. Первое ее упоминание датируется 18 веком, а именно в работе Леонарда Эйлера 1759 года “Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию”. (очень странно, но к сожалению я не смог найти оригинал этой статьи).

Также Эйлер в своей переписке с Гольдбахом “говорил”:

“ …Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашёл, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб. “

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

*Гамильтонов граф – граф, содержащий гамильтонов цикл. Гамильтоновым циклом является такой цикл, который проходит через каждую вершину графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.

Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532.Шахматные математические задачи, стали очень быстро развиваться и множится примерно с 18 века, когда шахматы получили популярность в Европе, а затем и во всем мире. И помимо задачи “ход конем”, имеется множество других, не менее интересных, но о них всех как нибудь позже.

Шахматные математические задачи – это раздел шахматной композиции, где используются логика и математические принципы для поиска решений (мат в N ходов, этюды, задачи на расстановки и т.д.), а также задачи из области комбинаторики и теории графов, решаемые на шахматной доске (например, задача о восьми ферзях, задачи о ходе коня и разрезании доски домино).

Задача о ходе ферзем – это известная комбинаторная головоломка, основная формулировка которой: расставить 8 ферзей на стандартной 8x8 шахматной доске так, чтобы ни один ферзь не атаковал другого (по горизонтали, вертикали, диагонали). Помимо этого, существуют и более простые задачи, где нужно определить, может ли ферзь одним ходом переместиться из одной клетки в другую.

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

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

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей x/y, где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.

На третьем принципе я хотел бы немного остановиться и рассмотреть фигуру автора алгоритма.

Генрих Христиан Варнсдорф (Heinrich Christian Warnsdorff) – немецкий математик и педагог 19 века, который в 1823 году прославился своей философией решения задачи о ходе коня, которую назвали в его честь “Правило Варнсдорфа”. Варнсдорф опубликовал ее в брошюре “Простейшее и наиболее общее решение задачи о ходе коня”. Однако стоит сказать, что Варнсдорф активно занимался теорией графов, и поэтому его решение было не случайным.Правило Варнсдорфа.

Правило Варнсдорфа это разновидность жадного алгоритма, который, формулируется так:

При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них.

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

*Жадный алгоритм – алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.

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

Но так как эта статья о программировании, куда же без написания алгоритма, ниже я приведу пример программы на Python, с двумерным списком для моделирования шахматной доски и массивом смещения (список из 8 возможных ходов у коня), для решения этой задачи.

Переменные и структуры данных.

1. Конфигурационные параметры.

```

board_size = 8

```

Назначение: Определяет размер шахматной доски (8×8 клеток).

Тип: Целое число.

Влияние: Определяет размер матрицы `board`.

```

start_row = 0

start_col = 0

```

Назначение: Координаты начальной позиции коня.

Тип: Целое число.

Влияние: Конь начинает движение из верхнего левого угла (0,0).

2. Структуры данных.

```

board = [[0 for _ in range(board_size)] for _ in range(board_size)]

```

Назначение: Двумерный список (матрица), представляющий шахматную доску.

Размерность: `board_size × board_size` (8×8).

Значения:

- `0` - клетка не посещена.

- `1` - клетка посещена.

Создание: Двойное list comprehension создает матрицу нулей.

```

knight_moves = [...]

```

Назначение: Список всех возможных перемещений коня.

Структура: 8 пар `[Δrow, Δcol]` (изменение строки и столбца).

Логика: Конь движется буквой "Г" - 2 клетки в одном направлении и 1 в перпендикулярном.

```

current_pos = [start_row, start_col]

board[current_pos[0]][current_pos[1]] = 1

```

Назначение: Текущая позиция коня и ее инициализация.

Структура: Список из двух элементов `[row, col]`.

Инициализация: Помечаем начальную клетку как посещенную.

Функции алгоритма.

Функция `draw_board()`

```

def draw_board():

print("Доска (1 - где был конь, 0 - пустая клетка):")

for row in range(board_size):

for col in range(board_size):

print(f" {board[row][col]} ", end="")

print()

```

Назначение: Визуализация текущего состояния доски.

Алгоритм:

1. Выводит заголовок.

2. Для каждой строки `row` от 0 до `board_size-1`:

- Для каждого столбца `col` от 0 до `board_size-1`:

- Выводит значение `board[row][col]` с пробелами.

- Переходит на новую строку.

Результат: Текстовое представление матрицы доски.

Функция `is_valid_move(position)`

```

def is_valid_move(position):

row, col = position

return 0 <= row < board_size and 0 <= col < board_size and board[row][col] == 0

```

Назначение: Проверка допустимости хода в указанную позицию.

Входные данные: `position` - список `[row, col]`.

Логика проверки (три условия через логическое И):

1. `0 <= row < board_size` - строка в пределах доски.

2. `0 <= col < board_size` - столбец в пределах доски.

3. `board[row][col] == 0` - клетка не посещена ранее.

Возвращаемое значение: `True` если ход допустим, иначе `False`.

Инициализация.

```

print(f"Ход 1 - начальная позиция [{start_row}, {start_col}]:")

draw_board()

move_count = 1

```

Действие:

1. Вывод информации о начальной позиции.

2. Отображение начального состояния доски.

3. Инициализация счетчика ходов (`move_count = 1`).

Основной цикл `while True:`

Алгоритм выполняет последовательные итерации до достижения терминального состояния.

Шаг 1: Поиск возможных ходов.

```

possible_moves = []

for move in knight_moves:

next_pos = [current_pos[0] + move[0], current_pos[1] + move[1]]

if is_valid_move(next_pos):

possible_moves.append(next_pos)

```

Цель: Сформировать список всех допустимых следующих ходов.

Алгоритм:

1. Создать пустой список `possible_moves`.

2. Для каждого возможного перемещения из `knight_moves`:.

- Вычислить координаты потенциального хода: `next_pos`.

- Проверить допустимость через `is_valid_move(next_pos)`.

- Если допустим, добавить в `possible_moves`.

Результат: Список всех клеток, куда конь может пойти с текущей позиции.

Шаг 2: Проверка наличия возможных ходов.

```

if possible_moves:

// Есть возможные ходы

...

else:

// Нет возможных ходов

...

```

Логика: Если `possible_moves` не пуст, выбираем первый ход; если пуст - тупик.

Шаг 3: Выполнение хода (если есть возможности).

```

current_pos = possible_moves[0]

board[current_pos[0]][current_pos[1]] = 1

move_count += 1

```

Действия:

1. Обновить текущую позицию на первый элемент из `possible_moves`.

2. Пометить новую клетку как посещенную (`board[...] = 1`).

3. Увеличить счетчик ходов.

Шаг 4: Отображение информации о ходе.

```

print(f"\nХод {move_count}:")

print(f"Конь перемещен в позицию: {current_pos}")

draw_board()

```

Назначение: Визуализация текущего состояния.

Шаг 5: Проверка завершения обхода.

```

all_visited = True

for row in range(board_size):

for col in range(board_size):

if board[row][col] == 0:

all_visited = False

break

if not all_visited:

break

```

Цель: Определить, посещены ли все клетки доски.

Алгоритм:

1. Изначально предполагаем, что все клетки посещены (`all_visited = True`).

2. Проверяем каждую клетку матрицы `board`.

3. Если находим хотя бы одну `0`, устанавливаем `all_visited = False` и прерываем проверку.

Результат: `True` если все клетки = 1, иначе `False`.

Шаг 6: Завершение при полном обходе.

```

if all_visited:

print(f"\nУра! Прошли все поле за {move_count} ходов!")

break

```

Условие: Если `all_visited == True`.

Действие:

- Вывод сообщения об успехе.

- Выход из цикла `while True`.

Шаг 7: Обработка тупика.

```

else:

print(f"\nТупик! Больше нет возможных ходов.")

print(f"Всего сделано ходов: {move_count}")

print(f"Посещено клеток: {sum(sum(row) for row in board)} из {board_size * board_size}")

break

```

Условие: Если `possible_moves` пуст.

Действия:

1. Вывод информации о тупике.

2. Вывод статистики:

- Количество сделанных ходов.

- Количество посещенных клеток (сумма всех элементов матрицы).

- Общее количество клеток на доске.

3. Выход из цикла.

Временная сложность.

Одна итерация цикла: O(8 + n²) ≈ O(n²).

- Поиск возможных ходов: 8 проверок.

- Проверка полного обхода: n² проверок.

Общая сложность: O(k × n²), где k - количество сделанных ходов.

Пространственная сложность.

Основные структуры: O(n²) для матрицы `board`.

Вспомогательные: O(1) для текущих переменных.

Задача о восьми ферзях – это тоже широко известная комбинаторная задача по расстановке фигур на шахматной доске. Основная формулировка это шахматной задачи звучит так, “Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого”.

Общее число возможных расположений 8 ферзей на 64-клеточной доске равно

А общее число возможных расположений, удовлетворяющих условию задачи – 92.

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

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

Спасибо, что заглянули!

Ссылка на репозиторий проекта:

Steam Profile:

Itch.io:

Instagram:

GitHub:

#игры #разработка #программирование #games #development #design #проекты #алгоритм #алгоритмы #история #python #комбинаторика #математика #искусственныйинтеллект