一键在 Manus 中运行任何 Skill

bfs-state-space

星标66

分支1

更新时间2026年5月17日 09:22

Model minimum-move problems as BFS over a state space. Use when solving bucket pouring puzzles, sliding tiles, or any problem asking for the shortest sequence of moves to reach a goal.

安装

用 Codex 或 Claude 帮你安装复制这段 Prompt，粘贴到 Codex、Claude 或其他助手里，让它检查 Skill 页面并帮你完成安装。

在 Manus 中运行

来源

knoopx

knoopx/pi

打开 GitHub 仓库查看创作者相关仓库

下载

在 Manus 中运行

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.

Edge cases

If start_bucket is forbidden as an immediate "fill the wrong one first" move, encode that as a filter on the initial transitions.

Example

Bucket pouring: state = (a, b). Transitions: fill A, fill B, empty A, empty B, pour A→B, pour B→A. BFS from (0, 0); first time a state has a goal value, that distance is the minimum.

同仓库更多 Skills

同仓库

markdown-rendering

knoopx/pi

Renders markdown to self-contained HTML with a custom dark stylesheet and opens in browser. Use when previewing markdown documents, generating styled HTML from README or report files.

2026-05-1966

notify

knoopx/pi

Inform the user what is happening — skip passive lookups

2026-05-1966

jj-core

knoopx/pi

Manage version control with Jujutsu (jj) — no staging area, immediate changes, smart rebasing. Use when navigating history, squashing, or pushing to Git remotes.

2026-05-1966

jj-hunk

knoopx/pi

Programmatic hunk selection for Jujutsu — split, commit, or squash specific hunks without interactive prompts. Use when making partial commits or selective squashes.

2026-05-1966

research-protocol

knoopx/pi

Gather facts from the web using evidence-first approach with mandatory citations. Use when researching topics, answering factual questions, or any task requiring web-sourced evidence.

2026-05-1966

binary-search

knoopx/pi

Search on monotonic predicates for sorted arrays, answer spaces, and rotated arrays. Use when finding minimum/maximum values, insertion points, or solving 'minimize the maximum' problems.

2026-05-1766

name	bfs-state-space
description	Model minimum-move problems as BFS over a state space. Use when solving bucket pouring puzzles, sliding tiles, or any problem asking for the shortest sequence of moves to reach a goal.
topic	State-Space Search
token_cost	120
related	["dfs-vs-bfs","dynamic-programming"]
keywords	["bucket","pouring","state space","minimum moves","shortest sequence","reach goal","transitions","visited states","water","pour","fill","empty"]

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.

Edge cases

If start_bucket is forbidden as an immediate "fill the wrong one first" move, encode that as a filter on the initial transitions.

Example

Bucket pouring: state = (a, b). Transitions: fill A, fill B, empty A, empty B, pour A→B, pour B→A. BFS from (0, 0); first time a state has a goal value, that distance is the minimum.