Програма розміщення 8 королев на шаховій дошці

 

Зміст


Вступ

Розділ 1. Теоретичні основи розвязку задачі восьми королев

Розділ 2. Метод розвязку даної задачі

Розділ 3. Програмна реалізація задачі восьми королев

Висновок

Список використаної літератури

Додаток А. Блок-схема програми

Додаток Б. Лістинг програми

Додаток В. Екранна форма результаті


Вступ


На сьогодні існує велика кількість різноманітних мов програмування, кожна з яких має свої певні переваги та недоліки. В цьому розмаїтті не завжди легко зробити свій вибір на користь якоїсь певної мови програмування.

Для більшості завдань, що стають перед нами, ми просто не в змозі дозволити собі затрачати багато часу на досягнення поставленої мети. Саме тому слід вибрати для програмування Visual Basic. Він є достатньо простою обєктно-орієнтованою мовою програмування з широкими можливостями. Visual Basic забезпечує нам найпростіший шлях для створення програм в операційній системі Windows. Екранні форми та обєкти управління позбавляють нас від надмірних зусиль, повязаних з відображенням та поновленням вмісту вікна.

Застосування засобів програмування Visual Basic дозволяє нам досить легко створювати інтерфейси програм високого рівня на відміну від інших мов програмування. В звязку з цим значно більшу частину свого часу ми можемо приділити для написання коду програми, не турбуючись про її зовнішній вигляд.

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


Розділ 1. Теоретичні основи розвязку задачі восьми королев


Головною проблемою, що стоїть в основі мого курсового проекту є питання: чи можна розмістити 8 королев на шаховій дошці таким чином, щоб вони не били одна одну? Більш точніше - необхідно знайти всі способи розстановки восьми королев, в який ніякі дві королеви не стоять на одній вертикалі, горизонталі, або діагоналі.

Перед тим як перейти до вирішення основного завдання я хочу розповісти про історію вирішення даної задачі без допомоги ЕОМ. Дана задача була поставлена в 1848 році німецьким шахістом М. Беццелем. в червні 1850 року Ф. Наук опублікував 60 розвязків цієї задачі. Великому математику К. Гауссу вдалося знайти 72 розвязки. Однак незабаром його результат перевищив той самий Наук, який знайшов 92 розвязки. А в 1874 році англійський математик Д. Глешер довів, що більше розвязків не існує.

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

b c d e f g h a b c d e f g h

X 1 X

X 2 X

X 3 X

X 4 X

5 X

6 X

7 X

8

Рис.1.1 - Варіанти розміщення королев на дошці.

На рисунку 1.1 зображено дві спроби розв'язку задачі. На лівій дошці стоять 4 королеви. Всі поля рядка 6 ними уже блоковані, тому продовжувати далі немає сенсу. На правій дошці ми зуміли поставити 7 королев, але восьмий рядок уже блокований.

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


Розділ 2. Метод розвязку даної задачі


Тепер звернемося до методу розвязку поставленої перед нами задачі. Спочатку потрібно зазначити, що дві королеви не можуть знаходитися в одному рядку (горизонталі) і, оскільки, необхідно поставити вісім королев на вісім рядків, то в кожному рядку є одна королева.

Аналогічно, є тільки одна королева в кожному стовпчику. Чітко видно, що неможливо одночасно управляти розміщенням і по рядках, і по стовпчиках - саме цього і потребує задача.

Необхідно розміщати королеви на послідовних рядках, починаючи зверху.

Щоб почати, я поміщаю королеву в перший стовпчик на першому рядку. Тоді залишається розвязати меншу задачу: розмістити сім королев на семи останніх рядках шахової дошки, враховуючи, що королева стоїть на першому полі першого рядка. Я отримаю тоді всі розвязки з королевою 1 в стовчику 1 рядка 1. При цьому потрібно підсумувати кількість королев на шаховій дошці. Якщо ця кількість є меншою ніж 8, то умова даної задачі не виконується. Тоді я ставлю королеву 1 в стовчик 2 рядка 1 і тоді розвязую задачу уже з 7 королевами. Таким чином ми королеву 1 переміщуємо по стовпчиках рядка 1 до тих пір, поки не будуть розставлені усі 8 королев.

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

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

Однак королева, яку необхідно розмістити, бє деяку кількість полів, які вже не можна буде використовувати в майбутньому. Щоб це врахувати, потрібно записати значення 1 на всіх полях, які були раніше вільними, а тепер їх бє ця нова королева. Для здійснення даної операції потрібно два цикли для зайняття полів, які бє королева на тій же вертикалі і горизонталі, а також необхідно два інших цикла - для кожної з діагоналей, що проходять через дане поле.

Важливе значення має інформація про те, чи можна використовувати дане поле чи ні. Для цього необхідно вияснити, чи стоїть королева в цьому ж стовпчику, рядку і діагоналях, що проходять через дане поле.

Необхідно знати стан зайнятості стовпців, рядків і діагоналей. Вихід з даної ситуації можна знайти за допомогою чотирьох таблиць: одна - для стовпчиків, друга - для рядків, третя - для правих діагоналей і четверта - для лівих діагоналей. Для того, щоб взнати чи вільне дане поле, необхідно вияснити, чи вільні стовпчик, рядок та дві діагоналі, що проходять через нього.

Для того, щоб зайняти поле, необхідно відмітити, що його стовпчик, рядок і діагоналі зайняті. Для того, щоб звільнити це поле, необхідно відмітити, що вони вільні. Циклів більше немає.


Розділ 3. Програмна реалізація задачі восьми королев


Кожна програма, написана за допомогою засобів програмування Visual Basic, включає в себе дві частини:

  • зовнішню - інтерфейс програми;
  • внутрішню - код програми.

Опис реалізації зовнішньої частини.

Створюю новий проект, вибравши New Project (Новий проект) з меню File. У вікні властивостей замінюю встановлене по замовчуванню імя форми на frmQueen. Задаю властивість форми BorderStyle рівним 1-Fixed Single. Це означає, що під час виконання програми розмір форми не може змінюватися. Властивості Caption надаю значення 8 королев. Вказую, що MaxButton рівне False, тобто форма не може бути розгорнута/згорнута.

З панелі ToolBox вибираю PictureBox і встановлюю його розміри на формі. Отже, я створила першу клітинку щахової дошки. Оскільки шахова дошка складається з 8х8 (64) клітинок, то необхідно створити масив клітинок. Для цього першу створену клітинку копіюю у буфер, а потім вставляю з буфера. При цьому Visual Basic автоматично створює масив клітинок (в дужках вказується номер клітинки). Дану операцію повторюю 64 рази, тобто відповідно до числа клітинок на шаховій дошці.

Створюю масиви з міток Label1 і Label2, в яких будуть виводитися цифри та літери латинського алфавіту для позначення координат фігур на шаховій дошці. Також створюю мітку lblEkran, в якій будуть виводитися дані про порядок розташування королев і їх координати.

З панелі ToolBox вибираю CommandButton і встановлюю її на формі. Надаю їй назву - cmdAvtor. Це буде командна кнопка, при натисканні якої можна отримати інформацію про автора програми. Аналогічно створюю командну кнопку cmdExit, що означає вихід з програми.

До виконуваного файлу програми я приєдную особисту піктограму через власивість Icon. Цю піктограму я створюю за допомогою Microsoft Image Editor.

Залишається лише встановити розташування форми на екрані. Для цього властивості StartUpPosition надаю значення CenterScreen. Це означає, що форма при запуску програми буде зявлятися посередині екрану.

Опис коду програми.

Основою внутрішньої частини є процедура Rozstanovka. Насамперед потрібно встановити значення змінної KilkKorolev. Оскільки в нашій програмі потрібно розставити 8 королев, то значення цієї змінної також буде 8. Ставлю початкове значення стовпчика col = -1. Далі всю процедуру записую в цикл з передумовою: Do Until…Loop. Оператори всередині циклу виконуються до тих пір, поки умова хибна (іншими словами, поки умова не виконується). В моїй програмі умовою служать змінні kilk i col, тобто цикл виконується до тих пір, поки змінна kilk буде рівна KilkKorolev або номер стовпчика колонки буде рівний 7, тобто останньому. За допомогою властивості Height, я встановлюю висоту мітки lblEkran, в якій будуть виводитися дані про послідовність розташування королев та їх координати.

Потім я обнуляю матрицю і очищаю всі клітинки шахової дошки. Для цього використовую два цикли з ітераціями по і (0..7), то по j (0..7), які відповідають відповідно номеру рядку і номеру стовпчика. За допомогою цих циклів виводжу значення міток Label1(j).caption = (8 - j) - числа, що відповідають номеру стовпчика, а також Label2(i).caption = chr(97 + i) - букви латинського алфавіту, які відповідають номеру рядка. Функція Chr(97+i) повертає односимвольну стрічку, яка містить символ з ASCII-кодом (97+і), тобто a,b,c,…,f,h. Щоб очистити всі клітинки і встановити колір, я використовую умовний оператор If…Then…Else. Тобто, якщо сума (i+j) ділиться на 2 без остачі, то за допомогою властивості BackColor встановлюю колір клітинки чорний, в іншому випадку - білий.

Оскільки ще жодної королеви немає на дошці, тому kilk = 0, а колонка, з якої будемо розставляти королеви стає нульовою - col = col + 1. Одразу ж встановимо значення логічної змінної b = true, тому що ми збираємось поставити першу королеву. Якщо b = true, то зафіксуємо координати першої королеви: coordJ = col; coordI = 0, і замінемо значення b з true на false, тому що перша королева вже поставлена. Для всіх інших королев координати будуть такі: coordJ = i; coordI = j.

Далі потрібно перевірити чи вільна клітинка на шаховій дошці з цими координатами. Якщо так, то збільшуємо лічильник kilk на одиницю, а дану клітинку зафіксуємо, що вона вже занята. Аналогічно потрібно зафіксувати ті клітинки, які бє дана королева. Оскільки королева бє по горизонталі, по вертикалі і по діагоналях, то необхідно ці клітинки помітити. За допомогою двох циклів відмічаю клітинки по горизонталі і по вертикалі. Далі потрібно відмітити діагоналі, які проходять через дану королеву, тобто ті, які бє ця королева. Для цього використовую ще чотири цикли, за допомогою яких відмічаю ті клітинки діагоналей, які знаходяться по таких сторонах від поточної королеви:

  • вліво-вверх;
  • вправо-вниз;
  • вліво-вниз;
  • вправо-вверх.

Після цього необхідно представити королеву у графічному вигляді в клітинці. Дану королеву я розробила в Microsoft Image Editor і зберегла з розширенням.bmp. Оскільки існують чорні і білі клітинки, то я зберегла два файли, в одному з яких королева розташована на чорному фоні, в іншому - на білому і встановила розмір даних королев, що відповідають розміру клітинки на шаховій дошці. Щоб взнати, яку королеву ставити на дошці я використовую умовний оператор If…Then…Else, тобто якщо сума (coordI + coordJ) ділиться на два без остачі, то в клітинку ставлю чорну королеву, в іншому випадку - білу.

Ще залишається вивести в мітку lblEkran координати поточної королеви. Оскільки координати - це цілі числа, то їх необхідно перетворити в тип даних string. Для цього використовую функцію CStr(expression), яка перетворюю значення expression в тип даних string. В даному випадку замість expression відповідають значення coordI i coordJ. Тут я ще використовую спеціальну константу vbCrLf, якій відповідають два символи Chr(13) i Chr(10) (повернення каретки та зміна стрічки). Я використовую цю константу для зручнішого представлення даних у вигляді стовпчика.

шаховий visual basic програма


Висновок


Отже, по завершенню роботи над курсовим проектом можна зробити висновок про те, що мені вдалося досягти своєї мети і розвязати поставлену перед мною задачу розміщення восьми королев. Також за допомогою засобів Visual Basic мені вдалося належним чином без особливих зусиль оформити інтерфейс програми. З усього сказаного вище слідує, що мова програмування Visual Basic найкраще підходить для тих людей, які займаються розробкою різноманітних програм, логічних ігор, головоломок та програмуванням будь-якої іншої інформації, що потребує досконалого, легкого для сприйняття та розуміння візуального представлення.

Розробка даної програми дала мені змогу не лише підвищити рівень знань та практичних навичок у користуванні засобами програмування Visual Basic, а й розвинути логічне мислення та просторову уяву.

Мова програмування Visual Basic заставляє програміста не лише задумуватися над кінцевими результатами програми, але й примушує враховувати потреби та зручність користувача, легкість при використанні програми.


Список використаної літератури


  1. Арсак Ж. Программирование игр и головоломок: Пер. с франц. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 224с.
  2. Майкл Маккелви. Visual Basic 4 (серия Без проблем.): Пер. с англ. - М.: БИНОМ. - 576с.: ил.
  3. Потапкин А.В. Основы Visual Basic для пакета Microsoft Office: Практ. Пособие. - М.: ЭКОМ, 1996. - 256с.: ил.
  4. Простое и сложное в программировании / Авт. предисл. Е.П. Велихов. - М.: Наука, 1988. - 176с., ил.
  5. Реселман Боб, Писли Ричард и др. Использование Visual Basic 6.: Пер. с англ. - К., М., СПб.: Издательский дом Вильямс, 1999. - 608с.:ил. - Парал. тит. англ., уч.пос.

Додаток А


Блок-схема програми









Додаток Б


Лістинг програми

Sub Form_Load().Visible = FalseRozstanovkaSub


'Основна процедура

Sub Rozstanovka()a(7, 7) As Integeri, j, coordI, coordJ As IntegerKilkKorolev, mm, nn As Integerb As Booleankilk, col As Integer

= 8 ' Задаємо кількість королев, яких потрібно розставити= -1 ' Номер колонки, з якої будемо починати розстановку

Until (kilk = KilkKorolev) Or (col = 7).Height = Picture1(0).Height * 0.75 * KilkKorolev


'Обнуляємо матрицю і очищаємо формуi = 0 To 7j = 0 To 7(i, j) = 0

(j).Caption = 8 - j(i).Caption = Chr(97 + i).Caption = ""


'Встановлюмо колір клітинок: чорна або біла((i + j) Mod 2) = 0 Then(8 * i + j).BackColor = &H80000009(8 * i + j).Picture = LoadPicture(""): Picture1(8 * i + j).BackColor = &H80000008(8 * i + j).Picture = LoadPicture("")If

ji

= 0 'Початкова кількість королев рівна 0= col + 1 = True

i = 0 To 7j = 0 To 7b = True Then= col= 0= False:= i= jIf

a(coordI, coordJ) = 0 Then 'Початок умови= kilk + 1(coordI, coordJ) = 1


'Перевірка розташування

'по горизонталіmm = 0 To 7a(mm, coordJ) <> 1 Then a(mm, coordJ) = 2mm


'по вертикаліnn = 0 To 7a(coordI, nn) <> 1 Then a(coordI, nn) = 2nn


'вверх-вліво від поточної королеви= coordI= coordJUntil (mm = 0) Or (nn = 0)mm - 1 <> -1 Then mm = mm - 1nn - 1 <> -1 Then nn = nn - 1(mm, nn) = 2


'вниз-вправо від поточної королеви= coordI= coordJUntil (mm = 7) Or (nn = 7)mm + 1 <> 8 Then mm = mm + 1nn + 1 <> 8 Then nn = nn + 1(mm, nn) = 2


'вниз-вліво від поточної королеви = coordI= coordJUntil (mm = 0) Or (nn = 7)mm - 1 <> -1 Then mm = mm - 1nn + 1 <> 8 Then nn = nn + 1(mm, nn) = 2


'вверх-вправо від поточної королеви = coordI= coordJUntil (mm = 7) Or (nn = 0)mm + 1 <> 8 Then mm = mm + 1nn - 1 <> -1 Then nn = nn - 1(mm, nn) = 2


'Вивід королеви: чорної, або білої

((coordI + coordJ) Mod 2) = 0 Then(8 * coordI + coordJ).Picture =("D:\VB6.0\Vb5.0\8 Королев\Koroleva-W.bmp"):Picture1(8 * coordI + coordJ).Picture = ("D:\VB6.0\Vb5.0\8 Королев\Koroleva-B.bmp")If


'Вивід координат поточної королеви.Caption = lblEkran.Caption & CStr(kilk) & ". - " & CStr(Label2(coordJ)) &

CStr(Label1(coordI)) & vbCrLfIf 'Кінець умовиjiSub


'Перехід від frmAvtor до frmQueenSub cmdOK_Click().Enabled = True.Visible = FalseSub



'Інформація про автораSub cmdAvtor_Click().Visible = True .Enabled = FalseSub


'Вихід

Sub cmdExit_Click()'При натисненні кнопки Exit здійснюється вихід з програмиSub


Додаток В


Екранна форма результатів



Зміст Вступ Розділ 1. Теоретичні основи розвязку задачі восьми королев Розділ 2. Метод розвязку даної задачі Розділ 3. Програмна реалізація зада

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ