Jan 132015
 

http://f.cl.ly/items/25322w1e2O163G1S1l39/kenken.jpg

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:

https://gist.github.com/loisaidasam/507e82157d670023500b

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:

http://www.math.cornell.edu/~mec/KenKen/Lecture_4.html

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…