İki klassik tapmaca yaxşı budamanın nə qədər vacib olduğunu göstərir. Hər ikisi əvvəlki dərsdəki şablonu izləyir: seç, araşdır, ləğv et.

N vəzir

n x n lövhədə n vəziri elə yerləşdirin ki, heç biri eyni sətirdə, sütunda və ya diaqonalda olmasın. Hər sətirdə düz bir vəzir olur, ona görə sətirləri bir-bir doldurur və sütun seçirik. Konfliktləri üç çoxluqla O(1)-də yoxlayırıq:

  • cols: tutulmuş sütunlar;
  • diag1: row - col dəyərləri (bir istiqamətli diaqonallar);
  • diag2: row + col dəyərləri (digər istiqamət).
4×4 lövhədə dörd vəzirin bir həlli və sütun, diaqonal çoxluqları
4×4 lövhədə dörd vəzirin bir həlli və sütun, diaqonal çoxluqları

Eyni diaqonaldakı bütün xanaların row - col (və ya row + col) dəyəri eynidir, ona görə çoxluqda yoxlama kifayətdir.

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