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…

  One Response to “Tuesdays and KenKen”

  1. UPDATE!

    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 turns out that this is the beginning of a math problem that isn’t done. The boards that we have talked about here go by the name latin squares. One problem that mathematicians don’t know an answer to is how many nxn latin squares there are, that is, how many ways there are of filling in of an nxn board with the numbers 1 to n appearing exactly once in each row and column, there are for an arbitrary n.

    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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)