Problem N hetmanów i propagacja ograniczeń
Umieszczać N hetmanów na planszy N×N, używając zbiorów kolumn i przekątnych do sprawdzania ograniczeń w czasie O(1), oraz omówić różnicę między zliczaniem a wyliczaniem rozwiązań
Problem N hetmanów i propagacja ograniczeń to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem N-Queens
Problem N-Queens (LeetCode 51/52) polega na umieszczeniu N hetmanów na szachownicy N×N w taki sposób, aby żadne dwa hetmany nie atakowały się wzajemnie. Hetmany atakują wzdłuż wierszy, kolumn oraz obu przekątnych. Dla N=4 istnieją dokładnie 2 rozwiązania. Dla N=8 (w wersji klasycznej) istnieją 92 rozwiązania. Jest to klasyczny problem backtrackingu z kontrolą ograniczeń, która znacznie ogranicza przestrzeń przeszukiwania.
# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)
# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)Umieszczanie jednego hetmana w każdym wierszu
Ponieważ dwa hetmany nie mogą znajdować się w tym samym wierszu, umieszczamy dokładnie jednego hetmana w każdym wierszu. Backtracking przechodzi rekurencyjnie przez kolejne wiersze, wybierając kolumnę dla każdego z nich. Zmniejsza to przestrzeń przeszukiwania z N² możliwości dla każdego hetmana do zaledwie N kolumn w każdym wierszu, co daje N^N początkowych gałęzi — jednak ograniczenia znacznie ją redukują. Głębokość rekurencji wynosi N (jeden poziom na wiersz), a współczynnik rozgałęzienia jest co najwyżej równy N.
def solve_n_queens(n):
results = []
queens = [] # queens[row] = column of queen in that row
def backtrack(row):
if row == n:
# Build the board representation
board = []
for r in range(n):
board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
results.append(board)
return
for col in range(n):
if is_valid(row, col):
queens.append(col) # CHOOSE
backtrack(row + 1) # EXPLORE
queens.pop() # UNCHOOSE
def is_valid(row, col):
for r, c in enumerate(queens):
if c == col: return False # same column
if abs(row - r) == abs(col - c): return False # diagonal
return True
backtrack(0)
return results
print(len(solve_n_queens(4)), 'solutions for N=4') # 2
print(len(solve_n_queens(8)), 'solutions for N=8') # 92Sprawdzanie ograniczeń w O(1) za pomocą zbiorów
Sprawdzanie poprawności przez skanowanie wszystkich umieszczonych hetmanów zajmuje O(N) dla każdego kandydata, co w najgorszym przypadku daje łączną złożoność O(N² × N!). Można zmniejszyć koszt każdego sprawdzenia poprawności do O(1), utrzymując trzy zbiory: cols (zajęte kolumny), diag (wartości row-col dla przekątnych biegnących z góry po lewej do dołu po prawej) oraz anti_diag (wartości row+col dla przekątnych biegnących z góry po prawej do dołu po lewej). Hetmany na tej samej przekątnej mają tę samą wartość row-col, a hetmany na tej samej przeciwprzekątnej mają tę samą wartość row+col.
def solve_n_queens_fast(n):
results = []
cols = set() # occupied columns
diag = set() # row - col (positive diagonal)
anti = set() # row + col (negative diagonal)
queens = []
def backtrack(row):
if row == n:
board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
results.append(board)
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue # PRUNE: constraint violated
# CHOOSE
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
backtrack(row + 1) # EXPLORE
# UNCHOOSE
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
backtrack(0)
return results
print(len(solve_n_queens_fast(8))) # 92Wyjaśnienie niezmiennika przekątnych
Kluczowa obserwacja dotycząca przekątnych: wszystkie pola na tej samej przekątnej biegnącej z góry po lewej do dołu po prawej mają tę samą wartość row - col. Na przykład (0,0), (1,1) i (2,2) mają row-col=0. Wszystkie pola na tej samej przeciwprzekątnej mają tę samą wartość row + col: (0,2), (1,1) i (2,0) mają row+col=2. Są to stałoczasowe niezmienniki, które pozwalają sprawdzać konflikty na przekątnych za pomocą wyszukiwania w zbiorze w czasie O(1), zamiast liniowego skanowania w czasie O(N).
# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
print([r-c for c in range(n)])
print('row+col values (same anti-diagonal):')
for r in range(n):
print([r+c for c in range(n)])
# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2) # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0) # both 2Zliczanie rozwiązań: N-Queens II
N-Queens II (LeetCode 52) wymaga tylko podania liczby rozwiązań, a nie plansz. Pozwala to na niewielką optymalizację: można pominąć konstruowanie planszy i jedynie zwiększać licznik. Zastosowanie masek bitowych zamiast zbiorów może dodatkowo przyspieszyć zliczanie do wartości bliskich O(1) na operację. Liczba rozwiązań rośnie niemonotonicznie: 1(N=1), 0(N=2), 0(N=3), 2(N=4), 10(N=5), 4(N=6), 40(N=7), 92(N=8).
def total_n_queens(n):
count = [0]
cols = set(); diag = set(); anti = set()
def backtrack(row):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue
cols.add(col); diag.add(row-col); anti.add(row+col)
backtrack(row + 1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col)
backtrack(0)
return count[0]
for n in range(1, 11):
print(f'N={n}: {total_n_queens(n)} solutions')N-Queens z maskami bitowymi dla większej szybkości
W przypadku bardzo dużych wartości N implementacja z maskami bitowymi działa znacznie szybciej. Należy użyć trzech liczb całkowitych jako masek bitowych: cols, left_diag (przesuwanej w lewo w każdym wierszu) oraz right_diag (przesuwanej w prawo w każdym wierszu). Dostępne kolumny to ((1<<n)-1) & ~(cols|left_diag|right_diag). Każdą dostępną kolumnę należy wyodrębnić za pomocą bit = available & -available (najmłodszy ustawiony bit), a następnie wywołać rekurencję. Zapewnia to sprawdzanie ograniczeń w czasie O(1) za pomocą operacji bitowych.
def total_n_queens_bitmask(n):
full = (1 << n) - 1 # all n columns set
count = [0]
def bt(cols, left_diag, right_diag):
if cols == full:
count[0] += 1
return
available = full & ~(cols | left_diag | right_diag)
while available:
bit = available & -available # lowest set bit
available &= available - 1 # remove lowest bit
bt(cols | bit,
(left_diag | bit) << 1,
(right_diag | bit) >> 1)
bt(0, 0, 0)
return count[0]
for n in range(1, 13):
print(f'N={n}: {total_n_queens_bitmask(n)}')Koncepcja propagacji ograniczeń
Propagacja ograniczeń wykracza poza proste przycinanie: po umieszczeniu hetmana należy natychmiast wywnioskować i wyeliminować wszystkie nieprawidłowe pozycje w kolejnych wierszach. Jest to bardziej agresywne podejście niż sprawdzanie poprawności przy każdym kandydacie — aktywnie zawężają Państwo przestrzeń wyszukiwania, zanim rozpocznie się rozgałęzianie. Najbardziej znanym przykładem jest spójność łukowa stosowana w solverach SAT i solverach Sudoku, gdzie umieszczenie jednej cyfry eliminuje możliwości w tym samym wierszu, kolumnie i polu 3×3.
# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further
# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
cols = set(q for q in queens)
diags = set(r - q for r, q in enumerate(queens))
anti_diags = set(r + q for r, q in enumerate(queens))
row = len(queens)
return [c for c in range(n)
if c not in cols
and (row-c) not in diags
and (row+c) not in anti_diags]
print(remaining_columns(8, [0])) # valid cols for row 1 after placing col 0 in row 0Solver Sudoku
Sudoku jest kanonicznym problemem propagacji ograniczeń. W każdej pustej komórce prawidłowymi kandydatami są cyfry, których nie ma jeszcze w tym samym wierszu, kolumnie ani polu 3×3. Solver wykorzystujący backtracking wykonuje następujące kroki: znajduje pierwszą pustą komórkę, próbuje każdej prawidłowej cyfry i wywołuje się rekurencyjnie. Gdy pojawi się sprzeczność (pusta komórka bez żadnej prawidłowej cyfry), następuje powrót. Dobre solvery Sudoku stosują również propagację ograniczeń (notatki ołówkowe) przed użyciem backtrackingu.
def solve_sudoku(board):
def is_valid(r, c, num):
for i in range(9):
if board[r][i] == num: return False # row
if board[i][c] == num: return False # col
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
if board[br+i][bc+j] == num: return False # box
return True
def backtrack():
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for d in '123456789':
if is_valid(r, c, d):
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False # no valid digit found
return True # no empty cells: solved
backtrack()
return board
# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')Heurystyka najbardziej ograniczonej zmiennej
Jest to kluczowa optymalizacja dla problemów spełniania ograniczeń: należy zawsze wybierać jako następną najbardziej ograniczoną zmienną (komórkę z najmniejszą liczbą prawidłowych możliwości). W Sudoku, jeśli jedna komórka ma tylko 1 prawidłową cyfrę, jej natychmiastowe uzupełnienie jest wymuszone — nie ma potrzeby wykonywania backtrackingu. Wybieranie takich komórek w pierwszej kolejności znacząco zmniejsza głębokość drzewa wyszukiwania. Jest to heurystyka Minimum Remaining Values (MRV) stosowana w programowaniu z ograniczeniami w dziedzinie sztucznej inteligencji.
def solve_sudoku_mrv(board):
'''Find cell with fewest valid choices (MRV heuristic).'''
def valid_choices(r, c):
nums = set('123456789')
for i in range(9):
nums.discard(board[r][i])
nums.discard(board[i][c])
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
nums.discard(board[br+i][bc+j])
return nums
def find_mrv():
best = (10, -1, -1, set()) # (choices_count, r, c, choices)
for r in range(9):
for c in range(9):
if board[r][c] == '.':
choices = valid_choices(r, c)
if len(choices) < best[0]:
best = (len(choices), r, c, choices)
return best[1], best[2], best[3]
def backtrack():
r, c, choices = find_mrv()
if r == -1: return True # no empty cells
for d in choices:
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False
backtrack()
return boardTabela liczby rozwiązań problemu N hetmanów
Liczba rozwiązań problemu N hetmanów tworzy następujący dobrze znany ciąg: N=1: 1, N=2: 0, N=3: 0, N=4: 2, N=5: 10, N=6: 4, N=7: 40, N=8: 92, N=9: 352, N=10: 724. Nie jest znany żaden wzór zamknięty, dlatego liczbę rozwiązań trzeba obliczać. Dla N=27 istnieje około 2.34 × 10^17 rozwiązań. Pytania rekrutacyjne zwykle dotyczą wartości N ≤ 9. Zrozumienie wykładniczego wzrostu wyjaśnia, dlaczego optymalizacja za pomocą masek bitowych ma znaczenie dla większych wartości N.
def count_queens(n):
'''O(1) per constraint check using sets.'''
count = [0]
cols = set(); diag = set(); anti = set()
def bt(row):
if row == n: count[0] += 1; return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col)
bt(row+1)
cols.discard(col); diag.discard(row-col); anti.discard(row+col)
bt(0)
return count[0]
sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]Konstrukcja planszy problemu N hetmanów
Gdy osoba przeprowadzająca rozmowę poprosi o zwrócenie rzeczywistych plansz (LeetCode 51), należy zbudować każdą planszę na podstawie listy queens, gdzie queens[r] oznacza kolumnę hetmana w wierszu r. Konstrukcja wiersza ma postać: '.' * col + 'Q' + '.' * (n - col - 1). Ta konstrukcja o złożoności O(n²) jest wywoływana tylko w liściach drzewa rekurencji (gdy wszystkie N hetmanów zostało umieszczonych), więc nie wpływa na ogólną złożoność.
def n_queens_boards(n):
results = []
queens = []
cols = set(); diag = set(); anti = set()
def build_board():
return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
def bt(row):
if row == n:
results.append(build_board())
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
bt(row+1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
bt(0)
return results
for board in n_queens_boards(4):
for row in board: print(row)
print()Szybki test
Sprawdź swoją wiedzę na temat koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: problem N hetmanów umieszcza po jednym hetmanie w każdym wierszu i używa zbiorów dla kolumn, przekątnych (row-col) oraz przekątnych przeciwbieżnych (row+col), aby sprawdzać ograniczenia w czasie O(1), maski bitowe dodatkowo przyspieszają sprawdzanie ograniczeń i pozwalają badać wszystkie ustawienia w czasie bliskim O(1) na operację, a propagacja ograniczeń (heurystyka MRV) ogranicza wyszukiwanie, zawsze wybierając w następnej kolejności najbardziej ograniczoną zmienną. Następnie porównamy podejścia zachłanne i DP oraz nauczymy się, kiedy stosować każde z nich.
Często zadawane pytania
Czy lekcja „Problem N hetmanów i propagacja ograniczeń” jest bezpłatna?
Tak — pełny tekst „Problem N hetmanów i propagacja ograniczeń” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Problem N hetmanów i propagacja ograniczeń”?
Umieszczać N hetmanów na planszy N×N, używając zbiorów kolumn i przekątnych do sprawdzania ograniczeń w czasie O(1), oraz omówić różnicę między zliczaniem a wyliczaniem rozwiązań Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Problem N hetmanów i propagacja ograniczeń”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Szablon backtrackingu: wybierz, zbadaj, cofnij wybór
- Podzbiory i zbiór potęgowy
- Permutacje i kombinacje
- Problem N hetmanów i propagacja ograniczeń