It's a lot of options.

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 25 · page 25.2
It's a lot of options.
When a problem has no smart solution, we cross all options by cutting it off.
Review of options
- It's a universal method: try every combination you can and choose the best.
GEF
PIF
EGE No. 12
01
Types of combined objects
Object
Formula
Example
Spaces without repetition
A(n,k) = n! / (n-k)!
Sit down 3 out of 5
Relocations
P(n) = n!
Settle all 5
Combinations without repetition
C(n,k) = n! / (k!(n-k)!)
Select Team 3 out of 5
Recurring locations
n
k
4 digit password
Combinations with Repeats
C(n+k-1, k)
Place the balls in boxes
02
Backtracking — Return Search
Backtracking
- A over-the-counter algorithm that:
Makes a decision step by step, choosing one option at each level.
If the current partial choice does not lead to a complete solution, it will roll back and try another option.
He uses a search tree: the root is an empty choice, the leaves are a complete solution.
At worst: O (number of leaves of a search tree), often exponential.
Backtracking wood: 3 Ferzes (simplified)
At each level, a column is selected. Reverse = return to previous level.
Q1
Q2
Q2
Q3
Q3
Q3
Q3
X
OK
X
Red lines = rebound (conflict), green = allowed
The tree grows larger: each level is the next queen; the branch is broken if the position beats the previous queens.
def n_queens(n, row=0, cols=[], diag1=[], diag2=[]):
if row == n:
print(cols) # одна расстановка: cols[i] = столбец ферзя на строке i
return 1
count = 0
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # откат — бит, пропускаем
count += n_queens(n, row+1, cols+[col], diag1+[row-col], diag2+[row+col])
return count
print(f"Решений для 8 ферзей: {n_queens(8)}") # 92
# Визуализация:
def print_board(cols):
n = len(cols)
for r in range(n):
row = ['.' if c != cols[r] else 'Q' for c in range(n)]
print(' '.join(row))
print_board([0, 4, 7, 5, 2, 6, 1, 3]) # первое решение
8 Fersei — Scale
It's over 648 x 2.8x1014 combinations, with cuts ~15,000 nodes (of 4.4 billion).
About 19 million times less
I don't know what to do with it, because of the backtracking!
Labyrinth: Searching the return path
Start ~ End. On each cell, we try the neighbors from left to right. The dummy = return (backtrack).
S
A
B
✗
D
E
F
G
H
End
①
②
③
④
⑤
↩
↩
⑥
✓
Full = Tested, point = Backtrack
Path: S.A.B.O.M.E.I.End (found in six steps). B.C. was thrown away (tupid), E.H. was abandoned (the G.H gave the best route).
def solve_maze(maze, start, end):
path = []
visited = set()
def backtrack(pos):
if pos == end:
return True
for row in range(len(maze)):
for col in range(len(maze[row])):
if maze[row][col] == 1 and (row, col) not in visited:
visited.add((row, col))
path.append((row, col))
if backtrack((row, col)):
return True
path.pop() # backtrack
return False
visited.add(start)
path.append(start)
return path if backtrack(start) else []
maze = [[0,1,0,0,0],
[0,1,1,1,0],
[0,0,0,1,0],
[0,0,0,1,0]]
print(solve_maze(maze, (0,1), (3,4)))
# → [(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)]
🧭
Labyrinth: Animation Backtracking
N-Queens: step-by-step tree (4 queens, simplified)
Level 0: empty. Level 1: the queen in column 0. Level 2: the queen of column 1... each branch is cut off if the queen beats the previous one.
∅
[0]
[1]
[0,1]
✗
✗
[1,3]
✗
✓
✗
✗
✗
✓
✗
♪ = empty ♪ [0.1] = queen 0 in column 0, queen 1 in column 1 ♪ ♪ solution ♪
The branch [0.1] .. . ♪ [0.1.3?] has made a decision. ~99.99999% of the branches are cut off.
♕
N-Quens: Animation Backtracking
🎯
Mini-test: 5 questions
XP: 0
🧩
Quick test on the subject
Five questions, 20 XP for every correct answer.