BHU Entrance /Reasoning Ability

Puzzles

Non-Verbal & Puzzles · free study notes

🧩 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.


6.

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.