It's a lot of options.

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

Back to the table of contents
Alterna · Chapter 22 · page 22.2
It's a lot of options.
Backtracking, N-Queens, reshuffling, locations, combinations.
When a problem has no smart solution, we cross all options by cutting it off.
Backtracking
(Return search) is the main trick used in N-Queens, trumps, shapes, and combinatorial tasks.
GEF
PIF
EGE No. 12.23
01
Types of combined objects
Object
Formula
Example
Spaces without repetition A(n,k)
n! / (n−k)!
Seat 3 out of 5
Reshuffle 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
We make a decision step by step, choosing one option at each level.
If the current partial choice doesn't lead to a complete solution, we 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.
03
N-Queens Visualizer
♛
Task N Fersei: Stepwise Animation
N