The New Sudoku Players' Forum

[Mathimagics]

.

I hope that my fellow programmers will find this question intriguing!

Say we have a blank N x N grid, and a list, W, of N-digit words (ie. some subset of the N! valid numbers).

The aim is to form a Latin Square (or Sudoku grid) using only words from the list. That is, the words corresponding to each row (from left to right), and for each column (from top to bottom), must match a value in W.

My question is this - how many words must W contain in order to guarantee that at least one valid LS can be formed?

My rather limited progress to date can be viewed over at math.stackexchange (here).

[dobrichev]

how many words must W contain in order to guarantee that at least one valid grid can be formed?

0

[Mathimagics]

I meant to say "at least one valid latin square"!!

[Mathimagics]

.

It seems that there is no end to my stupidity ...

If we list all of the N! possible words, but exclude those beginning with 1 (there are (N-1)! of these), then no LS can be obtained from the resulting list.

So the minimum word-list size that guarantees a result is N! - (N-1)! + 1.


Sigh ...

[Mathimagics]

So the minimum word-list size that guarantees a result is N! - (N-1)! + 1.

But is that right? We can build a set with N! - (N-1)! entries as described, which admits no LS, and which is maximal, in the sense that the addition of any word to the list yields a LS.

But this does not actually prove that every set with N! - (N-1)! + 1 entries necessarily yields a LS. One suspects that this is so, but a proof is still required.