1

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!

Francis
  • 33
  • 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. – user2566092 Apr 18 '15 at 18:11
  • Correct - This does not take into account cages. – Francis Apr 18 '15 at 18:30

1 Answers1

2

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.

DRF
  • 5,167