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

Листинг 3.11. Восемь ферзей. Поиск одного варианта 
void Queen(int i, out bool found) 
{ 
int j = 0;
do 
{ 
found = false; 
j++; 
if (NoHor[j] && NoRDiag[i+j] && NoLDiag[i-j]) 
{ 
PosQ[i] = j; // 
поставить ферзя 
NoHor[j] = false; 
NoLDiag[i - j] = false; 
NoRDiag[i + j] = false; 
if (i < Size) 
{ 
Queen(i + 1, out found); 
if (!found) 
{ 
PosQ[i] = 0; // 
убрать ферзя 
NoHor[j] = true; // 
линии свободны 
NoLDiag[i - j] = true; 
NoRDiag[i + j] = true; 
} 
} 
else
found = true; 
} 
19 / 23

---

66 
} 
while (!(found || (j == Size))); 
} 
В проекте, форма которого представлена на рисунке 3.5, реализован 
алгоритм бэктрекинга для данной задачи. На форме позиции ферзей 
отмечены символом ‘W’. 
Рис. 3.5. Форма проекта «Восемь ферзей». Реультат поиска 
единственного решения 
На форме размещены три элемента управления: 
− элемент dataGridView1; 
− кнопка «Одно решение»; 
− кнопка «Все решения». 
В листинге 3.12 представлен обработчик события клик по кнопке «Од-
но решение». После присваивания всем элементам булевских массивов зна-
чения false в нем производится вызов рекурсивной функции расстановки 
ферзей Queen. 
20 / 23

---

67 
Листинг 3.12. Восемь ферзей. Расстановка ферзей 
private void btnSet_Click(object sender,
EventArgs e) 
 
{ 
for (int i=1; i<=Size; i++) 
NoHor[i] = true; // 
горизонтали свободны 
for (int i = 2; i <= 2*Size; i++) 
NoRDiag[i]=true; //
все антидиагонали свободны 
for (int i =-Size+1; i <= Size-1; i++) 
NoLDiag[i]=true; // 
все диагонали свободны 
Queen(1, out ok); 
for (int k = 0; k < Size; k++) 
dgw[k, PosQ[k + 1] - 1].Value = 'W';
} 
Решение второго варианта задачи о расстановке ферзей – поиска всех 
возможных конфигураций гораздо проще (листинг 3.13). Оно сводится к реа-
лизации общей схемы алгоритма поиска с возвратом, представленной в лис-
тинге 3.13.