Javascript шлях коня дошкою NxN

БлогNot. Javascript: шлях коня дошкою NxN

Javascript: шлях коня дошкою NxN

Завдання відоме і класичне - обійти ходом шахового коня всі поля прямокутної дошки, не обов'язково розміру 8x8.

Наведений нижче скрипт використовує не зовсім звичайний підхід до визначення клітин, на які може сходити кінь - скрипт знаходить їх координати з рівняння "клітинного кола" x 2 +y 2 =5 , де x і y можуть приймати цілі значення від -2 до 2 включно крім нуля (див. nMovesCalculate в коді).

Розміри дошки вибирайте самі зі списку від 5 до 26 включно. Після вибору натисніть "Очистити", щоб створити дошку. Потім клацніть по клітці, з якої кінь починає свій шлях, і натисніть "Знайти". Скрипт покаже хід коня візуально на дошці та у текстовому вигляді під дошкою.

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

Чому такі розміри дощок?

• Для неквадартних дощок міняти програму ліньки, поміняйте самі пару рядків у коді, якщо потрібно;
• Верхній розмір = 26 просто тому, що скінчилися латинські літери. Якщо вигадати, як позначати поля далі (див. firstLetterCode в коді), можна без втрат часу отримати рішення для дощок великих розмірів;
• Нижній розмір = 5, тому що:

• якщо одна сторона дошки дорівнює 3, то інша повинна бути або 4 або не менше 7;
• якщо обидві сторони більше 3, то обхід коня можливий усім дошках, крім 4x4.

Кількість маршрутів коня для дошки 8x8 дорівнює значенню 19591828170979904, так що все показувати або виводити недоцільно :)

Для дощок 5x5 і 7x7 алгоритм гарантовано знайде повний шлях, мабуть, лише зкутового або центрального поля дошки (хоча може і з інших), на інших дошках повинен шукати будь-якого стартового поля. Уточнення – для деяких стартових полів можливі проблеми з дошками непарного розміру. :)

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

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

Повний вихідник скрипту:

Багато рішень завдання будь-якими мовами, тільки не JS і не з вибором розміру дошки :)

Завдання Knight's tour у "Вікі" (EN)

Завдання про хід коня у "Вікі" (RU)

А як запам'ятати маршрут коня дошкою 8x8?

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

Перші літери задають координати ходів: Алеє Осінь = А1; Цінними Дарами = С2; і т. д. У кожну строфу вставлено підказку, що допомагає не переплутати послідовність строф: ще ОДИН, ДВА вечора, дістаються ТРЬОМ і т.д.

---