Математическая шахматная задача

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Задача о восьми ферзях[править | править вики-текст]

Требуется расставить на шахматной доске 8 ферзей так, чтобы они не угрожали друг другу (то есть ни один ферзь не должен стоять на одной вертикали, горизонтали или диагонали с любым другим ферзём), и выяснить, сколькими способами можно это сделать. Э. Наук в 1850 году нашёл 92 такие позиции, а Джеймс Глейшер доказал (1874), что других решений нет. При любом решении один ферзь обязательно стоит на поле а4 или на симметричных ему полях а5, d8, e8, h5, h4, e1, d1. Позиций, которые не могут быть получены друг из друга поворотами и зеркальными отображениями, всего 12.

Задача может быть обобщена и на произвольные квадратные доски размером n×n. На всех досках при n>3 можно расставить n ферзей, которые не угрожают друг другу. Аналогично и для других фигур (ладей, слонов, коней, королей) можно поставить задачу о их максимальном числе, которое можно расставить на доске определённой размерности, когда они не угрожают друг другу. Ладей таким образом на обычной доске можно разместить 8 (что очевидно). Легко доказывается, что коней размещается 32 - на полях одного цвета, слонов - 14. Королей можно разместить 16. Эти задачи называются задачами о независимости шахматных фигур.

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

Задача обхода шахматной доски конём[править | править вики-текст]

Требуется, поставив коня на любое поле доски («первый ход»), последовательно пройти им все поля, не занимая ни одно из них дважды. Если после этого 65-м ходом конь может попасть на исходное поле, маршрут называется замкнутым. Наиболее простым алгоритмом решения данной задачи является правило Варнсдорфа - ход делается на то поле, с которого можно сделать наименьшее количество ходов. Если таких полей несколько, то выбирается любое. Однако этот алгоритм приводит к решению не всегда. Вероятность тупикового варианта зависит от выбора начального поля. Она минимальна при начале с углового поля и несколько больше, например, если начинать с поля с1.

Задача о неприкосновенном короле[править | править вики-текст]

У белых — король на с3 (с6, f6 или f3) и ферзь, у чёрных — король. Всегда ли белые могут, не двигая своего короля, дать мат? Решение удалось получить при помощи ЭВМ (А. Л. Брудно и И. Я. Ландау, 1969). Мат даётся не позднее 23-го хода при любом положении ферзя и чёрного короля.

При других положениях белого короля и свободном чёрном короле мат поставить нельзя.

Литература[править | править вики-текст]

  • Гарднер М., Матем. головоломки и развлечения, перевод с английского, М., 1971;
  • его же, Матем. досуги, перевод с английского, М., 1972;
  • его же, Матем. новеллы, перевод с английского, М., 1974;
  • Дьюдени Г., Кентерберийские головоломки, перевод с английского, М., 1979;
  • Гик Е. Я., Шахматы и математика, М., 1983.
  • Шахматы : энциклопедический словарь / гл. ред. А. Е. Карпов. — М.: Советская энциклопедия, 1990. — С. 238. — 624 с. — 100 000 экз. — ISBN 5-85270-005-3.