1

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Зміст

Вступ

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

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

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

Висновок

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

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

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

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

Вступ

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

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

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

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

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

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

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

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

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

1 X * * * * * * * 1 X * * * * * * *

2 * * X * * * * * 2 * * X * * * * *

3 * * * * X * * * 3 * * * * X * * *

4 * X * * * * * * 4 * * * * * * X *

5 * * * * * * * * 5 * X * * * * * *

6 * * * * * * * * 6 * * * X * * * *

7 * * * * * * * * 7 * * * * * X * *

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

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

Арсак Ж. Программирование игр и головоломок: Пер. с франц. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 224с.

Майкл Маккелви. Visual Basic 4 (серия “Без проблем”.): Пер. с англ. - М.: БИНОМ. - 576с.: ил.

Потапкин А.В. Основы Visual Basic для пакета Microsoft Office: Практ. Пособие. - М.: ЭКОМ, 1996. - 256с.: ил.

Простое и сложное в программировании / Авт. предисл. Е.П. Велихов. - М.: Наука, 1988. - 176с., ил.

Реселман Боб, Писли Ричард и др. Использование Visual Basic 6.: Пер. с англ. - К., М., СПб.: Издательский дом “Вильямс”, 1999. - 608с.:ил. - Парал. тит. англ., уч.пос.

Додаток А

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



Додаток Б

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

Private Sub Form_Load()

frmAvtor.Visible = False

Call Rozstanovka

End Sub

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

Public Sub Rozstanovka()

Dim a(7, 7) As Integer

Dim i, j, coordI, coordJ As Integer

Dim KilkKorolev, mm, nn As Integer

Dim b As Boolean

Static kilk, col As Integer

KilkKorolev = 8 ' Задаємо кількість королев, яких потрібно розставити

col = -1 ' Номер колонки, з якої будемо починати розстановку

Do Until (kilk = KilkKorolev) Or (col = 7)

lblEkran.Height = Picture1(0).Height * 0.75 * KilkKorolev

'Обнуляємо матрицю і очищаємо форму

For i = 0 To 7

For j = 0 To 7

a(i, j) = 0

Label1(j).Caption = 8 - j

Label2(i).Caption = Chr(97 + i)

lblEkran.Caption = ""

'Встановлюмо колір клітинок: чорна або біла

If ((i + j) Mod 2) = 0 Then

Picture1(8 * i + j).BackColor = &H80000009

Picture1(8 * i + j).Picture = LoadPicture("")

Else: Picture1(8 * i + j).BackColor = &H80000008

Picture1(8 * i + j).Picture = LoadPicture("")

End If

Next j

Next i

kilk = 0 'Початкова кількість королев рівна 0

col = col + 1

b = True

For i = 0 To 7

For j = 0 To 7

If b = True Then

coordJ = col

coordI = 0

b = False

Else:

coordJ = i

coordI = j

End If

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

kilk = kilk + 1

a(coordI, coordJ) = 1

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

'по горизонталі

For mm = 0 To 7

If a(mm, coordJ) <> 1 Then a(mm, coordJ) = 2

Next mm

'по вертикалі

For nn = 0 To 7

If a(coordI, nn) <> 1 Then a(coordI, nn) = 2

Next nn

'вверх-вліво від поточної королеви

mm = coordI

nn = coordJ

Do Until (mm = 0) Or (nn = 0)

If mm - 1 <> -1 Then mm = mm - 1

If nn - 1 <> -1 Then nn = nn - 1

a(mm, nn) = 2

Loop

'вниз-вправо від поточної королеви

mm = coordI

nn = coordJ

Do Until (mm = 7) Or (nn = 7)

If mm + 1 <> 8 Then mm = mm + 1

If nn + 1 <> 8 Then nn = nn + 1

a(mm, nn) = 2

Loop

'вниз-вліво від поточної королеви

mm = coordI

nn = coordJ

Do Until (mm = 0) Or (nn = 7)

If mm - 1 <> -1 Then mm = mm - 1

If nn + 1 <> 8 Then nn = nn + 1

a(mm, nn) = 2

Loop

'вверх-вправо від поточної королеви

mm = coordI

nn = coordJ

Do Until (mm = 7) Or (nn = 0)

If mm + 1 <> 8 Then mm = mm + 1

If nn - 1 <> -1 Then nn = nn - 1

a(mm, nn) = 2

Loop

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

If ((coordI + coordJ) Mod 2) = 0 Then

Picture1(8 * coordI + coordJ).Picture =

LoadPicture("D:\VB6.0\Vb5.0\8 Королев\Koroleva-W.bmp")

Else:Picture1(8 * coordI + coordJ).Picture =

LoadPicture("D:\VB6.0\Vb5.0\8 Королев\Koroleva-B.bmp")

End If

'Вивід координат поточної королеви

lblEkran.Caption = lblEkran.Caption & CStr(kilk) & ". - " & CStr(Label2(coordJ)) &

CStr(Label1(coordI)) & vbCrLf

End If 'Кінець умови

Next j

Next i

Loop

End Sub

'Перехід від frmAvtor до frmQueen

Private Sub cmdOK_Click()

frmQueen.Enabled = True

frmAvtor.Visible = False

End Sub

'Інформація про автора

Private Sub cmdAvtor_Click()

frmAvtor.Visible = True

frmQueen.Enabled = False

End Sub

'Вихід

Private Sub cmdExit_Click()

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

End Sub

Додаток В

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

Размещено на Allbest.ru