Tree of Thoughts (Breadth-First)

The problem

Sampling whole solutions wastes compute on chains that went wrong early. Tree of Thoughts (Yao et al., 2023) searches over partial solutions instead. You have:

• a state: a partial solution;
• propose(state): a list of child states, the candidate next steps ("thoughts");
• value(state): how promising a state is (higher is better).

With breadth-first search, you keep the breadth best states at each level:

1. Start with the frontier [root].
2. At each of depth levels: expand every state of the frontier with propose, collect all the children, and keep the breadth children with the highest value. They are the new frontier.
3. Stop early if no state has children. Return the best state of the final frontier by value.

Example. A toy puzzle: reach the number 10 starting from 1. A step either adds 3 or doubles, so propose(s) is [s + 3, s * 2], and value(s) is minus the distance from 10, $-|10 - s|$. With breadth = 2 and depth = 3:

level	all children	kept, best first
1	4, 2	4 (value $-6$), 2 ($-8$)
2	7, 8, 5, 4	8 ($-2$), 7 ($-3$)
3	11, 16, 10, 14	10 ($0$), 11 ($-1$)

The best state of the last frontier is 10: the puzzle is solved.

With breadth = 1 (greedy): level 1 keeps 4; level 2 keeps 8 (children 7 and 8); level 3 has children 11 and 16, and the best is 11. The path to 10 went through 7, which greedy search threw away because 8 looked better at that moment. Keeping more states per level, a beam, recovers it.

What to implement

tot_bfs(root, propose, value, breadth, depth): return the best state of the final frontier.

Requirements

• Sort by value from high to low and keep ties in the order they were generated (Python's sorted is stable): frontier order first, then the order propose returned.
• breadth = 1 is greedy search.
• Call value on each candidate (calling it more than once is allowed; it is a pure function here).