Latin Square Construction Problem

Programs which generate, solve, and analyze Sudoku puzzles

Latin Square Construction Problem

Postby Mathimagics » Mon Apr 25, 2016 7:52 pm

.

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Latin Square Construction Problem

Postby dobrichev » Mon Apr 25, 2016 7:59 pm

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: 1296
Joined: 24 May 2010

Re: Latin Square Construction Problem

Postby Mathimagics » Tue Apr 26, 2016 2:31 pm

I meant to say "at least one valid latin square"!! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Latin Square Construction Problem

Postby Mathimagics » Wed Apr 27, 2016 2:20 pm

.

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Latin Square Construction Problem

Postby Mathimagics » Thu Apr 28, 2016 9:09 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Software