Saltar al contenido ForoHackers

Puzzles: start here

Acertijos
#3129 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder