Курсова робота
Тема:
«гшення завдання про 8 ферзів В»
Харків 2007
Мета роботи: розробити програму, яка б наочно продемонструвала варіанти розміщення ферзів на шахівниці, задовольняючи правилам задачі.
Метод дослідження: вивчення літератури, складання і налагодження програм на комп'ютері, перевірка рішень.
Програма розміщення ферзів на практиці може застосовуватися в в освітніх цілях. Також її можна використовувати для вивчення математичної моделі поставленої задачі. Адже задача особливо цікава, при збільшенні розміру шахової дошки.
Завдання звучить наступним чином:
В«Якими способами можна розставити на дошці вісім ферзів так, щоб вони не загрожували один одному, тобто ніякі два не стояли на одній вертикалі, горизонталі та діагоналі і скільки таких способів? В»
Задача про восьми ферзя
Очевидно, більше восьми мирних ферзів (як і тур) на звичайній дошці розставити неможливо. Знайти якесь розташування восьми ферзів, не загрожують друг одному, легко (на малюнку представлені чотири шукані розстановки). Значно важче підрахувати загальне число розстановок і вивести їх, у чому, власне, і полягає завдання.
Цікаво, що багато авторів помилково приписували цю задачу і її рішення самому К. Гауссу. Насправді, вона була вперше поставлена ​​в 1848 р. німецьким шахістом М. Беццелем. Доктор Ф. Наук знайшов 60 рішень і опублікував їх у газеті В«Illustrierte ZeitungВ» від 1 червня 1850 Лише після цього Гаусс зацікавився завданням і знайшов 72 рішення, які він повідомив у листі до свого друга астроному Шумахеру від 2 Вересень 1850 Повний же набір рішень, що складається з 92 позицій, отримав все той же Ф. Наук. Він привів їх у згаданій газеті від 21 вересня 1850 Ця хронологія встановлена ​​відомим німецьким дослідником математичних розваг В. Аренс.
Суворе доказ того, що 92 рішення вичерпують всі можливості, було отримано лише в 1874 р. англійським математиком Д. Глешером (за допомогою теорії визначників). Забігаючи наперед, відзначимо, що суттєвих рішень (не співпадаючих при відображеннях і поворотах дошки) мається тільки дванадцять.
Відомо багато способів організувати ефективний пошук розташування восьми мирних ферзів (Методи Пермантье, Ла-Ное, Гюнтера, Глешера, Лакьера та ін.) Ці способи описані в численній літературі по цікавій математиці. У наше століття ЕОМ завдання такого сорту не викликала б настільки жвавий інтерес. Адже достатньо скласти нескладну програму, і вже через кілька хвилин після її введення в машину всі 92 необхідні позиції будуть видані на друк.
З кожного рішення задачі про ферзі можна отримати ряд інших за допомогою поворотів (Обертань) дошки на 90, 180 і 270 В°, а також при її дзеркальному відображенні щодо ліній, що розділяють дошку навпіл. Наприклад, з розстановки, показаної на рис. а, при повороті дошки на 90 В° за годинниковою стрілкою ми отримуємо розстановку на рис. в, а при відображенні дошки відносно лінії, що розділяє королівський та ферзевий фланги, - на рис. м. За допомогою інших поворотів і відображень дошки можна отримати ще п'ять рішень.
Отже, зазначені операції з шаховою дошкою дозволяють з одного розташування мирних ферзів отримати, взагалі кажучи, сім нових. Доведено, що в загальному випадку на дошці nхn (при n> 1) для будь розстановки n мирних ферзів можливі три ситуації:
1) при одному відображенні дошки виникає нова розстановка ферзів, а при поворотах та інших відображеннях нових рішень не виходить;
2) нове рішення виникає при повороті дошки на 90 В°, а її відображення дають ще дві розстановки;
3) три повороту дошки і чотири відображення приводять до семи різних розстановки (а якщо вважати і вихідну, то все маємо вісім позицій).
У разі 1) вихідне рішення називається двічі симметрическим, у разі 2) - симметрическим, а в разі 3) - простим. Для звичайної дошки кожне рішення є або простим, або симметрическим, а двічі симетричних не існує.
Набір розстановок восьми мирних ферзів називається основним, якщо, по-перше, ці розстановки не переходять один в одного при поворотах і відображеннях дошки, і, по-друге, будь-яка інша розстановка виходить з якоїсь основної при допомогою даних перетворень дошки. Доведено, що всякий основний набір рішень завдання містить рівно 12 розстановок. Ось один з таких наборів:
1) див. рис. а;
2) див. рис. б;
3) a4, b1, c5, d8, e6, f3, g7, h2;
4) a4, b2, c5, d8, e6, f1, g3, h7;
5) a4, b2, c7, d3, e6, f8, g1, h5;
6) a4, b2, c7, d3, e6, f8, g5, h1;
7) a3, b5, c2, d8, e6, f4, g7, h1;
8) a4, b1, c5, d8, e2, f7, g3, h6;
9) a4, b7, c3, d8, e2, f5, g1, h6;
10) a6, b4, c2, d8, e5, f7, g1, h3;
11) a4, b8, c1, d5, e7, f2, g6, h3;
12) a4, b2, c7, d5, e1, f8, g6, h3.
Інші 80 розстановок виходять із цих дванадцяти за допомогою поворотів і відображень дошки. Основна розстановка на рис. б є симетричної, інші одинадцять основних розстановок - простими. Отже, всього на дошці маємо 11.8 +1 В· 4 = 92 розстановки восьми ферзів, не загрожують один одному.
Відзначимо кілька цікавих властивостей розстановок мирних ферзів. Симетрична розстановка на рис. б як їй і належить, має зовнішньої симетрією. Вона характеризується також тим, що центральна частина дошки (квадрат 4х4) не зайнята ферзь. Вільні тут і обидві головні діагоналі дошки (цим властивістю володіє і восьма основна розстановка). У першій розстановці (рис. а) жодні три ферзя не знаходяться на одній прямій, проведеній через центри полів (маються на увазі не тільки вертикалі, горизонталі та діагоналі дошки, але і прямі з іншими кутами нахилу).
Всяке рішення задачі про вісім ферзів можна записати як набір (t1, t2, С?, t8), представляє собою перестановку чисел 1, 2, С?, 8. Тут ti - номер горизонталі, на якій стоїть ферзь i-й вертикалі. Так як ферзі не стоять на одній горизонталі, то всі числа ti різні, а оскільки ферзі не стоять і на одній діагоналі, то для будь-яких i, j (i
Запишемо числа 1, 2, С?, 8 спочатку за зростанням, а потім за спаданням. Після цього складемо числа кожної з цих двох перестановок з числами довільної перестановки восьми чисел, наприклад такий - (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8
+ 3, 7, 2, 8, 5, 1, 4, 6
4,9, 8, 7, 6, 5, 4, 3, 2, 1
+ 3, 7, 2, 8, 5, 1, 4, 6
11,14,8,13,9,4, 6, 7.
Отримані суми утворюють два набори: (4, 9, 5, 12, 10, 7, 11, 14) і (11, 14, 8, 13, 9, 4, 6, 7). Розглянемо наступну задачу.
Які перестановки чисел від 1 до 8 дають в результаті зазначеної операції додавання два таких набору, в кожному з яких всі елементи різні?
Задача про восьми ферзя привернула увагу Гаусса саме у зв'язку з цією чисто арифметичної завданням. Виявляється, між рішеннями цих двох завдань існує взаємно однозначна відповідність. Іншими словами, кожна розстановка восьми ферзів, не загрожують один одному, дає рішення арифметичної задачі, і навпаки. Для обраної перестановки обидва набори складаються з різних чисел, і це не випадково - вона відповідає першій основній розстановці (див. рис. а).
Неважко бачити, що при поворотах і відображеннях дошки одні рішення виходять з інших за допомогою простих арифметичних операцій над координатами полів, зайнятих ферзь. Аналіз цих операцій дозволяє виявити додаткові властивості рішень, які ми не станемо обговорювати.
Задача про n ферзь. На шаховій дошці nхn розставити n ферзів так, щоб вони не загрожували один одному.
На дошці 1х1 один ферзь ставиться на одне-єдине поле, і рішення існує. На дошці 2х2 один ферзь, де б не стояв, нападає на три інших поля, і другого ферзя поставити нікуди. На дошці 3х3 уміщаються тільки два мирних ферзя. Отже, для дощок 2х2 і 3х...
