Задание ходом шахматного коня

Идёт приём заявок

Подать заявку

Для учеников 1-11 классов и дошкольников

-Расположению фигуры коня в начальной позиции, правилам хода коня и взятия конём.

Учащиеся получат возможность научиться:

– достигать определённой клетки шахматной доски за минимальное число ходов ( дид. игра «Кратчайший путь»),

-достигать определённой клетки шахматной доски, не становясь на «заминированные» поля и на поля, находящиеся под ударом противника(дид. игра «Лабиринт», «Перехитри часовых») ,

-побить фигуры, расположенные на шахматной доске, уничтожая каждым ходом по фигуре противника (дид. игра «Один в поле воин»)

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

Материал : демонстрационные шахматы ,шахматы раздаточные, буквы Г, Т, К,Л.Ь, шаблон движения коня, магниты.

Раздаточный материал: , учебники И. Г. Сухина «Шахматы, первый год или там клетки чёрно-белые чудес и тайн полны», часть 1 , рабочие тетради И. Г. Сухина «Шахматы первый год или там клетки чёрно-белые чудес и тайн полны», часть 1, Обнинск, «Духовное возрождение», 2017.

-Загадка. Отгадайте загадку и догадайтесь, о ком пойдёт речь.

Скачет по полю красиво,

Разлетелась в беге грива,

Не догнать никак его,

Ржёт задорно: – Иго-го! (Конь).А. Измайлов

-Для чего нужны кони? Как люди заботятся об этих животных?

-Верно, а сегодня мы много узнаем про коня, не настоящего а … (шахматного)

Чтение одним из учащихся загадки про шахматного коня.

Он не цокает, конечно,

Но легко перешагнём…

Через ряд фигур и пешек

Этим шахматным … (конем) А.Хребтюков

-Что бы вы хотели узнать про эту фигуру?(нач. позицию, правила хода, взятия)

– Кто заметил в шахматной загадке что-нибудь необычное о том, как может двигаться конь.

-Кто-нибудь может пояснить, как ходит конь?

-Выберите из предложенных букв ту, на которую похоже движение коня.

Вывод : конь двигается буквой Г, может прыгать через фигуры.

Проверка шаблоном движения коня.

По силе 1 конь равен 3 пешкам. Обозначается заглавной буквой К.

-Кто назовет начальную позицию коней – белых и чёрных?

-Кто сможет назвать начальную позицию белых и чёрных коней, не глядя на доску?

Работа с учебником

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

Конь всегда прыгает с белого на черное, а с черного – на белое

– – Обратите внимание, как происходит взятие фигуры противника.

Работа с учебником

Задание 2. Стр.уч. 63 Решение шахматных задач. (№1-№6). Работа на шахматной доске: демонстрационной и раздаточной – решение одной из задач по выбору.

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

-Напомните, как происходит взятие фигур:

1.Работать надо одной рукой.

2.Когда взятие сначала берем фигуру противника

Задание 3. Стр. уч. 64 Решение шахматных задач. (№1-№6) дид. игра «Кратчайший путь» . Работа на демонстрационной шахматной доске: – решение одной из задач по выбору.

Задание 4. Стр. уч. 65 Решение шахматных задач. (№1-№6) дид. игра «Лабиринт». Работа на демонстрационной шахматной доске – решение одной из задач по выбору.

Задание 5. Стр. уч. 66 Решение шахматных задач. (№1-№6) дид. игра «Перехитри часовых» .Работа на демонстрационной шахматной доске – решение одной из задач по выбору.

Конь меня в дорогу ждет, (руки за спиной сцеплены в замок).

Бьет копытом у ворот, (ритмичные, поочередные поднимания согнутых в коленях ног).

На ветру играет гривой, (покачивания головой, затем наклоны в стороны).

Пышной, сказочно красивой.

Быстро я в седло вскочу, (подскоки)

Не поеду – полечу !

Работа в рабочей тетради.

-Стр.27 задания №1, №2, №3

-стр. 28 задание№4- запись ходов на доске и в тетради

Рефлексия: вспомним, что мы хотели выяснить сегодня про фигуру «коня»?

-что вы можете рассказать дома о том, что узнали на занятии?

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

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» [1] . В письме к Гольдбаху [2] он сообщал:

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

Содержание

Формулировка задачи [ править | править код ]

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

Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 [3] . Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

Методы решения [ править | править код ]

Метод Эйлера [ править | править код ]

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

Рассмотрим в качестве примера следующий маршрут:

55	58	29	40	27	44	19	22
60	39	56	43	30	21	26	45
57	54	59	28	41	18	23	20
38	51	42	31	8	25	46	17
53	32	37	a	47	16	9	24
50	3	52	33	36	7	12	15
1	34	5	48	b	14	c	10
4	49	2	35	6	11	d	13

Сначала попытаемся из незамкнутого маршрута сделать замкнутый. Для этого рассмотрим, куда можно пойти с полей 1 и 60. С поля 1 можно пойти на поля 2, 32 и 52, а с 60 — на 29, 51 и 59. В этих двух наборах есть поля, различающиеся на единицу, а именно — 51 и 52. Благодаря этому можно сделать маршрут замкнутым, обратив его часть. Для этого перенумеруем поля с 52 по 60 в обратном порядке. После этого у нас получается замкнутый маршрут:

57	54	29	40	27	44	19	22
52	39	56	43	30	21	26	45
55	58	53	28	41	18	23	20
38	51	42	31	8	25	46	17
59	32	37	a	47	16	9	24
50	3	60	33	36	7	12	15
1	34	5	48	b	14	c	10
4	49	2	35	6	11	d	13

Теперь можно включить в маршрут некоторые из непройденных клеток. Так как наш маршрут замкнутый, то его можно разорвать в произвольном месте и к одному из концов прицепить подходящую цепочку из непройденных клеток. Например, если разорвать цепочку в клетке 51 (перенумеровав клетки и сделав её последней, а 52 — первой), то сможем удлинить нашу цепочку на клетки a, b и d, которые станут клетками 61, 62 и 63.

Метод Вандермонда [ править | править код ]

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

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

Правило Варнсдорфа [ править | править код ]

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

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

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

Примечательные маршруты [ править | править код ]

Маршрут Яниша [ править | править код ]

50	11	24	63	14	37	26	35
23	62	51	12	25	34	15	38
10	49	64	21	40	13	36	27
61	22	9	52	33	28	39	16
48	7	60	1	20	41	54	29
59	4	45	8	53	32	17	42
6	47	2	57	44	19	30	55
3	58	5	46	31	56	43	18

Маршрут Яниша

Маршрут коня, найденный К. Я. Янишем, образует полумагический квадрат, а при повороте доски на 180° первая половина маршрута (номера с 1 до 32) переходит во вторую (номера с 33 по 64). Маршрута же, представляющего собой настоящий магический квадрат, не существует для доски 8 × 8 [5] .

Маршрут «Турка» [ править | править код ]

Шахматный автомат «Турок» демонстрировал замкнутый маршрут коня, изображенный на диаграмме справа.

Мнемоническое стихотворение [ править | править код ]

Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению: [6]

Алеет Осень Ценными Дарами,
Ещё Один Животворящий День.
Хлеба Червонят Желтыми Шнурами,
Хрустальных Вод Философична Сень.

Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Ещё Покрыта Флоксами Трава.

Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.

Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.

Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.

Фокстротами Шесть Девушек Пленились,
Эстрадных Танцев Фантастичней Па,
Едва Ступающий Цыпленок Вылез,
А Селезень Блуждающий Пропал.

Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.

Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.

Первые буквы задают координаты ходов:

Алеет Осень = А1; Ценными Дарами = С2; и т. д.

В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т. д.

Обобщение на произвольные доски [ править | править код ]

Замкнутые маршруты [ править | править код ]

Количество замкнутых маршрутов с учётом направления в два раза больше. Замкнутые маршруты существуют на досках n × n для всех чётных n ⩾ 6 (последовательность A001230 в OEIS).

Незамкнутые маршруты [ править | править код ]

Для неквадратных досок незамкнутый обход конём существует только при выполнении следующих условий: если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7; если же обе стороны больше 3, то обход коня возможен на всех досках, кроме 4 × 4. В частности, незамкнутые маршруты существуют на квадратных досках n × n для всех n ⩾ 5 . [7] Количество незамкнутых маршрутов на досках n × n образуют последовательность A165134 в OEIS.

Анимация прохождения коня через все клетки поля шахматной доски 5 x 5

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

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (Шаблон:Нет АИ 2). В письме к Гольдбаху он сообщал: Шаблон:Цитата

Формулировка задачи Править

Граф, соответствующий шахматной доске 8×8. Указанные степени вершин показывают количество различных ходов коня из соответствующих полей доски.

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

Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 [1] .

Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

Методы решения Править

Метод Эйлера Править

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

Рассмотрим в качестве примера следующий маршрут:

55	58	29	40	27	44	19	22
60	39	56	43	30	21	26	45
57	54	59	28	41	18	23	20
38	51	42	31	8	25	46	17
53	32	37	a	47	16	9	24
50	3	52	33	36	7	12	15
1	34	5	48	b	14	c	10
4	49	2	35	6	11	d	13

Сначала попытаемся из незамкнутого маршрута сделать замкнутый. Для этого рассмотрим, куда можно пойти с полей 1 и 60. С поля 1 можно пойти на поля 2, 32 и 52, а с 60 – на 29, 51 и 59. В этих двух наборах есть поля, различающиеся на единицу, а именно – 51 и 52. Благодаря этому можно сделать маршрут замкнутым, обратив его часть. Для этого перенумеруем поля с 52 по 60 в обратном порядке. После этого у нас получается замкнутый маршрут:

57	54	29	40	27	44	19	22
52	39	56	43	30	21	26	45
55	58	53	28	41	18	23	20
38	51	42	31	8	25	46	17
59	32	37	a	47	16	9	24
50	3	60	33	36	7	12	15
1	34	5	48	b	14	c	10
4	49	2	35	6	11	d	13

Теперь можно включить в маршрут некоторые из непройденных клеток. Так как наш маршрут замкнутый, то его можно разорвать в произвольном месте и к одному из концов прицепить подходящую цепочку из непройденных клеток. Например, если разорвать цепочку в клетке 51 (перенумеровав клетки и сделав её последней, а 52 – первой), то сможем удлинить нашу цепочку на клетки a, b и d, которые станут клетками 61, 62 и 63.

Метод Вандермонда Править

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

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

Правило Варнсдорфа Править

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

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

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

Примечательные маршруты Править

Маршрут Яниша Править

50	11	24	63	14	37	26	35
23	62	51	12	25	34	15	38
10	49	64	21	40	13	36	27
61	22	9	52	33	28	39	16
48	7	60	1	20	41	54	29
59	4	45	8	53	32	17	42
6	47	2	57	44	19	30	55
3	58	5	46	31	56	43	18

Маршрут коня, найденный К. Я. Янишем, образует полумагический квадрат, а при повороте доски на 180° первая половина маршрута (номера с 1 до 32) переходит во вторую (номера с 33 по 64).

Маршрут, найденный шахматным автоматом Править

Шахматный автомат нашёл замкнутый маршрут коня, изображенный на диаграмме справа.

Мнемоническое стихотворение Править

Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению: [3]

Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Еще Покрыта Флоксами Трава.

Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.

Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.

Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.

Фокстротами Шесть Девушек Пленились,
Эстрадных Танцев Фантастичней Па,
Едва Ступающий Цыпленок Вылез,
А Селезень Блуждающий Пропал.

Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.

Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.

Первые буквы задают координаты ходов:

Алеет Осень = А1; Ценными Дарами = С2; и т. д.

В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т.д.

Обобщение на произвольные доски Править

Замкнутые маршруты Править

Количество замкнутых маршрутов с учётом направления в два раза больше. Замкнутые маршруты существуют на досках $ n imes n $ для всех чётных $ ngeqslant 6 $ (Шаблон:OEIS).

Незамкнутые маршруты Править

Для неквадратных досок незамкнутый обход конём существует только при выполнении следующих условий: если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7; если же обе стороны больше 3, то обход коня возможен на всех досках, кроме 4×4. В частности, незамкнутые маршруты существуют на квадратных досках $ n imes n $ для всех $ ngeqslant 5 $ . [4] Количество незамкнутых маршрутов на досках $ n imes n $ образуют Шаблон:OEIS.

“>