Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.10. Схема алгоритма с возвратом 
void Attemt(int i, bool hit) 
{ 
int k = 0; 
do 
{ 
//
выбор k-ого возможного хода 
if(hit) 
{ 
//
обработка хода; 
if(i < n) Attemt(i+1, hit); 
if( !hit ) 
вернуться назад; 
} 
} while(!hit && (k < m); 
} 
Эта схема предполагает, что на каждом шаге существует некоторое 
фиксированное число путей m, а глубина рекурсии ограничена значением n. 
В конкретных программах эта схема может воплощаться различными спосо-
бами. 
3.4.1. Р
АССТАНОВКА ФЕРЗЕЙ
 
Это классическая задача, на которой обычно демонстрируют примене-
ние метода проб и ошибок и алгоритмов бэктрекинга. Она известна как зада-
ча о восьми ферзях и формулируется следующим образом: нужно расставить 
16 / 23

---

63 
восемь ферзей на шахматной доске размером 8×8 таким образом, чтобы ни 
один ферзь не угрожал другому, т. е. чтобы ни на одной из горизонталей, вер-
тикалей или диагоналей не находилось два или более ферзей. Задача в такой 
формулировке была впервые предложена в 1848 г. немецким шахматистом 
М. Беццелем. Ее решением занимались многие математики, в том числе 
К.Ф. Гаусс, который в 1850 году опубликовал 72 варианта такой расстановки. 
Исследуем две постановки этой задачи: 
− найти некоторое решение; 
− найти все возможные решения, то есть все правильные варианты 
расстановки ферзей. 
Для решения первого варианта задачи воспользуемся рекурсивной схе-
мой, приведенной в листинге 3.10: 
void Attemt(int i, out bool found) 
{ 
// 
инициализировать выбор позиции для i-ого фер-
зя; 
do 
{ 
found = false; 
// 
выбор позиции i-ого ферзя 
if(
выбрана позиция k) 
{ 
// 
поставить ферзя; 
if(i < 8)
Attemt(i+1, out found); 
if(!found)
// 
снять ферзя; 
else 
found = true; 
} 
} while(!found && (k < 8); 
} 
17 / 23

---

64 
Прежде всего, необходимо выбрать способ представления шахматной 
доски в памяти компьютера. Использование в таком качестве двумерного 
массива связано с необходимостью при выборе позиции для очередного фер-
зя проверять, свободны ли соответствующие диагонали и горизонталь. Это в 
значительной степени усложнит решение. Поскольку позиции ферзей зада-
ются номерами соответствующих горизонталей и вертикалей, то их можно 
хранить в одномерном массиве, используя в качестве индекса номер вертика-
ли, а в качестве значения – номер горизонтали. Для проверки возможности 
размещения ферзя в некоторой позиции выбранной вертикали необходимо 
иметь информацию о занятости горизонтали и двух диагоналей, проходящих 
через эту позицию. С этой целью объявим три дополнительных булевских 
одномерных массива, в элементы которых будут записываться значения 
true
или false в зависимости от состояния занятости соответствующей 
горизонтали или диагонали. Будем использовать для обозначения размера 
шахматной доски константу Size. Тогда число диагоналей каждого вида 
(параллельных главной и побочной диагонали соответственно) будет равно 
2×Size+1.
Каждая из диагоналей, параллельных главной диагонали, может 
характеризоваться значением разности координат i–j, постоянной для всех 
ее элементов. Аналогично, в пределах каждой из диагоналей, параллельных 
побочной, постоянна сумма i+j координат ее элементов. С учетом перечис-
ленных обстоятельств массивы, используемые для представления шахматной 
доски, опишем следующим образом: 
const int Size = 8; 
// 
размер шахматной доски 
// 
позиция ферзя на вертикали 
RangeArray PosQ = new RangeArray(1, Size);
// 
отсутствие ферзя на горизонтали 
RangeArrayBool NoHor = new RangeArrayBool(1, Size); 
// 
отсутствие ферзя на антидиагонали 
RangeArrayBool NoRDiag = new RangeArrayBool(2, 
2*Size); 
// 
отсутствие ферзя на диагонали 
RangeArrayBool NoLDiag = new RangeArrayBool(-Size+1, 
Size-1); 
Необходимо предусмотреть выход из рекурсии после успешного раз-
мещения последнего из ферзей. Поэтому в число параметров рекурсивной 
функции расстановки ферзей необходимо включить параметр, фиксирующий 
факт обнаружения решения. Данная функция представлена в листинге 3.11. 
18 / 23

---

65