Умен кон

Умен кон
или как да обиколим цялата шахматна дъска с рицар, като съм посетил всяка клетка само веднъж

Сигурно сте забелязали, че шахът е интересен не само като игра, но е и „бойно поле“ на множество пъзели и логически проблеми. Много от тях се основават на специален рицарски ход под формата на английската буква L. Класически пример е рицарският поход през цялата шахматна дъска, дошъл при нас от математически трактати от началото на 18 век. Проблемът е, че като се започне от горния ляв ъгъл на шахматната дъска, преминете рицаря, така че фигурата да е посещавала всяка от 64-те клетки на шахматната дъска веднъж и само веднъж. Едно от решенията на този проблем е предложено от J. C. Warnsdorff през 1823 г. Програмата по-долу предлага друго решение, основано на използването на рекурсия.

Най-големият проблем при решаването на този проблем е вземането на решение за формата на данните, т.е. как шахматната дъска ще се съхранява в компютъра. Може би най-естественото решение би било да представим шахматната дъска като двуизмерен масив от 8 х 8. Нека обаче го направим по различен начин. Използване на два едномерни масива ред [64] и col [64] за съхраняване, съответно, на броя редове и колони, които рицарят последователно преминава по дъската.

Рицарят в позиция (i, j) може при следващия си ход да се озове в клетките с координати (i-2, j + 1), (i-1, j + 2), (i + 1, j + 2), (i + 2, j + 1), (i + 2, j-1 ), (i + 1, j-2), (i-1, j-2), (i-2, j-1). Имайте предвид, че ако рицарят е близо до ръба на дъската, тогава някои ходове могат да накарат рицаря да се премести извън него, което, разбира се, е неприемливо. Осемте възможни движения на рицаря могат да бъдат дадени като два масива ktmov1 [] и ktmov2 [], както е показано в следващия кодов фрагмент. Въз основа на това, рицарят в позиция (i, j) може да се премести на позиция (i + ktmov [k], j + ktmov2 [k]), където k е всяка стойност от диапазона 0 - 7, избрана от условието рицарят да остане на дъската. Така че програмата, която реализира движението на рицаря в съответствие с горните условия, ще изглежда така: