Восемь ферзей
Эта задача - одна из очень интересных шахматных головоломок.
Условие такое: можно ли поставить восемь ферзей на пустой доске таким образом, чтобы ни один из них не "атаковал" другого, т.е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски. Решение этой задачи, как вы понимаете, существует, причем не одно. На рис.1 я показал один из возможных вариантов расстановки ферзей.
| Ф | |||||||
| Ф | |||||||
| Ф | |||||||
| Ф | |||||||
| Ф | |||||||
| Ф | |||||||
| Ф | |||||||
| Ф |
Решение этой задачи на компьютере не представляет большой сложности. В принципе, можно тупо перебрать все возможные варианты расстановки ферзей на доске, а затем определить подходящие. Написать такую программу не сложно, но возникает вопрос: "Сколько существует вариантов и сколько времени нужно для их перебора?" Честно говоря, считать точное количество вариантов мне было лень, но, судя по всему, ждать придется долго.
Поэтому, нужно каким-то образом определить на какую клетку ставить следующего ферзя. Например, ставить несколько ферзей в одну линию бессмысленно (это противоречит условию). Если попробовать решить задача вручную, то становится понятно, что расставить 6 - 7 ферзей не сложно. Но после этого свободных клеток (которые не "бьются" ни одним из ферзей) нет. Следовательно, ферзей нужно расставлять так, чтобы они били как можно меньше клеток. Очень хорошо если несколько разных ферзей "бьют" одни и те же клетки, но при этом не "бьют" друг друга.
Дальше все очень просто. Нужно перебрать по очереди все свободные клетки доски (те, которые не "атакует" ни один ферзь) и посчитать, сколько свободных клеток "будет" бить ферзь из данной.
Подобные алгоритмы называются эвристическими и очень часто используются при разработке компьютерных игр. Эти алгоритмы обычно содержат условия, на основании которых компьютер может просчитать последствия того или иного хода (в данном случае, это количество клеток, которые будет "бить" ферзь), и выбрать лучший из них. Другие примеры программ, использующих эвристические алгоритмы вы можете посмотреть на сайте http://www.vova-prog.narod.ru/.
Для решения задачи нам понадобиться массив accessibility[8][8]. В нем мы будем хранить информацию о том, свободна данная клетка или нет. Таким образом, для того чтобы определить сколько клеток будет "бить" ферзь из заданной, нам нужно перемещать ферзя по всем возможным направлениям (их 8) и считать свободные клетки. Для перемещения ферзя удобно использовать два одномерных массива, элементы которых указывают на сколько клеток нужно сместить ферзя при движении в выбранном направлении. Я определил их таким образом:
const int vert[] = {0,-1,-1,-1,0,1,1,1};
const int hor[] = {1,1,0,-1,-1,-1,0,1};
Нулевой элемент соответствует перемещения вправо. Первый - по диагонали вправо и вверх, и т.д.
Для перемещения ферзя, например, на одну клетку вниз можно записать
x += hor[6]; y += vert[6];
Далее нужно выбрать клетку, которой соответствует наименьшее количество "выбитых" свободных клеток. Если таких клеток несколько, то выбираем одну из них случайным образом и ставим на неё ферзя (при этом нужно отметить в массиве accessibility, что соответствующие клетки заняты). Процесс повторяется до тех пор, пока не будут установлены все 8 ферзей.
На этом примере очень хорошо виден главный недостаток эвристического программирования - он не всегда позволяет решить задачу. Программа, работающая по данному алгоритму, находит решение примерно один раз из десяти. Этот результат, конечно, можно улучшить, если, например, выполнять анализ на несколько ходов вперед. Но, в любом случае, такая программа не сможет гарантировать решение, мы только увеличим вероятность его нахождения.
- Скачать программу (~223 Кб)
- Скачать исходники (~6,4kB)
