На этом шаге мы рассмотрим алгоритм решения этой задачи.
Шахматная доска - это сетка размером 8x8 клеток. Ферзь - шахматная фигура, которая может перемещаться по шахматной доске на любое количество клеток по любой горизонтали, вертикали или диагонали. Если за один ход ферзь может переместиться на клетку, на которой стоит другая фигура, не перепрыгивая ни через какую другую фигуру, то ферзь атакует эту фигуру. (Другими словами, если фигура находится в зоне прямой видимости ферзя, то она подвергается атаке.) Задача восьми ферзей состоит в том, как разместить восемь ферзей на шахматной доске таким образом, чтобы ни один из них не атаковал другого (рисунок 1).
Рис.1. В решении задачи восьми ферзей (существует много решений) никакие два ферзя не могут угрожать друг другу
Чтобы представить клетки на шахматной доске, присвоим каждой из них два целых числа, обозначающих горизонталь и вертикаль. Мы можем гарантировать, что никакая пара из восьми ферзей не находится на одной вертикали, просто присвоив им последовательно номера вертикалей с первого по восьмой. Переменными в задаче с ограничениями могут быть просто вертикали рассматриваемых ферзей. Области определения могут быть допустимыми горизонталями, тоже с номерами с первого по восьмой. Ниже показан код, помещенный в конец нашего файла, где присвоены значения этим переменным и областям определения.
if __name__ == "__main__": columns: List[int] = [1, 2, 3, 4, 5, 6, 7, 8] rows: Dict[int, List[int]] = {} for column in columns: rows[column] = [1, 2, 3, 4, 5, 6, 7, 8] csp: CSP[int, int] = CSP(columns, rows)
Чтобы решить эту задачу, понадобится ограничение, которое проверяло бы, находятся ли любые два ферзя на одной горизонтали или диагонали. (Вначале всем им были присвоены разные номера вертикалей.) Проверка общей горизонтали тривиальна, но проверка общей диагонали требует небольшого применения математики. Если любые два ферзя находятся на одной диагонали, то разность между номерами их горизонталей будет равна разности между номерами их вертикалей. Заметили ли вы, где в QueensConstraint выполняются эти проверки? Обратите внимание на то, что следующий код расположен вверху исходного файла.
class QueensConstraint(Constraint[int, int]): def __init__(self, columns: List[int]) -> None: super().__init__(columns) self.columns: List[int] = columns def satisfied(self, assignment: Dict[int, int]) -> bool: # q1c = ферзь на 1-й вертикали, q1r = ферзь на 1-й горизонтали for q1c, q1r in assignment.items(): # q2c = ферзь на 2-й вертикали for q2c in range(q1c + 1, len(self.columns) + 1): if q2c in assignment: q2r: int = assignment[q2c] # q2r = ферзь на 2-й горизонтали if q1r == q2r: # тот же ряд? return False if abs(q1r - q2r) == abs(q1c - q2c): # одна диагональ? return False return True # нет конфликтов
Осталось только добавить ограничение и запустить поиск. Теперь вернемся в конец файла:
csp.add_constraint(QueensConstraint(columns))
solution: Optional[Dict[int, int]] = csp.backtracking_search()
if solution is None:
print("Решение не найдено!")
else:
print(solution)
Обратите внимание на то, что мы довольно легко приспособили схему решения задач с ограничениями, созданную для раскраски карты, к совершенно другому типу задач. В этом и заключается эффективность написания обобщенного кода! Алгоритмы должны быть реализованы настолько широко, насколько это возможно, если только не потребуется специализация для оптимизации производительности конкретного приложения.
Правильное решение присваивает каждому ферзю вертикаль и горизонталь:
{1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4}
На следующем шаге мы рассмотрим поиск слова.
