The New Sudoku Players' Forum

[r.e.s.]

Can anyone find a Sudoku solution grid composed *entirely* of four-digit patterns of the type

Code: Select all

     a  b

     b  a

where the digits are on the corners of a rectangle with one ab-pair in one 3x3 box and the other ab-pair in another 3x3 box? I.e., every digit in the solution is one of four digits in such a pattern. The closest I've found so far is the solution to the following puzzle (where I've used just the four-digit patterns themselves as clues):

Code: Select all

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

[bennys]

As far as I know 81 is not divided by 4

[r.e.s.]

As far as I know 81 is not divided by 4

It isn't apparent that such a solution would require 81 to be divisible by 4, because a cell can be in more than one pattern (i.e., the patterns can overlap).

[Moschopulus]

So you want a completed grid where each digit is a member of an unavoidable set of size 4.

You will need at least 21 unavoidable sets of size 4.

The grid in the first post here (the "Grid not containing a 16" thread)

http://forum.enjoysudoku.com/viewtopic.php?t=1527&start=0

has 20 unavoidable sets of size 4. That's the highest number I've seen, but I haven't done a big search or anything.

[r.e.s.]

The grid in the first post here (the "Grid not containing a 16" thread) http://forum.enjoysudoku.com/viewtopic.php?t=1527&start=0 has 20 unavoidable sets of size 4. That's the highest number I've seen, but I haven't done a big search or anything.

Thanks, I hadn't read that thread. In the present context, that solution grid is an improvement over the one specified above -- but not by much (if I haven't miscounted, it falls short of the goal by 26 cells, compared to 27 for the one above).

Not surprisingly (considering how you made it), this one can't be presented like the one above, with just the pattern-digits shown as clues ...

Code: Select all

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

... because this partial grid does not have a unique solution, due to some 6-cell unavoidable sets that are disjoint from the 4-cell ones.

[Moschopulus]

At least that's something. Since that grid is 26 cells short, there's a fair bit of overlap between the 4-sets. I doubt very much if your grid exists. Generally speaking, a high number of unavoidable 4-sets will correspond to a high MCN (MCN = clique number = max number of pairwise disjoint unavoidables). That grid (MG) has MCN = 15, and 20 4-sets. The highest MCN I've ever seen is 15, so I doubt if any grid has many more than 20 4-sets, and probably all grids will fall short. Of course that's not a proof....

The program UNAVOID from http://www.maths.nuim.ie/staff/gmg/sudoku will find unavoidable sets, and the MCN, and give a max clique. (It's contained in checker.zip Any questions, just ask.) Usually a max clique consists of a fair number of 4-sets, but bigger sets as well.

This post http://forum.enjoysudoku.com/viewtopic.php?t=605&start=315 gives MCNs of a load of random grids.

[r.e.s.]

At least that's something. [..]

Definitely, and I thank you for the info & links. In my present unenlightenment, I still look for a grid that significantly reduces the current best value of 26 -- maybe I'll wise up after a bit more study.

[dukuso]

these 4-unavoidables are inside one 3*9-chute.
So, we can examine the 416 bands and there is one
(#145, gangster #31) with 7 such sets and 22 cells
being involved:

123456789
457189326
869732415

now, choose a grid with all 3 bands being #145 and you have
66 cells being involved in some 4-unavoidable which
lies in a horizontal band. (grids with all 3 bands from the same
S-class do always exist)
Many(all?) of the remaining 15 cells can probably be covered
by the vertical 4-unavoidables

with B12347-method I found this one :

Code: Select all


456123789
189457326
732869415
543216897
867395241
921784653
375948162
614532978
298671534     
               



with 10 uncovered cells and 30 4-unavoidables

(unchecked, there could be mistakes)

[dukuso]

here is one with all cells being in a 4-unavoidable :

Code: Select all

123568479
864791352
957243681
218657934
536489127
749312865
391825746
472136598
685974213



t-invariant, all chutes are #271, gangster 38

[Moschopulus]

Interesting! Good idea to use the bands. This has 36 unavoidable 4-sets. I didn't think any grid would have that many.

Even with so many 4-sets, the MCN of this grid is still only 15. Can you construct a grid with MCN = 16?

[dukuso]

this one should have MCN >=16 :

145726983
837495261
926381574
293874156
581269347
674153892
318547629
459632718
762918435

[Moschopulus]

Yes it does. Excellent! Which gangsters are they?

I can't resist the next (rather obvious) question....can you construct a grid with MCN = 17?

[dukuso]

chutes 97,139,52
gangsters 28,31,33
t-invariant.

this wasn't constructed, I just searched the t-invariant grids.
This takes about 1sec. per grid and nr. 906 was successful.
Searching a MCN=17, if it exists this way would presumably take days

[r.e.s.]

dukuso, Is there any particularly good link that would help me get up to speed on the techniques & terminology you're using? (B12347-method, gangsters, t-invariance, ...)

[dukuso]

most terms are only reused by me.
wikipedia,Frazer's page, search-button above are good references

B12347 : blocks 1,2,3,4 and 7 i.e. first band and stack

gangsters: 44 G-classes of 3*9-chutes
also 416 S-classes of 3*9-chutes
t-invariant: isomorphic to its transpose

http://www.setbb.com/phpbb/viewtopic.php?t=194&mforum=sudoku

(grr, do you people also have the problem, that the
editing window is gone after opening another window
e.g. for searching for links ?)

see also "sticky:basic terms" in some forum here.
I don't want to search the exact link, else I might
have to edit this post again...