Minimum givens on Latin Squares, and r+c+d conjecture

Everything about Sudoku that doesn't fit in one of the other sections

Minimum givens on Latin Squares, and r+c+d conjecture

Postby qiuyanzhe » Fri Aug 31, 2018 7:32 am

I am glad to see a topic about minimal givens on Sudokus, but I think that minimum givens on n*n Latin Squares is more natural and mathematical. For any size n there is a puzzle with floor(n^2/4) givens(OEIS A002620), with every number going diagonally and givens in two triangles, And that number of givens has been conjectured to be minimal. We have not found any helpful public research on the Internet.
I have something to share about this problem and some patterns in Latin Squares. And you are welcome to discuss with us if you are interested or you spot some useful articles, or you have your own view.
Last edited by qiuyanzhe on Thu Sep 06, 2018 1:23 am, edited 2 times in total.
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Fri Aug 31, 2018 10:02 am

These days I have been thinking about this problem:

If a n*n latin square puzzle, has all its givens in 'r' rows, 'c' columns and 'd' digits, where r+c+d=n-2, is it possible to have unique solution?

For example, here is a 8*8 puzzle with 2 rows, 2 columns and 2 digits.
Code: Select all
1 2 3 4 5 6 7 8
3 5 7 8 1 4 2 6
7 6 . . . . 1 .
4 3 . . 7 . . 1
2 1 . 7 . . . .
5 7 . 1 . . . .
8 4 1 . . 7 . .
6 8 . . . 1 . 7


The answer seems to be no, and if so, then the minimum number of givens is *almost* deducted to be floor(n^2/4).
Last edited by qiuyanzhe on Sat Sep 01, 2018 4:41 am, edited 2 times in total.
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby Serg » Fri Aug 31, 2018 3:56 pm

Hi, qiuyanzhe!
I am interested in minimum givens (clues) Latin Square puzzle investigations.
qiuyanzhe wrote:These days I have been thinking about this problem:

If a n*n latin square puzzle, has all its givens in 'r' rows, 'c' columns and 'd' digits, where r+c+d=n-2, is it possible to have unique solution?

For example, here is a 8*8 puzzle with 2 rows, 2 columns and 2 digits.
Code: Select all
1 2 3 4 5 6 7 8
3 5 7 8 1 4 2 6
7 6 . . . . 1 .
4 3 . . 7 . . 1
2 1 . 7 . . . .
5 7 . 1 . . . .
8 4 1 . . 7 . .
6 8 . . . 1 . 7


The answer seems to be no, and if so, then the minimum number of givens will be exactly floor(n^2/4), according to some deduction.

Do you state that if any Latin Square puzzle having all its givens in 'r' rows, 'c' columns and 'd' digits, where r+c+d=n-2 has not unique solution (i.e. has no solution or multiple solutions), then minimum number of givens will be exactly floor(n^2/4)?

Please, post your deduction.

Serg
Serg
2018 Supporter
 
Posts: 606
Joined: 01 June 2010
Location: Russia

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Sat Sep 01, 2018 4:38 am

I am sorry for not having a proof for specific situations. Here are my thoughts.


If there are (2k) rows, so that each of them has at most (k-1) givens.

Otherwise, for example, k=2, if there are 4 rows having 1 given in each..
Code: Select all
********
********
********
********
....a...
..b.....
.....c..
.......d


We can consider only the 4 rows with empty cells.
It could be transformed to the following pattern.
Code: Select all
a....e...
b..e.....
c.....e..
d.......e

with r=n-4, c=d=1.
(The other rows can always be completed row by row.)

In cases where some of the digits or columns repeat(at least 2k-2 times), things have not been done, but I don't think it matters too much. It may be solved in another way, or the method of the previous problem may also work on these grids.
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby Serg » Tue Sep 04, 2018 11:12 pm

Hi, qiuyanzhe!
Unfortunately your post is too brief. I didn't understand most of your points.
qiuyanzhe wrote:If there are (2k) rows, so that each of them has at most (k-1) givens.

"each of them has at most (k-1) givens" - what Latin Square puzzles do you mean - having unique solution or having multiple solutions? Row has at most (k-1) givens for what reason - to have unique solution or have not?

Did you see the article "Latin squares and critical sets of minimal size" by Joan Cooper, Diane Donovan and Jennifer Seberry (1991)?

Serg
Serg
2018 Supporter
 
Posts: 606
Joined: 01 June 2010
Location: Russia

Re: Minimum givens on Latin Squares

Postby Mathimagics » Wed Sep 05, 2018 12:05 am

Serg wrote:Did you see the article "Latin squares and critical sets of minimal size" by Joan Cooper, Diane Donovan and Jennifer Seberry (1991)?


Hi Serg!

I have obtained that paper. I am having trouble understanding what is meant by a strong critical set. The formal definition seems a little opaque to me. Can you assist?
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Wed Sep 05, 2018 2:07 am

Strong means it can be solved by Naked Singles. Semi-strong means it can be solved by Naked Singles and Hidden Singles.
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Wed Sep 05, 2018 3:34 am

Hi Serg!

I am afraid that it is too complex to describe in details.
Also, thanks for providing the research article. I don't think going through all equivalence classes is a good idea, bucause there will be too many as the grid goes bigger.
And there is a proof that minimal size of strong/semistrong critical set is floor(n^2/4), which can be found by searching "minimal strong critical set". (I am doubtful if it would work. There are many 7-given 5*5s requiring forcing chains..)
My guess is that, the minimal size is always floor(n^2/4), and all grids with that many clues have the pattern of two triangles.

12....
2.....
......
.....3
....34
...345
btw it is inspired by this pattern.//Enjoysudoku forum link by blue.


Another thing: I coined a concept called "distinction"(between 2 rows/columns), and it equals(for rows)"columns occupied+kinds of digits-number of digits".In
51.63.2..
6.152..4.
it is 7+6-10=3(can also be thought as 11,223,4. 5566 forms a cycle and does not count)
If two rows have distinction 1, then any way to fill the rest of the grid corresponds at least one solution. It could help proving some uniqueness techniques like UCC. But nothing for two rows with distinction 2 have been found.
qiuyanzhe
Last edited by qiuyanzhe on Thu Sep 06, 2018 12:34 am, edited 2 times in total.
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby blue » Wed Sep 05, 2018 7:08 am

qiuyanzhe wrote:btw it is inspired by this pattern.(Note:I heard that this puzzle comes from this forum, but I couldn't find the original post..)

See this post, and the one that follows.
blue
 
Posts: 683
Joined: 11 March 2013

Re: Minimum givens on Latin Squares

Postby Serg » Wed Sep 05, 2018 9:35 am

Hi, qiuyanzhe!
qiuyanzhe wrote:Strong means it can be solved by Naked Singles. Semi-strong means it can be solved by Naked Singles and Hidden Singles.

I should add a note to you post.
To my mind strong critical set in Latin Square puzzles implies that given puzzle (critical set) has unique solution path by naked singles. I.e. we must see the only naked single at each step of solution path. This concept (unique solution path) is new for Sudoku world.

Serg
Serg
2018 Supporter
 
Posts: 606
Joined: 01 June 2010
Location: Russia

Re: Minimum givens on Latin Squares

Postby blue » Wed Sep 05, 2018 12:01 pm

Hi qiuyanzhe,

Here are some "r + c + d = n - 2" puzzles with unique completions:

Code: Select all
+---------------+
| 1 4 6 3 5 7 2 |
| 2 1 5 7 3 4 6 |
| 5 6 1 . . . . |
| 3 5 . . . 1 . |
| 6 2 . . . . 1 |
| 7 3 . . 1 . . |
| 4 7 . 1 . . . |
+---------------+

+-----------------+
| 2 1 3 8 7 5 4 6 |
| 1 2 5 7 8 6 3 4 |
| 7 3 . . . 1 . 2 |
| 5 4 . 1 . . 2 . |
| 6 8 1 . . 2 . . |
| 8 5 . 2 1 . . . |
| 3 6 2 . . . . 1 |
| 4 7 . . 2 . 1 . |
+-----------------+

+-------------------+
| 9 2 3 4 6 7 1 5 8 |
| 2 1 5 9 8 6 3 4 7 |
| 1 6 8 7 9 2 4 3 5 |
| 7 3 . . . 1 . 2 . |
| 8 7 . 1 2 . . . . |
| 6 9 . 2 1 . . . . |
| 3 5 . . . . . 1 2 |
| 5 4 1 . . . 2 . . |
| 4 8 2 . . . . . 1 |
+-------------------+

+---------------------+
| 5 9 1 3 2 8 6 7 4 a |
| 2 1 3 8 a 7 9 4 5 6 |
| 1 a 2 7 6 4 3 8 9 5 |
| 9 6 5 . . . 2 . . 1 |
| 8 7 9 2 . . . 1 . . |
| 6 2 a . 1 . . . . . |
| a 4 8 . . 2 . . 1 . |
| 4 3 6 . . 1 . . . 2 |
| 3 8 7 . . . 1 2 . . |
| 7 5 4 1 . . . . 2 . |
+---------------------+

+-----------------------+
| 1 2 3 4 5 6 7 8 9 a b |
| 2 3 1 7 8 9 5 b a 6 4 |
| 3 1 2 5 a b 8 4 7 9 6 |
| 4 9 b . 2 3 . . 1 . . |
| 5 8 6 3 . . 2 . . 1 . |
| 6 7 5 . 1 . . 2 . . 3 |
| 7 4 9 . 3 . . 1 2 . . |
| 8 5 4 2 . . 1 . 3 . . |
| 9 b a . . 1 . 3 . 2 . |
| a 6 7 . . 2 3 . . . 1 |
| b a 8 1 . . . . . 3 2 |
+-----------------------+
blue
 
Posts: 683
Joined: 11 March 2013

Re: Minimum givens on Latin Squares

Postby Mathimagics » Wed Sep 05, 2018 2:51 pm

qiuyanzhe wrote:My guess is that, the minimal size is always floor(n^2/4), and all grids with that many clues have the pattern of two triangles.


All solution grids, or all puzzles?

Code: Select all
  +-------------------+
  | 1 2 3 . . . 4 . . |
  | 2 . 4 . . . . . . |
  | 3 4 2 . . . . . . |
  | . . . . . . . . 5 |
  | . . . . . . . . . |
  | 4 . . . . . . . . |
  | . . . . 7 . . 5 6 |
  | . . . . 5 . . . 7 |
  | . . . . 6 5 . 7 8 |
  +-------------------+


Solves to:
Code: Select all
  +-------------------+
  | 1 2 3 5 8 7 4 6 9 |
  | 2 5 4 6 1 8 7 9 3 |
  | 3 4 2 7 9 6 5 8 1 |
  | 7 8 6 1 4 3 9 2 5 |
  | 5 6 7 9 2 1 8 3 4 |
  | 4 7 5 8 3 9 6 1 2 |
  | 8 1 9 2 7 4 3 5 6 |
  | 6 9 8 3 5 2 1 4 7 |
  | 9 3 1 4 6 5 2 7 8 |
  +-------------------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: Minimum givens on Latin Squares

Postby Mathimagics » Wed Sep 05, 2018 3:35 pm

.
BTW, having made a cursory review of this problem, I can see why the N^2/4 conjecture has only been verified for N < 9.

Getting confirmation for N = 9, ie demonstrating that no 19-clue Latin Square puzzle exists on a 9 x 9 grid, is a computational problem of rather staggering proportions!
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Thu Sep 06, 2018 12:40 am

Hi Mathimagics,
Thanks for your example.
I'm sorry for not making my expression clear, but I think your puzzle has that pattern too.. I was meaning currently all (n^2/4) puzzles can be transformed to the pattern below.
By switching c47,c23,c78,c58,r23,r46,r78 it becomes

Code: Select all
 1 3 2 4 . . . . .
 3 2 4 . . . . . .
 2 4 . . . . . . .
 4 . . . . . . . .
 . . . . . . . . .
 . . . . . . . . 5
 . . . . . . . 5 7
 . . . . . . 5 7 6
 . . . . . 5 7 6 8
.

qiuyanzhe
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Re: Minimum givens on Latin Squares

Postby qiuyanzhe » Thu Sep 06, 2018 1:23 am

Hi blue,
Thanks for your link. My post has been edited.
And I fully appreciate your amazing examples with different sizes and various bottlenecks!
So we see r+c+d conjecture gets busted..

btw I am curious if the conjecture holds given d=0, ie the empty part is rectangular.
qiuyanzhe
qiuyanzhe
 
Posts: 20
Joined: 21 August 2017
Location: China

Next

Return to General