Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Choose every unused value for the next slot: The Permutation Wheel.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Permutation backtracking matches the clues
- 2Keep this true after every move: path contains distinct chosen indices and has one value per completed position
- 3Reach the result within O(n times n!) output time
Rules and pressure
- Target cost: O(n times n!) output time
- State rule: path contains distinct chosen indices and has one value per completed position
Lesson 1 of 3
Live algorithm trace
Permutation backtracking
Complete execution1 of 6
1
choice
2
3
0
1
2
The first position may choose any sorted value.
1
if path length is n: record2
for each index3
skip index when already used4
mark used and append value5
recurse for next position6
pop and unmarkpath = []used = none
Truth to preserve / Cost target
Truth to preserve
path contains distinct chosen indices and has one value per completed position
Cost target
O(n times n!) output time
Each recursion depth owns one output position. Try every unused value there, mark it during the child search, then unmark it for the next sibling.
Your call · What should guide every step of this algorithm?