\documentclass[spec, och, labwork]{SCWorks}
\usepackage{preamble}

\begin{document}
\include{titlepage.tex}

\section*{Описание работы алгоритма}

В качестве рекурсивного алгоритма будет рассмотрена задача о ходе коня "---
задача о нахождении маршрута шахматного коня, проходящего через все поля доски
по одному разу.

Алгоритм нахождения данного пути можно описать следующим образом:
\begin{enumerate}
    \item Пометить текущую клетку;
    \item Если все клетки помечены, то закончить алгоритм, иначе перейти к шагу 3;
    \item
        Перейти в одну из возможных не помеченных клеток. Если невозможно
        совершить ни один ход, то снять метку с текущей клетки, вернуться в
        предыдущую клетку и перейти к шагу 1.
\end{enumerate}

\subsection*{Оценка сложности}

Так как из заданной клетки конь может перейти в 2-8 клеток, из которой он в
свою очередь так же может перейти в 2-7 других клеток и т.д. Такой путь
состоит из $n^2$ клеток. При этом доска также состоит из $n^2$ клеток.
Таким образом, сложность данного алгоритма составляет $O(n^{2n^2})$

\subsection*{Реализация на языке C++}

\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../../knights-tour.cpp}

\end{document}