I took The Art of Computer Progamming Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions home last night to read instead of my usual, the dragon compilers book. AOCP Vol 4 Fas 0 is all about graphs and combinatorial puzzles. The book starts off with Knuth talking enthusiastically about how much he loves combinatorial problems, and the first chapter starts off with a couple of historical combinatorial puzzles. I’m not usually into puzzles, but these were actually so much fun.

Langford pairs

You are given the numbers {1, 1, 2, 2, …, n, n}, and you want to place them in a row so that exactly k numbers occur between the two appearances of each digit k.

When n = 3, there is essentially one way to arrange them: 231213 (and it’s left-right reversal)

What is the solution for n = 4?

Card sudoku

“Take all the aces, kings, queens, and jacks from an ordinary deck of playing cards and arrange them in a square so that each row and each column contains all four values and all four suits.” - Recreations mathematiques et physiques (Paris: 1725, Jacques Ozanam)

I hunger for more puzzles!