Шахи: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м виправлення посилання за допомогою AWB |
|||
Рядок 574:
{{See also|Комп'ютерні шахи|Шаховий рушій|Вирішення шахів}}
Структура і природа гри в шахи мають стосунок до кількох галузей математики. Багато питань [[Комбінаторика|комбінаторики]] і [[Топологія|топології]], пов'язаних з шахами, відомі впродовж сотень років.
Підраховуючи число можливих ходів фігури <math>x</math> з кожного поля дошки й додаючи ці числа, отримуємо загальне число ходів <math>S(x).</math> Ділячи <math>S(x)</math> на число полів, доступних фігурі, отримуємо <math>P(x)</math> - її рухомість.
Наприклад, задача обходу конем шахматної дошки є задачею [[Динамічне програмування|динамічного програмування]]. Нехай шлях складається з <math>L</math> шляхів на дошці розміром <math>N^{2}.</math> Тоді задача побудови шляхів довжиною <math>N^{2}</math> зводиться до задачі побудування шляху <math>N^{2}-L</math> кроків, тобто до задачі найменшого об'єму. Далі від кожного поля можлива побудова декількох гляхів, відповідно, для цих шляхів задача побудови шляху до поля є перекривуваною. Розрахунковий цикл задається лістингом:<syntaxhighlight>
num:=0
WHILE num<k DO
ПобудоваШляху(Хід[num], Довжина);
num:=num+1;
END;
</syntaxhighlight>Цей рекурсивний процес ніколи не закінчується, оскільки не вистачає глухих кутів, тобто ситуацій, у яких немає продовжень. Такі ситуації можуть бути двох типів: "глухий кут - рішення" та "глухий кут - відсутність ходу". Глухий кут, який є рішенням, співпадає із ситуацією <math>\text{Довжина}=N^{2}.</math><ref>{{Cite book|title=Виталий Потопахин - Искусство алгоритмизации.|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref>
=== Комбінаторика шахів і шахові головоломки ===
| |||