Эта задача – одна из очень интересных шахматных головоломок. Условие такое: можно ли поставить восемь ферзей на пустой доске таким образом, чтобы ни один из них не "атаковал" другого, т. е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски. Решение этой задачи, как вы понимаете, существует, причём не одно. На рис.1 я показал один из возможных вариантов расстановки ферзей.
| Ф |
| Ф |
| Ф |
| Ф |
| Ф |
| Ф |
| Ф |
| Ф |
Рис.1 Решение этой задачи на компьютере не представляет большой сложности. В принципе, можно тупо перебрать все возможные варианты расстановки ферзей на доске, а затем определить подходящие. Написать такую программу не сложно, но возникает вопрос: "Сколько существует вариантов и сколько времени нужно для их перебора?" Честно говоря, считать точное количество вариантов мне было лень, но, судя по всему, ждать придется долго. Поэтому, нужно каким-то образом определить на какую клетку ставить следующего ферзя. Например, ставить несколько ферзей в одну линию бессмысленно (это противоречит условию). Если попробовать решить задача вручную, то становится понятно, что расставить 6 – 7 ферзей не сложно. Но после этого свободных клеток (которые не "бьются" ни одним из ферзей) нет. Следовательно, ферзей нужно расставлять так, чтобы они били как можно меньше клеток. Очень хорошо если несколько разных ферзей "бьют" одни и те же клетки, но при этом не "бьют" друг друга. Дальше все очень просто. Нужно перебрать по очереди все свободные клетки доски (те, которые не "атакует" ни один ферзь) и посчитать, сколько свободных клеток "будет" бить ферзь из данной. Для решения задачи нам понадобиться массив accessibility[8][8]. В нем мы будем хранить информацию о том, свободна данная клетка или нет. Таким образом, для того чтобы определить сколько клеток будет "бить" ферзь из заданной, нам нужно перемещать ферзя по всем возможным направлениям (их восемь) и считать свободные клетки. Для перемещения ферзя удобно использовать два одномерных массива, элементы которых указывают на сколько клеток нужно сместить ферзя при движении в выбранном направлении. Я определил их таким образом: