Princeton University Computer Science Department

Computer Science 345 The Efficient Universe Avi Wigderson

Spring 2006

Puzzles

General Information   |   Is This Course for Me?

Puzzle:

Domino:

Two opposite corners are removed from a 8x8 board. Is it possible to cover the remaining squares with 31 dominoes? (Each domino tile covers two adjacent squares.)

• Is the puzzle above interesting? Why?
• Is computing 1+1 an interesting puzzle? Why?
• Can you characterize interesting puzzles? (e.g. if your friend asked you a puzzle you couldn't solve, and later took an hour to explain the solution for you, would you find it interesting? How about a minute? How about a minute with the help of a computer?)
• If a puzzle has a short (quick to explain) solution, can a smart enough person (or a computer program) find such a solution fast?
• Can the solution to a given hard puzzle be viewed as a secret?

More puzzles...