В том же году генерал Евдокимов был назначен начальником всей Терской области и, как войска, так и все округа, там расположенные, подчинились ему.
В 1856 году генерал Муравьев был смещен. Главнокомандующим Кавказской армией и наместником Кавказским был назначен князь Барятинский.
Состоя при ген. Евдокимове, я участвовал во всех бывших экспедициях, получая разные поручения, то как начальник всей кавалерии отряда, то как начальник отдельного отряда.
Наконец по настойчивой просьбе его я был назначен в 1857 г., 14 января, к общему удивлению, начальником Владикавказского военного округа, на место генерала Мищенко. Назначение мое на некоторое время было предметом различных суждений (между русскими).
Одни говорили, что я, начальствуя на родной земле, легко могу увлечься в пользу народных элементов, и виды правительства сильно пострадают и дело испортится надолго.
Другие же говорили, что я знаю край и народ лучше всякого другого, и потому начальство может требовать от меня более чем от незнающего ни края, ни народа.
Как бы то ни говорили, приказ состоялся, и я был очень рад своему назначению, давшему мне случай осуществить давнишние мои искренние желания: уничтожение обычаев, оставшихся в народе с варварских времен, разорявших их домашнее благосостояние, поддерживая постоянно вражду, вместо доброго согласия, от которого зависит народное счастье.
Кроме того, из мелких аулов я устроил большие аулы и где было возможно, заложил сады, завел в некоторых аулах школы для обучения чтению и письму. Вызвал из Одессы англичанина-фабриканта полевых машин, выписал несколько плугов. Одним словом, приложил все свои старания и способности чтобы хоть сколько-нибудь приучить народ пользоваться богатыми дарами природы, на которые ни один из начальствовавших русских не считал нужным обратить внимание народа, несмотря на то, что все высшее начальство на бумаге желало и даже требовало этого от них.
Здесь я помещаю копию письма графа Евдокимова к начальнику Главного Штаба ген. Милютину (ныне военный министр):
«Из писем моих и личных объяснений Вашему Превосходительству известно, что самою ненадежною и неустроенной частью на левом крыле был Военно-осетинский округ. Не далее как год тому назад в этом округе происходили народные волнения, а разбои на дорогах и в окрестностях Владикавказа были вещью' самою обыкновенною. В январе месяце нынешнего года заведование округом поручено полковнику Кундухову, и в течение семи месяцев энергичного и деятельного управления штаб-офицер этот успел восстановить в округе полный порядок и устройство. Разбои прекращены, народ предался мирным целевым занятиям, множество полезных мер введено для улучшения быта народного, и в настоящее время по справедливости я должен считать Военно-осетинский округ самою надежною и благоустроенною частью левого крыла. Желая вознаградить полезную службу полковника Кундухова и поощрить его к дальнейшей деятельности, я имею честь покорнейше просить ваше превосходительство не оставить особенным ходатайством перед главнокомандующим о производстве полковника Кундухова в генерал-майоры, согласно моему представлению.
