So my wife and I were riding the train this morning, and having finished the crossword puzzle, we gave the KenKen a shot. It definitely provided some fun, but more so it got me thinking about combinations and permutations…
Eventually I started wondering how many total permutations there are of the 6 by 6 grid of numbers, and how many of those constitute valid KenKen boards (each row and each column must have all of the numbers between 1-6).
I ended up writing this script to brute force it:
But it seems like there are more combinations than I’d guessed! …
$ ./kenken.py 1 Number of unique combinations for cardinality 1: 1 Good: 1 Bad: 0 $ ./kenken.py 2 Number of unique combinations for cardinality 2: 6 Good: 2 Bad: 4 $ ./kenken.py 3 Number of unique combinations for cardinality 3: 1680 Good: 12 Bad: 1668
I’m running it with cardinality of 4 now (4×4 grid of numbers between 1-4) and it’s checking board 3 billion something…
Next steps would be trying to think of a clever way to find out the number of valid combinations for a 6×6 grid. Either we can continue with a programatic approach, either by using multiprocessing or just throwing random combinations at it, or both…
OR we could probably divert to math. A quick Google search gave me this link that seems to explain it pretty well:
I guess the answer is
6! * 5! * 4! * 3! * 2! * 1!, or
24883200 (right? someone wanna double check me here?).
Long story short, it looks like there’s no shortage of viable KenKen boards!
Thanks Cornell Department of Mathematics…
I was trying to wrap this KenKen thing up and get my work day started, so I kind of breezed over the Cornell article that I linked to, which explicitly states in the last paragraph:
It looks like the answer I was looking for (all combinations of the 6×6 board) is actually 812,851,200. Still, no shortage of KenKen fun here!
For more Latin Squares reading, check it out on Wikipedia: http://en.wikipedia.org/wiki/Latin_square
Thanks to my buddy jdp for double checking me.