Главная » Алгоритмы » Задача о ферзях

0

Найти способ расстановки 8 ферзей на доске 8×8 так, чтобы они не били друг друга. Данная задача решается методом перебора с помощью рекурсии. Прежде чем поставить на доску очередного ферзя, нужно проверить, не бьет ли его какой другой ферзь. Если мы будем каждый раз сканировать все воз­можные перемещения всех ферзей, то это достаточно неэффективно. Мож­но ускорить проверку, если обратить внимание на один факт. Ферзь, как известно, ходит во всех направлениях, по всем диагоналям, вертикалям и горизонталям. С вертикалями и горизонталями все понятно: если был хоть один ферзь с координатой X или Y такой, как у нашего ферзя, то данное поле бьется. Как быть с диагоналями? Если диагональ восходящая (/), то сумма X и Y для всех клеток диагонали одна. Если нисходящая (\), то раз­ность X — Y для всех клеток одинакова. Мы можем иметь некоторые мно­жества, обнуленные в начале вычисления:

1.    Множество X.

2.    Y.

3.    X+Y.

4.    X—Y.

Чтобы узнать, бьется ли данное поле каким-либо ферзем, мы должны про­верить клетки массивов (множеств) 1, 2, 3, 4. Для массива 1 это будет клет­ка с индексом X, для массива 2 — Y, для 3 — (X+Y), для 4 — (X—Y+8). Все эти клетки должны быть нулевыми. Если хоть одна клетка 1, то поле бьется. Если мы поставили ферзя в какую-то клетку, то в соответствующие ячейки множеств должны записать 1. Если отменили ход — должны восстановить старое значение ячеек. Массив 4 имеет добавочный индекс 8 потому, что X—Y не может быть меньше 0, а в языке С индексация массивов от 0. Если мы поставили последнего ферзя, то конец перебора и вывод результата. Так как мы имеем дело с частным вырожденным случаем, то вместо 4 множеств можно использовать 3, а координату X увеличивать пошагово. Это гаранти­рует нам, что не будет двух ферзей с одинаковой координатой X. Старые значения множеств можно также не сохранять и не восстанавливать, т. к. если мы поставили ферзя на клетку, то это гарантия того, что в соответст­вующих ячейках массивов были нули. Вы можете попробовать написать эту программу сами. Это довольно занятно. Можно попытаться получить все возможные размещения ферзей.

Я же хочу обратить внимание на некоторый аспект этой задачи примени­тельно к программированию шахмат. Допустим, нам нужно определить, бьется ли поле (X,Y) фигурами противника. Как это сделать? Существует множество способов, но, применительно к данному примеру мы рассмотрим один. Допустим, у нас есть 4 массива со значениями в ячейках, соответст­вующих дальнобойным фигурам противника. В реальной программе это может делаться пошагово. Поставили фигуру (сделан ход) — увеличили со­ответствующие ячейки на единицу, убрали — уменьшили. Если в первом массиве у нас не 0 в ячейке с индексом X, возможно, в этой вертикали есть ладья или ферзь. Мы должны просканировать два луча в обоих направлени­ях до первой фигуры. Если в третьем массиве в ячейке с индексом (X+Y) не 0, то, возможно, на восходящей (/) диагонали нас бьет ферзь или слон противника. Нужно тоже просканировать два луча. Приращение при по­строении линии известно сразу. Для пешек нужно просто проверить две соседние клетки по диагонали. Несколько сложнее с королем и конем. Проверять соседние 8 клеток, в надежде найти там короля противника, и еще 8, в надежде найти коня, как-то не хочется. Но об этом несколько позднее.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии