Шахматные задачи от Поколения / forpes.ru

Главная
Шахматные задачи от Поколения

Шахматные задачи от Поколения

06.08.2024 08:36

tguev 15 6400 Источник

С 1966 года во всем мире 20 июля отмечают Международный день шахмат. В честь недавно прошедшего праздника мы решили написать статью о шахматных задачах из курсов "Поколение Python".

Так получилось, что шахматные задачи являются одной из главных визитных карточек наших курсов. Мы любим эти задачи потому, что они учат строить алгоритмы, находить закономерности, а также позволяют отточить работу с условными (if-else) и логическими (and и or) операторами.

В общем случае шахматные задачи имеют следующий вид:

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

У новичков часто возникают трудности с шахматными задачами. Поэтому в этой статье мы рассмотрим некоторые варианты решения каждой из них.

Шахматная доска

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

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

Ход ладьи ♖

Решаем задачу для ладьи. Шахматная ладья ходит по горизонтали или вертикали.

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

Приведенный ниже код решает поставленную задачу:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 == x2) or (y1 == y2):
    print('YES')
else:
    print('NO')

Несложно заметить, что условия x1 == x2 и y1 == y2 можно также записать в виде x1 - x2 == 0 и y1 - y2 == 0. Таким образом, одна из этих разностей должна быть равна нулю. Следовательно, условие (x1 == x2) or (y1 == y2) можно заменить на условие (x1 - x2) * (y1 - y2) == 0. Тогда код выше можно записать в таком виде:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - x2) * (y1 - y2) == 0:
    print('YES')
else:
    print('NO')

Ход короля ♔

Решаем задачу для короля. Шахматный король ходит по горизонтали, вертикали или диагонали, но только на 1 клетку.

Наиболее простое и прямое решение — это поочередная проверка 8 клеток.

Приведенный ниже код решает поставленную задачу:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if ((x1 - 1 == x2 and y1 + 1 == y2)
    or (x1 == x2 and y1 + 1 == y2)
    or (x1 + 1 == x2 and y1 + 1 == y2)
    or (x1 + 1 == x2 and y1 == y2)
    or (x1 + 1 == x2 and y1 - 1 == y2)
    or (x1 == x2 and y1 - 1 == y2)
    or (x1 - 1 == x2 and y1 - 1 == y2)
    or (x1 - 1 == x2 and y1 == y2)):
    print('YES')
else:
    print('NO')

Несложно заметить, что все проверки в данном решении по сути однотипны, меняются только сдвиги координат относительно начального положения короля. Выявив эту закономерность, можно составить список directions, содержащий пары из чисел -1, 0 и 1, которые описывают направления сдвига относительно короля:

значение -1 соответствует сдвигу на одну клетку влево по оси x или вниз по оси y
значение 1 соответствует сдвигу на одну клетку вправо по оси x или вверх по оси y
значение 0 соответствует отсутствию сдвига

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

С помощью данного списка и цикла for мы можем реализовать следующую проверку:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

directions = [(-1, +1), (0, +1), (+1, +1), (+1, 0), (+1, -1), (0, -1), (-1, -1), (-1, 0)]

for x0, y0 in directions:
    if (x1 + x0 == x2) and (y1 + y0 == y2):
        print('YES')
        break
else:
    print('NO')

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

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - 1 == x2 or x1 == x2 or x1 + 1 == x2) and \
    (y1 - 1 == y2 or y1 == y2 or y1 + 1 == y2):
    print('YES')
else:
    print('NO')

Используя встроенную функцию abs(), приведенный выше код можно переписать в таком виде:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if abs(x1 - x2) <= 1 and abs(y1 - y2) <= 1:
    print('YES')
else:
    print('NO')

Ход слона ♗

Решаем задачу для слона. Шахматный слон ходит по диагоналям.

При поиске закономерностей в координатах клеток диагоналей можно заметить, что условиеx1 - y1 == x2 - y2 соответствует одной диагонали, а условие x1 + y1 == x2 + y2 — другой диагонали. Так как слон ходит по обеим диагоналям, то следует использовать логический оператор or:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - y1 == x2 - y2) or (x1 + y1 == x2 + y2):
    print('YES')
else:
    print('NO')

Условия x1 - y1 == x2 - y2 и x1 + y1 == x2 + y2 можно записать в виде x1 - x2 == y1 - y2 и x1 - x2 == -(y1 - y2).

Так как из равенства модулей |a| = |b| следуют равенства a = b и a = -b, то используя встроенную функцию abs(), приведенный выше код можно переписать в таком виде:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if abs(x1 - x2) == abs(y1 - y2):
    print('YES')
else:
    print('NO')

Несложно заметить, что вместо модулей можно использовать и квадраты, ведь из равенства квадратов также следуют равенства a = b и a = -b:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - x2) ** 2 == (y1 - y2) ** 2:
    print('YES')
else:
    print('NO')

Ход ферзя ♕

Решаем задачу для ферзя. Шахматный ферзь ходит по диагонали, горизонтали или вертикали.

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

Приведенный ниже код решает поставленную задачу:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - x2) * (y1 - y2) == 0 or abs(x1 - x2) == abs(y1 - y2):
    print('YES')
else:
    print('NO')

Ход коня ♘

Решаем задачу для коня. Шахматный конь ходит буквой "Г".

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

Приведенный ниже код решает поставленную задачу:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if ((x1 - 2 == x2 and y1 + 1 == y2)
    or (x1 - 1 == x2 and y1 + 2 == y2)
    or (x1 + 1 == x2 and y1 + 2 == y2)
    or (x1 + 2 == x2 and y1 + 1 == y2)
    or (x1 + 2 == x2 and y1 - 1 == y2)
    or (x1 + 1 == x2 and y1 - 2 == y2)
    or (x1 - 1 == x2 and y1 - 2 == y2)
    or (x1 - 2 == x2 and y1 - 1 == y2)):
    print('YES')
else:
    print('NO')

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

С помощью данного списка и цикла for мы можем реализовать следующую проверку:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]

for x0, y0 in directions:
    if (x1 + x0 == x2) and (y1 + y0 == y2):
        print('YES')
        break
else:
    print('NO')

Однако, как и в задаче с королем, перебирать все 8 клеток нет никакого смысла. Можно заметить, что произведение разности соответствующих координат по модулю всегда равно 2, поэтому мы можем записать следующее условие:

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if abs((x1 - x2) * (y1 - y2)) == 2:
    print('YES')
else:
    print('NO')

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

x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - x2) ** 2 + (y1 - y2) ** 2 == 5:
    print('YES')
else:
    print('NO')

Расстояние между точками и вычисляется по формуле:

$\rho = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

Заключение

Шахматные задачи являются одним из лучших способов тренировки алгоритмического мышления для начинающих программистов. В статье мы рассмотрели различные варианты их решения.

Пишите в комментариях свои варианты, если они отличаются от наших.

Присоединяйтесь к нашему телеграм-каналу, будет интересно и познавательно!

❤️ Happy Pythoning! ?

Комментарии (15)

tonylenc
06.08.2024 08:51
#27132900
+5
Ход короля также можно решить через расстояние между клетками (теорему Пифагора):
```
x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= 2:
    print('YES')
else:
    print('NO')
```
Или более продвинуто через модуль разности соответствующих координат и отсортированный список:
```
x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if sorted([abs(x1 - x2), abs(y1 - y2)])[1] == 1:
    print('YES')
else:
    print('NO')
```
или через модуль разности соответствующих координат и сравнение с множеством:
```
x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())

if {abs(x1 - x2), abs(y1 - y2)} <= {0, 1}:
    print('YES')
else:
    print('NO')
```

Diversus
06.08.2024 08:51
#27133074
+9
Игра в шахматы - это неизбежная оптимизация по времени.

Думаю, что некоторые вещи лучше не пытаться как-то упростить. Наверное вот это (предположение):
```
x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())
if (x1 == x2) or (y1 == y2):    
  print('YES')
else:
  print('NO')
```
Лучше вот этого:
```
x1, y1, x2, y2 = int(input()), int(input()), int(input()), int(input())
if (x1 - x2) * (y1 - y2) == 0:
  print('YES')
else:
  print('NO')
```
По скорости работы. Возможно стоит об этом написать в статье.
1. tigreavecdesailes
  06.08.2024 08:51
  #27135258
  +3
  Безотносительно шахмат, это в целом очень плохой стиль программирования - без веской причины (оптимизация) заменять логическое выражение в терминах бизнес логики (и отсюда легко понятное человеку) на заковыристое выражение с эквивалентным результатом чтобы было меньше на пару строчек. А тут и строчек столько же и быстродействие хуже.
  1. ef_end_y
    06.08.2024 08:51
    #27136894
    +1
    Странно, что вас заминусовали. Возможно не поняли, что вы поддержали сообщение, на которое отвечаете
    
    tigreavecdesailes
    06.08.2024 08:51
    #27136936
    Наверное) Хотя у меня был коллега, который ради того чтобы уменьшить на пять строк делал goto в середину for цикла просто потому что там уже был нужный в данный момент код и гордился этим. Может он минуснул))
    
    ef_end_y
    06.08.2024 08:51
    #27139962
    Это фишка ассемблерных циклов. Так (прыжок в середину цикла) даже компилятор компилит
1. akakoychenko
  06.08.2024 08:51
  #27135536
  +4
  Шахматы вообще штука неочевидная. Как будто бы, каждая фигура сама за себя, и ООП просится с базовым классом Фигура (понятно, что перфа там не будет, но, это, если с упором на понятность писать), но, копнешь глубже, и нет, не сама за себя. И за возможность на проходе срубить пешку помнить надо, и за факт того, что король походил, и за то, не открываешь ли своего короля на шах ходом. То есть, приходим уже не к хождениям отдельных юнитов, а к стейту доски (включая переменные, скрытые в истории ходов, и невидимые на доске) и возможности изменить его в другой.
1. ef_end_y
  06.08.2024 08:51
  #27136906
  Переход на умножение это никакая не оптимизация - какая следующая фича будет запрошена? Правильно, проверять есть ли на пути другая фигура. В итоге "оптимизация" будет просто выкинутым временем

janatem
06.08.2024 08:51
#27134990
+11
В большинстве примеров содержится логическая ошибка — выдается ответ YES, когда начальное и конечное поле совпадают.
1. tonylenc
  06.08.2024 08:51
  #27135136
  +3
  Логической ошибки нет, потому что по условию задачи гарантируется, что подаются различные клетки шахматной доски:
  1. Akina
    06.08.2024 08:51
    #27135268
    +1
    Логической-то может и нет, а вот идеологическая присутствует.
    
    Любой ввод должен быть проверен. Особенно интерактивный.
    
    akakoychenko
    06.08.2024 08:51
    #27135538
    +2
    Тогда уж надо и границы доски проверять...
    
    Akina
    06.08.2024 08:51
    #27136838
    +1
    Да, обязательно. Это составная часть контроля входных данных. Переданные координаты не должны выходить за границы.
1. ef_end_y
  06.08.2024 08:51
  #27136908
  Это лучше проверять вне зависимости от фигуры чем для каждой фигуры дублировать код

tskdvraz0r

06.08.2024 08:51

#27135876

Слабоумие и отвага... но это не точно!

%%ipytest
import sys
import pytest
from loguru import logger

# Function
def chess_board(
    numbers: list[str | int],
    is_stdin: bool
) -> str:
    logger.debug(f"{numbers=}, {type(numbers)}")
    logger.debug(f"{is_stdin=}, {type(is_stdin)}")
    
    for value, value_type in zip(
            (numbers, is_stdin),
            (list, bool)
    ):
        if not isinstance(value, value_type):
            error_message: str = "Некорректный тип данных;"
            logger.error(error_message)
            raise TypeError(error_message)
    
    if is_stdin:
        try:
            logger.info("Преобразование типов элементов списка из str в int;")
            numbers: list[int] = [int(x) for x in numbers]
        except ValueError:
            error_message: str = f"Некорректное значение. Невозможно преобразовать {x=} в int;"
            logger.error(error_message)
            raise ValueError(error_message)
    else:
        logger.info("Проверка типов элементов списка;")
        if not all(isinstance(x, int) for x in numbers):
            error_message: str = "Некорректный тип данных элемента;"
            logger.error(error_message)
            raise TypeError(error_message)
    
    return "YES" if sum(numbers) % 2 == 0 else "NO"

@pytest.mark.parametrize(
    ["test_numbers", "test_is_stdin", "expected_result"],
    [
        # Good cases
        ([1, 1, 2, 6], False, "YES"),
        ([2, 2, 2, 5], False, "NO"),
        ([2, 3, 8, 8], False, "NO"),
        (["1\n", "1\n", "2\n", "6"], True, "YES"),
        (["2\n", "2\n", "2\n", "5"], True, "NO"),
        (["2\n", "3\n", "8\n", "8"], True, "NO"),
        
        # Error cases
        ("1 2 3 4", False, TypeError),
        ((1, 2, 3, 4), False, TypeError),
        (1234, False, TypeError)
    ]
)
def test_chess_board(
        test_numbers: list[str | int],
        test_is_stdin: bool,
        expected_result: str
) -> None:
    if test_numbers in ["1 2 3 4", (1, 2, 3, 4), 1234]:
        with pytest.raises(expected_exception=TypeError):
            chess_board(
                numbers=test_numbers,
                is_stdin=test_is_stdin
            )
    
    else:
        assert chess_board(
            numbers=test_numbers,
            is_stdin=test_is_stdin
        ) == expected_result

# Main Program
if __name__ == '__main__':
    try:
        logger.info("Вызов функции 'chess_board';")
        print(
            chess_board(
                numbers=[1, 2, 3, 4],
                is_stdin=False
            )
        )
        logger.info("Успешное завершение функции 'chess_board';")

    except Exception as err:
        logger.error("Ошибка выполнения функции 'chess_board';")