Simon And Newell Human Problem Solving Theory 1971

Search Strategy Selection

Working Memory: LIMITED + Backtracking: CHEAP
└── Use progressive deepening (depth-first with backtrack)

Working Memory: ABUNDANT + State comparison: NEEDED  
└── Use scan-and-search (breadth-first)

Task Structure Assessment:
├── Clear goal state + Measurable progress → Means-ends analysis
├── Hard constraints + Dependencies → Most-constrained-first
├── Recognizable patterns + Action opportunities → Opportunistic planning
└── Multiple valid paths + Resource limits → Constraint satisfaction

Heuristic Design Decision Tree

Task has well-defined goal state?
├── YES: Extract differences between current and goal
│   ├── Differences are measurable? → Means-ends analysis
│   └── Differences are qualitative? → Pattern-based selection
└── NO: Use structural constraints
    ├── Hard constraints exist? → Most-constrained-first
    ├── Known patterns exist? → Production rules (condition→action)
    └── Multiple operators available? → Extract structural ranking info

FAILURE MODES

Speed Fallacy Anti-Pattern

Detection Rule: If solution involves "faster hardware" or "more parallelism" for search problems Symptoms: Agent examines thousands of nodes, performance scales with compute Diagnosis: Missing selectivity through structural information extraction Fix: Analyze task structure for exploitable patterns, constraints, or goal-distance measures

Universal Strategy Trap

Detection Rule: If same search approach (usually means-ends) applied to all problems Symptoms: Works on clear-goal problems, fails on constraint satisfaction or opportunistic tasks
Diagnosis: Strategy-task structure mismatch Fix: Match search pattern to task structure—means-ends for goal reduction, constraint propagation for CSPs, pattern recognition for opportunistic planning

Representation Blindness

Detection Rule: If optimization effort goes to search algorithms before testing representations Symptoms: Extensive tuning yields marginal gains, "obviously easy" problems remain hard Diagnosis: Wrong problem space for task structure Fix: Test 2-3 alternative state representations before optimizing search within any one

Architecture-Strategy Mismatch

Detection Rule: If strategy requires more working memory than system provides Symptoms: Thrashing, exponential memory growth, inability to backtrack effectively Diagnosis: Importing unlimited-memory strategies to constrained systems Fix: Use progressive deepening for memory-limited, scan-and-search only when memory permits full state tracking

Construction Neglect Pattern

Detection Rule: If problem space treated as "given" without explicit construction phase Symptoms: Agent can't initialize on new tasks, representation seems arbitrary Diagnosis: No systematic problem space construction from task environment Fix: Allocate design effort to representation selection proportional to search difficulty

WORKED EXAMPLES

Example 1: Cryptarithmetic Problem (SEND + MORE = MONEY)

Novice Approach:

• Problem space: All possible letter-to-digit assignments (10! = 3.6M states)
• Search: Try random assignments, check arithmetic
• Result: Examines thousands of invalid states

Expert Application:

• Problem space construction: States are partial assignments of letters to digits with constraints
• Structural information extraction:
  • Column constraints (C1 + C2 + carry_in = result + 10*carry_out)
  • Most-constrained variable first (S and M have only 2 valid values each)
  • Constraint propagation (if S=9, then M=1, eliminating other M values)
• Decision point: Use constraint satisfaction, not means-ends (no single goal state)
• Search strategy: Most-constrained-first with forward checking
• Result: Solution in 50-100 nodes by eliminating impossible branches early

Key Insight: Same task, different problem space. Constraint-based representation exposes structure that assignment-enumeration hides.

Example 2: Tower of Hanoi (5 disks)

Representation Comparison:

Poor representation: States as disk positions [(disk1_peg, disk2_peg, ...)]

• 3^5 = 243 possible states, most invalid (large on small)
• No structural guidance for move selection
• Search examines invalid configurations

Good representation: States as peg configurations with implicit size ordering

• Only ~100 valid states (legal configurations)
• Move constraints embedded in representation
• Goal-distance heuristic: count disks not on target peg

Decision Logic Applied:

1. Task structure: Clear goal state (all disks on peg 3), subgoal decomposition possible
2. Strategy selection: Means-ends analysis appropriate (goal-directed with measurable progress)
3. Heuristic design: Difference = number of disks not on target peg
4. Architecture match: Recursive subgoaling fits human memory limits through problem decomposition

Search Performance: Expert finds solution in 31 moves (optimal) by examining ~50 nodes. Poor representation might examine 1000+ nodes and find suboptimal 100-move solution.

Example 3: Medical Diagnosis Task

Task Environment: Patient symptoms → disease identification → treatment

Problem Space Construction Decision:

• Option A: States = all possible diseases, operators = diagnostic tests
• Option B: States = symptom clusters, operators = differential diagnosis rules
• Option C: States = causal pathways, operators = evidence accumulation

Expert Choice: Hybrid approach

• Initial search: Pattern recognition (symptoms → candidate diseases)
• Refinement search: Most-constrained-first (tests that differentiate top candidates)
• Architecture consideration: Use production rules for fast pattern matching, deeper search only for ambiguous cases

Decision Framework Applied:

1. Recognizable patterns exist → Use opportunistic planning (symptom patterns trigger disease hypotheses)
2. Hard constraints exist → Most-constrained-first for disambiguation (tests that rule out maximum candidates)
3. Memory limits binding → Progressive deepening with early pattern termination

QUALITY GATES

• Problem space representation chosen explicitly (not assumed/inherited)
• Search strategy matches task structure (goal-directed vs. constraint-based vs. opportunistic)
• Heuristics extract information from problem structure (not generic distance metrics)
• Architecture constraints respected (memory limits, processing speed, backtracking costs)
• Selectivity demonstrated (examines <1% of theoretical search space for non-trivial problems)
• Failure modes have detection rules (can diagnose wrong representation vs. weak heuristics)
• Alternative representations tested when performance poor
• Structural information sources identified (constraints, patterns, goal-distances, dependencies)
• Strategy switches based on task structure assessment
• Problem space construction process explicit (not ad-hoc representation choice)

NOT-FOR Boundaries

Do NOT use this skill for:

• Pure optimization problems: Use mathematical optimization theory instead
• Machine learning model selection: Use statistical learning theory
• Parallel algorithm design: Use concurrent systems theory
• Database query optimization: Use relational algebra optimization
• Real-time control systems: Use control theory

Delegation Rules:

• For numerical optimization with continuous variables → Use convex-optimization or metaheuristics
• For pattern recognition with training data → Use machine-learning-fundamentals
• For concurrent search across multiple agents → Use distributed-systems-coordination
• For problems with probabilistic uncertainty → Use decision-theory-under-uncertainty
• For reactive systems with timing constraints → Use real-time-systems-design

Boundary Markers:

• Problem has discrete states and operators (not continuous optimization)
• Search space is large but finite (not infinite optimization landscapes)
• Solution quality depends on path/sequence (not just final state)
• Human-level intelligence provides useful benchmarks (not superhuman performance requirements)3d:["$","$L46",null,{"content":"$47","frontMatter":{"license":"Apache-2.0","name":"simon-and-newell-human-problem-solving-theory-1971","description":"Foundational cognitive science theory of human problem-solving through heuristic search in problem spaces","category":"Research & Academic","tags":["problem-solving","cognitive-science","search","heuristics","theory"]}}]