Панель администрирования библиотеки

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

python
def is_valid_move(x, y, visited):
    """
    Проверяет, что координаты (x, y) лежат в пределах доски и
    что клетка ещё не посещена.
    """
    if 0 <= x < 8 and 0 <= y < 8 and not visited[x][y]:
        return True
    return False

def solve_knight_tour(x, y, move_count, path, visited, moves):
    """
    Рекурсивная функция для поиска тура коня (knight's tour).
    
    x, y         - текущие координаты коня.
    move_count   - сколько клеток конь уже посетил (индекс в path).
    path         - список, в котором сохраняется маршрут обхода.
    visited      - двумерный массив (8x8), отмечающий посещённые клетки.
    moves        - все возможные ходы коня.
    
    Возвращает True, если найден полный маршрут обхода (64 хода),
    иначе False.
    """
    # Если конь уже посетил 64 клетки, тур завершён
    if move_count == 64:
        return True
    
    for dx, dy in moves:
        nx = x + dx
        ny = y + dy
        if is_valid_move(nx, ny, visited):
            visited[nx][ny] = True
            path[move_count] = (nx, ny)
            
            if solve_knight_tour(nx, ny, move_count + 1, path, visited, moves):
                return True
            
            # Откат (backtracking)
            visited[nx][ny] = False
    
    return False

def main():
    # Запрашиваем у пользователя стартовые координаты (1...8)
    # и приводим их к индексам (0...7)
    start_x = int(input("Введите номер строки стартовой позиции (1-8): ")) - 1
    start_y = int(input("Введите номер столбца стартовой позиции (1-8): ")) - 1
    
    # Проверка на допустимость координат
    if not (0 <= start_x < 8 and 0 <= start_y < 8):
        print("Координаты вне диапазона 1-8!")
        return
    
    # Список всех возможных ходов коня
    knight_moves = [
        (-2, -1), (-2, +1),
        (-1, -2), (-1, +2),
        (+1, -2), (+1, +2),
        (+2, -1), (+2, +1)
    ]
    
    # Массив посещённых клеток
    visited = [[False]*8 for _ in range(8)]
    visited[start_x][start_y] = True
    
    # Массив (список) для хранения пути (по порядку посещения)
    path = [None]*64
    path[0] = (start_x, start_y)
    
    # Пытаемся найти путь
    if solve_knight_tour(start_x, start_y, 1, path, visited, knight_moves):
        print("Найден маршрут обхода коня:")
        # Вывод пути, прибавляем 1 для перевода обратно в 1...8
        for step_num, (x, y) in enumerate(path, start=1):
            print(f"{step_num:2d}: ({x+1}, {y+1})")
    else:
        print("Маршрут найти не удалось (что крайне маловероятно для 8&times;8).")

if __name__ == "__main__":
    main()

Как работает программа

1. Ввод координат
   Пользователь вводит две координаты (строка и столбец) от 1 до 8, которые приводятся к диапазону 0–7 для удобства использования в списках Python.

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

   • visited – двумерный список (8×8), в котором True означает, что клетка уже посещена.
   • path – список из 64 элементов, куда последовательно записываются координаты клеток в порядке обхода.

3. Поиск в глубину (backtracking)
   Функция solve_knight_tour пытается сделать очередной ход коня в одно из восьми возможных направлений. Если ход допустим (не выходит за границы доски и не посещён ранее), то:

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

4. Успешное решение
   Когда move_count достигает 64, это означает, что все клетки доски посещены ровно по одному разу, и мы можем вывести путь.

Данный код на 8×8 доске обычно быстро находит решение из любой стартовой позиции.