ЗАДАЧА ПРО ХІД КОНЯ definition of ЗАДАЧА ПРО ХІД КОНЯ and synonyms of ЗАДАЧА ПРО ХІД КОНЯ (Ukrainian)

Матеріал з Вікіпедії – вільної енциклопедії

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

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

Кількість всіх замкнутих маршрутів коня (гамільтонових циклів) без урахування напряму обходу дорівнює 13 267 364 410 532 [1] (кількість замкнутих маршрутів з урахуванням спрямування вдвічі більше). У той же час завдання підрахунку всіх можливих незамкнених маршрутів є значно складнішим і не вирішене досі. Відомо, [2] що незамкнутих маршрутів вбирається у числа поєднань

.

Зміст

Методи вирішення

Метод Ейлера та Вандермонда

Метод Ейлера

Метод Ейлера полягає в тому, що спочатку кінь рухається довільним маршрутом, поки не вичерпає всі можливі ходи. Потім клітини, що залишилися непройденими, додаються у зроблений маршрут, після спеціальної перестановки його елементів.

Розглянемо як приклад наступний маршрут:

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 - координати поля на дошці. Очевидно, що в послідовності дробів, що відповідає ходам коня, різниця чисельників двох сусідніх дробів може бути тільки 1 або 2, при тому, що різниця їх знаменників становить відповідно 2 або 1. Крім того, чисельник і знаменник не можуть бути меншими за 1 і більше 8 .

Його метод знаходження відповідної послідовності аналогічний методу Ейлера, але дозволяє знаходити маршрути коня тільки для дошокпарноїрозмірності.

Рамковий метод Мунка та Колліні

Метод поділу на чверті Поліньяка та Роже

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

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

При обході дошки кінь слідує на те поле, з якого можна піти на мінімальну кількість ще не пройдених полів. Якщо таких полів кілька, то можна піти на будь-яке з них.

Примітні маршрути

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

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; і т.д.

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

---