Тривалий час бложик був поза ефіром через те, що я забув пере делегувати домен org.ua. Потім була дещо епічна історія з його відновленням. Зараз вже все добре, тому варто було б щось написати.
Тема виплила якось сама собою. Я інколи читаю деякі книжечки по С++ і розважаю мозок задачками деякими. Ніколи не вважав себе прогармістом, напевне, варто переключитися на щось інше. Власне, потроху переключаюся, але поки ще трошки пишу всякі такі примітивні задачки.
Сьогодні поговоримо про одну з таких – шахматна задача коня Евкліда. Приклад такої задачки описано Полом та Харві Дейтелами у своїй книжечці по с++. В чому суть задачі? Є шахматна дошка і кінь. Потрібно пройти конем всі клітинки дошки, побувавши на кожній лише один раз.
З чого почати? Ну, щоб краще уявити ситуацію, візьміть листок і спробуйте зробити максимум ходів, закреслюючи відвідані клітинки. Мені вдалося зробити близько 30 ходів. Гадаю, така кількість ходів – буде приблизно однаковою при старті з різних позицій та випадковій стратегій ходів. Ок, давайте напишемо програмку, яка буде генерувати ходи коня випадково. Доречі, про ходи – їх є 8 типів. Не думаю, що люди, які цікавляться на такому мінімальному рівні програмуванням не цікавилися ніколи шахматами.
Отож, буквою К позначимо коня на дошці, цифрами – можливі типи ходів. Сама дошка задається масивом board 8*8.
Окрім того, для опису типів ходів опишемо два одномірні вектори hor(horizontal) та ver(vertical), які заповнимо за наступним принципом – зміщення на клітинку – вправо – додатній елемент в hor-векторі, вліво – від’ємний елемент в hor-векторі, вверх – від’ємний елемент у ver-вектор та вниз – додатній у ver-вектор. Наприклад, хід типу 0 можна описати наступними значеннями – hor[0]=2, ver[0]=-1. За такою ж схемою в кінцевому вигляді вектори виглядатимуть: hor[2,1,-1,-2,-2,-1,1,2]; ver[-1,-2,-2,-1,1,2,2,1]. Окрім того, звісно ж, потрібно задати поточну позицію коня. На початку – дошка чиста (всі елементи board рівні 0). При відвідуванні якоїсь клітинки відмічаємо її як 1. При виконанні ходів потрібно виключати можливість виходу за дошку, та повернення на клітинку, де кінь вже був.
Оскільки на даному кроці виконання програми я змоделюю випадкові ходи (як у випадку ручного виконання на листочку), тоді програма просто генеруватиме якийсь один з 8 ходів доти, доки перевірка на те, чи він не виходить за межі дошки і чи це не хід на позицію, де кінь вже був не даватиме позитивний результат. В загальному ж ходи виконуватиметься доти, доки з поточної позиції буде доступний хоча б один хід, який відповідає заданим вимогам.
Код програми:
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <iomanip> #include <iostream> using namespace std; void clear(int k[], int n){ for (int i=0;i<n;i++) k[i]=0; } bool check (int k[], int n){ bool ans=false; int count=0; for (int i=0;i<n;i++){ if (k[i]==1) count++; } if (count==n) ans=true; return ans; } int main(int argc, char **argv) { int board[8][8]={{0}};//дошка int ver[8]={-1,-2,-2,-1,1,2,2,1}; //вбоки int hor[8]={2,1,-1,-2,-2,-1,1,2}; //вверх-вниз int type[8]={0};//типи ходів int curRow=6,curCol=6; board [curRow][curCol]=1; int moveNumber;//тип ходу int count=0;//кількість ходів while (!check(type,8)){ moveNumber=rand()%8; type[moveNumber]=1; cout<<"Number "<<moveNumber<<endl; if (((curRow+ver[moveNumber])<8)&&((curCol+hor[moveNumber])<8) &&((curRow+ver[moveNumber])>=0)&&((curCol+hor[moveNumber])>=0) &&board[curRow+ver[moveNumber]][curCol+hor[moveNumber]]!=1){ curRow+=ver[moveNumber]; curCol+=hor[moveNumber]; board [curRow][curCol]=1; clear (type,8); count++; } } for (int i=0;i<8;i++){ for (int j=0;j<8;j++){ if (board[i][j]==1) cout<<"*"; else cout<<"0"; } cout<<endl; } cout<<"Count of: "<<count; return 0; }
Програмка досить проста, тим більше, алгоритм я описав. Результат (3 запуски):
Як бачимо у всіх трьох спробах жодного разу не досягнуто успіху – 64 ходи. Оці табилчци з нулів та зірочок – вигляд дошки після останнього можливого ходу. То як же пройти всю дошку? В приведених трьох спробах – змінювалися лише два параметри – стартова позиція ходу – curRow та curCol в програмі. Зараз я вже і не згадаю, з яких точно стартових позицій запускалася програма, але в кожному наступному випадку обиралася менш доступна клітинка. В цьому і ключ.
Однозначно запопонувати якийсь ідеальний алгоритм важко, але логічно, що дошку варто обходит из пріоритетом на менш доступні позиції. Це так званий евристичний алгоритм – правильність рішення не доведена для всіх можливих випадків, хоча в більшості випадків результат достатній. Я щось багато пишу, тому проілюструю сказане:
Як бачите, з поточної позиції коня є 6 варіантів ходів. Цифрами в клітинках – це кількість позицій, з яких можна зробити хід на позицію з цифрою. Згідно обраної стратегії обираємо хід на найменш доступну клітинку.
Що ж, підсумуємо все і опишемо алгоритм для програми.
1. До попередньої програми додамо двомірний массив access 8*8 – матриця доступності ходів.
Початковий вигляд – внизу
2. Оскільки потрібно обирати найменш доступні ходи, то логічно – варто почати з однієї з крайнії клітинок. Для прикладу – [0][0].
3. Розраховуємо масив type[8] доступних ходів з поточної позиції коня. Доступний хід – це той, який не виходить за межі дошки і не веде на позицію, на якій ми вже були.
4. Визначаємо хід на найменш доступну позицію. Якщо таких ходів декілька, вибираємо останній.
5. Здійснюємо хід, вказуючи нову поточну позицію та позначаючи відвідану клітинку.
6. Перераховуємо таблицю доступності клітинок.
Виконання ходів виконується доти, доки в пункті №3 в масиві type[8] буде хоча б один доступний хід.
Код програми:
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <iomanip> #include <iostream> using namespace std; void clear(int k[], int n){ for (int i=0;i<n;i++) k[i]=0; } bool check (int k[], int n){ bool ans=false; int count=0; for (int i=0;i<n;i++){ if (k[i]==0) count++; } if (count==n) ans=true; //якщо всі ходи недоступні - повертаємо тру return ans; } int main(int argc, char **argv) { int board[8][8]={{0}};//дошка int ver[8]={-1,-2,-2,-1,1,2,2,1}; //вбоки int hor[8]={2,1,-1,-2,-2,-1,1,2}; //вверх-вниз int type[8]={1};//типи ходів - відмічатимемо доступні ходи int curRow=4,curCol=4; int minAccess=8;//мінімальна досутпність клітинки int minAccessIndex=0;//індекс мінімально доступного ходу board [curRow][curCol]=1; int access[8][8]={{2,3,4,4,4,4,3,2}, {3,4,6,6,6,6,4,3}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {3,4,6,6,6,6,4,3}, {2,3,4,4,4,4,3,2}}; int count=0;//кількість ходів while (!check(type,8)){ //визначаємо доступні типи ходів for (int i=0;i<8; i++){ if (((curRow+ver[i])<8)&&((curCol+hor[i])<8) &&((curRow+ver[i])>=0)&&((curCol+hor[i])>=0) &&board[curRow+ver[i]][curCol+hor[i]]!=1) type[i]=1;// позначаємо що тип ходу доступний else type[i]=0;//недоступний } if (!check(type,8)){ //якщо э ходи - проводимо алгоритм, нема - ыде на кынець ы цикл по вайл завершується //визначаємо найменшдоступний хід for (int i=0;i<8;i++){ if (type[i]==1){ if(access[curRow+ver[i]][curCol+hor[i]]<minAccess){ minAccessIndex=i; // визначаємо індекс найменшдоступного ходу minAccess=access[curRow+ver[i]][curCol+hor[i]]; } } } //переміщуємо коня в найменш доступну клітинку і позначаємо її відміченою curRow+=ver[minAccessIndex]; curCol+=hor[minAccessIndex]; board [curRow][curCol]=1; //занулення індексів доступності перед перерахунком for (int i=0;i<8;i++) for (int j=0;j<8;j++) access[i][j]=0; //переахунок індексів доступності клітинок for (int i=0;i<8;i++){ for (int j=0;j<8;j++){ for (int k=0;k<8;k++){//розрахунок типів ходів if ((board[i+ver[k]][j+hor[k]]==0)&& ((i+ver[k])>=0&&(i+ver[k])<8)&& ((j+hor[k])>=0&&(j+hor[k])<8)) access[i][j]++; } } } } cout<<endl<<"Indeksu dostypnuh hodiv: "; for (int m=0;m<8;m++) cout<<type[m]<<" "; cout<<endl<<endl; cout<<"Vubranuy tup hody: "<<minAccessIndex<<endl<<endl; for (int i=0;i<8;i++){ for (int j=0;j<8;j++){ if (board[i][j]==1) cout<<"* "; else cout<<"0 "; } cout<<" "; for (int n=0;n<8;n++) cout<<access[i][n]<<" "; cout<<endl; } cout<<endl<<"---------------------------------------"; minAccess=8;//відновлення максимальної доступності для наступних порівнянь count++; } cout<<endl<<"Count of: "<<count; return 0; }
Глянемо на результати?
На картинці приведено перших 5 та останніх 8 ходів (на картинці 9 через повторний друк останнього ходу). Як бачите, программа завершується коли массив доступних ходів містить лише нулі, які і описувалося у вимогах. Маємо всі 64 ходи. Задача розв’язана. Залишилось перевірити, чи зробить кінь всі 64 ходи з будь-якої клітинки. Очевидно, ні. Алгоритм потребує удосконалення. В четвертому пункті алгоритму я сказав, що якщо є декілька рівних за доступнісю ходів – вибираємо останній. Удосконалений алгоритм повинен враховувати, яка з двох однаково доступних клітинок при наступних ходах веде до менш доступних. Якось так:
З поточної позиції коня є 4 доступних ход и на 8 та 4 на 6. Із двох ходів 6 доступні два ходи 3, з інших двох – один з доступністю 2. Остання клітинка і є наша ціль. Отже, потрібно зробити хід на одну з двох сірих шісток. Програмна реалізація алгоритму очевидно проводиться через рекурсію. Справитеся самі?
Постовий: Шукаєте щоб такого цікавого почитати в мережі? Портал UA Review - завжди пише лише правду. Чесно.
Поделиться в соц. сетях
Адреса TrackBack
