Saltar al contenido ForoHackers

Puzzles: start here

Acertijos
#623 · Ophuscado · · Denunciar

Puzzles are problems posed for the pleasure of solving them: logic grids, mathematical riddles, ciphers, programming challenges, mechanical and cryptic puzzles. They train reasoning, patience and the habit of reframing a problem, and many hide real computer science, from search and constraint solving to complexity.

Key concepts

  • Representation: choose the states, the moves and the goal; a good representation often makes the answer obvious.
  • Constraint reasoning: deduce what must be true, eliminate what cannot be, and repeat.
  • Search and backtracking: try a choice, follow it, undo it when it fails, and prune branches that cannot work.
  • Invariants and parity: a property that never changes can prove that a goal is impossible.
  • Simplification and symmetry: solve a smaller case first and look for the pattern.

Vocabulary

  • Invariant: a quantity or property that every legal move preserves.
  • Backtracking: searching by extending a partial solution and undoing steps that lead nowhere.
  • Constraint: a condition that any valid solution must satisfy.
  • Brute force: trying every possibility until one works.

What to study, in order

  1. Solve logic puzzles by hand and write down which deductions you used.
  2. Take classics such as towers, river crossings and sliding tiles, and describe each as states and moves.
  3. Learn pigeonhole, parity and invariant arguments through mathematical puzzles.
  4. Write a backtracking solver for sudoku or the N queens problem.
  5. Solve the same puzzles with a SAT or constraint solver and compare the approaches.

Related tags

#combinatorics #logic #algorithms #complexity #competitive-programming

Inicia sesión o únete para responder.