Две классические головоломки показывают, как много значат хорошие отсечения. Обе следуют шаблону из прошлого урока: выбрать, исследовать, отменить.

N ферзей

Расставьте n ферзей на доске n x n так, чтобы никакие два не стояли в одной строке, колонке или диагонали. В каждой строке ровно один ферзь, поэтому заполняем строки по одной и выбираем колонку. Конфликты проверяем за O(1) тремя множествами:

  • cols: занятые колонки;
  • diag1: значения row - col (диагонали одного направления);
  • diag2: значения row + col (диагонали другого направления).
Доска 4×4 с одним решением задачи о четырёх ферзях и множествами колонок и диагоналей
Доска 4×4 с одним решением задачи о четырёх ферзях и множествами колонок и диагоналей

У всех клеток одной диагонали одинаковое row - col (или row + col), поэтому хватает проверки в множестве.

python
def solve_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    placement, solutions = [], []