1
$\begingroup$

I recently discovered the "KenKen" puzzle and have been trying to figure out some of the mathematics behind it. This led me to the following question:

Given an N x N grid, what is the minimum number of filled-in spaces ("clues") needed to define a unique grid, where we must satisfy the requirement that every row AND every column contains exactly one of the integers 1 through N.

It's easy to gather that it depends not only on the number of clues, but on their values as well. For example, the following clues define a unique 3x3 grid

Defines a unique grid.

but a 3x3 grid with only 1's on the diagonal does NOT define a unique grid.

Does not define a unique grid.

Does anyone have any insights into this (or other KenKen-related) problems? it is a very interesting topic indeed.

Thanks!

Improve this question
$\endgroup$
  • $\begingroup$ So you are assuming you have no "cages" where a block of numbers have to add or multiply (or divide or subtract for a cage of two adjacent cells) to a given target? Cages are common in Kenken. $\endgroup$ – user2566092 Apr 18 '15 at 18:11
  • $\begingroup$ Correct - This does not take into account cages. $\endgroup$ – Francis Apr 18 '15 at 18:30
2
$\begingroup$

What you are looking at is usually called latin squares in mathematics. These structures have the nice property of being the multiplication tables of quasigroups. A quasigroup is a set with a binary operation $(G,.)$ which has left and right division and cancellation. This means $\forall a,b \exists !c\;(a.c=b)$ and $\forall a,b \exists !d\; (d.a=b)$.

Such structures are generally not associative as if they are they end up forming a group. (Quite interesting really that just by adding associativity you force the appearance of a unit element.)

The question you are asking is open as far as I remember (7-8 years back) though some lower and upper bounds are known.

You can take a look at this paper for some older results (but more comprehensive I think) or enter link description here this younger one which I managed to only find behind a paywall I can't get through or an even younger one which should be accessible.

Edit: afterthought. I believe I remember that the best lower bounds were linear in the size of the square though the belief at the time was that they should really be quadratic.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the comment. Very interesting! $\endgroup$ – Francis Apr 18 '15 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.