## Latin Square Construction Problem

Programs which generate, solve, and analyze Sudoku puzzles

### Latin Square Construction Problem

.

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).
Last edited by Mathimagics on Mon Apr 25, 2016 8:18 pm, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1099
Joined: 27 May 2015

### Re: Latin Square Construction Problem

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

0
dobrichev
2016 Supporter

Posts: 1634
Joined: 24 May 2010

### Re: Latin Square Construction Problem

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

Mathimagics
2017 Supporter

Posts: 1099
Joined: 27 May 2015

### Re: Latin Square Construction Problem

.

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
2017 Supporter

Posts: 1099
Joined: 27 May 2015

### Re: Latin Square Construction Problem

Mathimagics wrote: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.

Mathimagics
2017 Supporter

Posts: 1099
Joined: 27 May 2015