Обхід шахової дошки конем

1. Постановка задачі
2. алгоритм обходу
3. Приклад роботи програми
4. Перелік програм:

Ця цікава головоломка була запропонована математиком Ейлером. Завдання, на перший погляд, досить просте # 150; потрібно шаховим конем, які перебувають на довільній клітці шахової дошки, обійти всі інші клітини дошки, розмір якої також заданий довільно. При цьому на одну клітку можна походити тільки один раз.

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

Для вирішення цього завдання на комп'ютері необхідно розробити правила, відповідно до яких комп'ютер буде вибирати хід. В принципі, черговий хід можна вибирати випадковим чином.

Оригінальна правило, дає лінійний за часом алгоритм обходу дошки, було запропоновано Варнсдорф (Warnsdorff) в 1983 році. Я реалізувала його в своїй роботі.

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

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

Евристика завжди працює на дошках від 5x5 до 76x76 клітин, при великих розмірах дошки кінь може зайти в глухий кут. Крім того, що базується на правилі алгоритм не дає всіх можливих рішень (тобто шляхів коня): можна піти проти правила і все одно отримати задовольняє умові завдання обхід.

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

Крім цього, я хотіла б пояснити, як виконується хід. Ми вже говорили, що існує вісім можливих ходів. Всі вони закодовані цифрами від 0 до 7. На рис. показані всі можливі варіанти ходів.

Кожен хід можна уявити як переміщення на задану кількість клітин по горизонталі і по вертикалі. Наприклад, нульового ходу відповідає переміщення на дві клітини по горизонталі, і "-1" клітку по вертикалі (знак мінус вказує на напрямок переміщення).

Заповнення масиву доступності трохи складніше. Кожен його елемент відповідає клітці на дошці, але тут ми записуємо інформацію про те, з скількох клітин можна походити на задану. Наприклад, на клітину а1 можна походити з двох клітин (с2 і b3). Масив цей перед початком виконання завдання має наступний вигляд:

Приклад роботи програми

Діалог створення шахової дошки з конем, на якій ми вибираємо розмір поля, розмір клітини, положення коня і інші параметри. Так само можна завантажити зображення елементів дошки з файлів.

Створено поле 5х5, кінь стоїть в позиції 2х4. Тепер, коли поле вже створено, можна запустити алгоритм обходу дошки конем.

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

//// version 8 final recomment

// малюємо зображення коня в межах поля

g.drawImage (HorseImage, EventBoardHorseMovedelX, EventBoardHorseMovedelY, null);

* Створює фонове зображення шахівниці з щільного масиву світлих і темних клітин,

* Якщо зображення не иниц. (Null), то фон не малюється,

* Порядок розташування клітин "по рядково, через одну", яка перша осередок на поле перша визначається параметром.

* @param whiteCells Зображення світлої осередки (клітини).

* @param blackCells Зображення темної осередки (клітини).

* @param firstCellWhite якщо true - то перша клітина поля світла, якщо false - то темна

* @return true - фон намальований, false - фон не намальований, через те що ізобращенія НЕ иниц. або НЕ иниц. розміри дошки.

public boolean BoardFonCreate (BufferedImage whiteCells, BufferedImage blackCells, boolean firstCellWhite)

BoardFon = new BufferedImage (BoardSize, BoardSize, BufferedImage.TYPE_INT_RGB);

int kX = 0; /// координати "точки малювання"

boolean firstCell = firstCellWhite; /// прапор для першого осередку

Graphics Fon = BoardFon.createGraphics (); /// для малювання

Fon.clearRect (0, 0, BoardFon.getWidth (), BoardFon.getHeight ()); /// очищаємо

for (int j = 0; j

kX = 0; // новий рядок

for (int i = 0; i

// біла в разі якщо парна осередок і перша осередок біла

// біла в разі якщо непарна осередок і перша осередок чорна

Fon.drawImage (whiteCells, kX, kY, CellsSize, CellsSize, null);

Fon.drawImage (blackCells, kX, kY, CellsSize, CellsSize, null);

kX = kX + CellsSize; // пересуваємося в рядку вправо для малювання наступної комірки (клітини)

/// наступний рядок починається з протилежного кольору осередки

* Прапор того що по дошці перетягується кінь, за допомогою миші

* Початкові координати коня до перетягування, X по горізоталі (пікселі)

* Початкові координати коня до перетягування, Y по вертикалі (пікселі)

* Зміна координат, X по горізоталі (пікселі)

* Зміна координат, Y по вертикалі (пікселі)

* Координати миші при натисканні ЛКМ, в системі координат коня (JButton), X по горізоталі (пікселі)

* Координати миші при натисканні ЛКМ, в системі координат коня (JButton), Y по вертикалі (пікселі)

* Перепрорісовка панелі (дошки)

* Початкові координати при переміщенні стрілками,

* Перед першою частиною "Г" -образного ходу,

* Тобто позиція осередки по горизонталі (штуки, клітини).

* Початкові координати при переміщенні стрілками,

* Перед першою частиною "Г" -образного ходу,

* Тобто позиція осередки по вертикалі (штуки, клітини).

* Код клавіші яка була натиснута першою: "перша стрілка"

* Складова зміщення у першій частині "Г" -образного ходу

* (Довжина відрізка в клітинах -1)

final int firstPartG = 2;

* Напралении першої частини "Г" -образного ходу,

* Щоб друга частина була перпендикулярна першій (буква "Г"),

* True - вертикально. false - горизонтально.

* Код клавіші яка була натиснута другий: друга стрілка тобто після першої стрілка

* Складова зміщення у другій частині "Г" -образного ходу

* (Довжина відрізка в клітинах -1)

final int secondPartG = 1;

* Екземпляр Коня (належить дошці)

public clHorse Horse = null;

* Клас Кінь успадкованих від класу JButton, для подальшого розміщення на панелі тобто дошці.

* Зображення Коня не містить в класі, а береться з класу Дошки, а також беруться параметри і функції.

* (Класи Кінь та Дошка нероздільні зовсім).

class clHorse extends JButton

private static final long serialVersionUID = 1L;

* Конструктор за замовчуванням, инициализирует коня

this.setBounds (0, 0, CellsSize, CellsSize); /// поміщаємо коня на дошку (за замовчуванням)

this.addKeyListener (new KeyMoveListener ()); // додаємо слухача події натискання клавіш для коня

mouseMoveListener = new MouseMoveListener (); // слухач подій миші стосовно коню

* Конструктор ініціалізує коня з приміщенням його на певну позицію

* @param PosX номер клітини по горизонталі

* @param PosY номер клітини по вертикалі

clHorse (int PosX, int PosY)

this (); // викликаємо конструктор (за замовчуванням) коня

HorseMove (PosX, PosY); /// переносить коня в певне місце на дошці

* Позиція Коня по горизонталі, осередки: 0,1,2. CellsNumberX-1

* Позиція Коня по вертикалі, осередки: 0,1,2. CellsNumberY-1