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
but a 3x3 grid with only 1's on the diagonal 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!
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.