The New Sudoku Players' Forum

[qiuyanzhe]

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.

[qiuyanzhe]

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).

[Serg]

Hi, qiuyanzhe!
I am interested in minimum givens (clues) Latin Square puzzle investigations.

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

[qiuyanzhe]

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.

[Serg]

Hi, qiuyanzhe!
Unfortunately your post is too brief. I didn't understand most of your points.

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

[Mathimagics]

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?

[qiuyanzhe]

Strong means it can be solved by Naked Singles. Semi-strong means it can be solved by Naked Singles and Hidden Singles.

[qiuyanzhe]

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

[blue]

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.

[Serg]

Hi, qiuyanzhe!

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

[blue]

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 |
+-----------------------+

[Mathimagics]

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 |
  +-------------------+


[Mathimagics]

.
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!

[qiuyanzhe]

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]

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