bfs-state-space
Installation
SKILL.md
When to use
When a problem asks for the MINIMUM number of moves/steps to reach a goal state (bucket pouring, puzzle solving, sliding tiles), model it as BFS over a state space.
Rules
- State = a tuple of all values that fully describe the situation (e.g. (bucket_a, bucket_b))
- From each state, enumerate every legal transition and produce the next state
- Use a visited set keyed on the state tuple to avoid cycles
- BFS from the start state; the first time you pop a state matching the goal, its distance is the minimum move count
- Track which bucket holds the goal and the other bucket's value at that point
- NEVER skip the visited check — cycles will cause infinite loops
- ALWAYS encode forbidden moves as filters on transitions, not as special cases
Example
Transitions for bucket pouring: fill A, fill B, empty A, empty B, pour A→B, pour B→A.