🧩 Reasoning Ability – Puzzles
BHU Entrance – Study Notes (MIT‑Level)
Goal: Model puzzle solving as a formal reasoning task, develop systematic tools, and explore theoretical limits.
Table of Contents
| Section | Sub‑Topics | Key Take‑aways |
|---|---|---|
| 1. Foundations | 1.1 Logic & Formal Systems | Propositional vs. Predicate Logic |
| 2. Classical Puzzle Taxonomy | 2.1 Deductive vs. Problem‑solving | 2.2 Spatial, Numerical, Sequence |
| 3. Graph‑Based Modeling | 3.1 Constraint Graphs | 3.2 Graph Colouring, Bipartite Matching |
| 4. Constraint Satisfaction | 4.1 CSP Formalism | 4.2 Arc Consistency & Backtracking |
| 5. Combinatorial Search | 5.1 Depth‑First, Breadth‑First | 5.2 Heuristics (A*, IDA*) |
| 6. Decision‑Tree & Probabilistic Methods | 6.1 Bayesian Inference | 6.2 Monte‑Carlo Tree Search |
| 7. Edge Cases & Ambiguity | 7.1 Contradictory & Incomplete Information | 7.2 Non‑Deterministic Puzzles |
| 8. Advanced Topics | 8.1 SAT Solving & CNF | 8.2 Integer Linear Programming |
| 9. Challenging Problem | 9.1 Statement & Annotated Solution | 9.2 Discussion of Complexity |
| 10. Further Reading | 10.1 Books & Papers | 10.2 Online Resources |
1. Foundations
1.1 Logic & Formal Systems
| Type | Syntax | Semantics | Example |
|---|---|---|---|
| Propositional Logic | (p, q, r); connectives (\land,\lor,\neg,\rightarrow) | Truth tables | “If it rains then the ground is wet.” |
| Predicate Logic (First‑Order) | (P(x), Q(x,y)); quantifiers (\forall,\exists) | Domain of discourse | “All students are enrolled.” |
Why it matters for puzzles
- Many puzzles can be encoded as logical formulae.
- Deductive puzzles correspond to model checking: find a model that satisfies all constraints.
Exercise
Translate the following puzzle statement into first‑order logic:
“Every cat has a unique owner who is a human, and no two cats share the same owner.”
Answer:
(\forall x,(\text{Cat}(x) \rightarrow \exists y,(\text{Human}(y)\land\text{Owner}(x,y))))
(\land \forall x\forall y,(\text{Cat}(x)\land\text{Cat}(y)\land x\neq y \rightarrow \exists z,(\text{Owner}(x,z)\land \text{Owner}(y,z)\rightarrow z=z)))
(…plus uniqueness constraints.)
2. Classical Puzzle Taxonomy
| Category | Typical Features | Representative Puzzles |
|---|---|---|
| Deductive | 1‑sentence clues, hidden variables | Zebra Puzzle, Knights & Knaves |
| Spatial | Arrangements on a grid or circle | Sudoku, Kakuro |
| Numerical | Arithmetic relationships | Cross‑numbers, Futoshiki |
| Sequence | Order constraints | Tower of Hanoi, 15‑Puzzle |
Key Insight:
*Identify the underlying constraint graph: nodes = variables, edges = constraints.
3. Graph‑Based Modeling
3.1 Constraint Graphs
- Vertices = variables (e.g., “Seat 3”, “Number 7”).
- Edges = pairwise constraints (e.g., “must be adjacent”, “must differ”).
Example:
Zebra puzzle → 10 houses × 5 attributes → 50 vertices, edges encode “belongs to same house”.
3.2 Graph Colouring
- Assign colors (values) to vertices such that adjacent vertices differ.
- Classic NP‑complete problem; many puzzles reduce to colouring.
Bipartite Matching
- Used when constraints are pairwise and each variable must be matched to a unique partner.
- Hungarian Algorithm solves in (O(n^3)).
Edge Cases
- Odd cycle → no 2‑colouring → indicates contradiction.
- Disconnected graph → solve components independently.
4. Constraint Satisfaction (CSP)
A CSP is a tuple ((X,D,C)) where
- (X = {x_1,\dots,x_n}) variables
- (D = {D_1,\dots,D_n}) domains
- (C = {c_1,\dots,c_m}) constraints
4.1 Arc Consistency (AC‑3)
- Propagates local consistency: for each pair ((x_i,x_j)), prunes values in (D_i) that have no support in (D_j).
- Complexity (O(ed^3)) (e (=) number of arcs, (d) max domain size).
4.2 Backtracking Search
- Recursive assignment, prune on constraint violation.
- Heuristics:
- MRV (Minimum Remaining Values)
- Degree (most constrained variable)
- Least Constraining Value (value that rules out fewest others)
4.3 Forward Checking
- After assigning a variable, immediately remove inconsistent values from neighbors.
- Reduces search tree size dramatically for dense CSPs.
5. Combinatorial Search
5.1 Depth‑First vs. Breadth‑First
- DFS explores a branch to depth before backtracking; low memory.
- BFS guarantees shortest path in unweighted graphs; high memory.
5.2 Heuristic Search
- A*: (f(n)=g(n)+h(n)); admissible (h) ensures optimality.
- IDA*: iterative deepening with depth‑first limit; memory‑efficient.
Example Application:
15‑Puzzle (sliding tiles) → graph of states; solvable using IDA* with Manhattan distance heuristic.