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

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 74 7 3 | . . 1 | 2 . .------+-------+------8 . 2 | . . . | . 7 43 1 4 | 8 . 7 | . . 2. 5 9 | . . . | . . .------+-------+------6 9 5 | . 8 4 | 7 . 12 4 8 | 1 . 5 | 3 9 .1 3 7 | 2 . 9 | 4 5 .`
r.e.s.

Posts: 337
Joined: 31 August 2005

As far as I know 81 is not divided by 4
bennys

Posts: 156
Joined: 28 September 2005

bennys wrote: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).
r.e.s.

Posts: 337
Joined: 31 August 2005

### unavoidable sets

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

Posts: 256
Joined: 16 July 2005

### Re: unavoidable sets

Moschopulus wrote: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 . 15 6 2 | 1 9 . | 3 8 7. 8 1 | 2 7 . | 5 6 9------+-------+------8 . 3 | 6 4 . | 9 . 5. . 5 | 9 3 . | 4 . 87 . 9 | 5 8 1 | . . 3------+-------+------3 . 8 | 4 6 . | 1 . 21 . 6 | . 2 . | 8 3 42 . 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.
r.e.s.

Posts: 337
Joined: 31 August 2005

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

Posts: 256
Joined: 16 July 2005

Moschopulus wrote: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.
r.e.s.

Posts: 337
Joined: 31 August 2005

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
`456123789189457326732869415543216897867395241921784653375948162614532978298671534                     `

with 10 uncovered cells and 30 4-unavoidables

(unchecked, there could be mistakes)
dukuso

Posts: 479
Joined: 25 June 2005

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

Code: Select all
`123568479864791352957243681218657934536489127749312865391825746472136598685974213`

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

Posts: 479
Joined: 25 June 2005

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?
Moschopulus

Posts: 256
Joined: 16 July 2005

this one should have MCN >=16 :

145726983
837495261
926381574
293874156
581269347
674153892
318547629
459632718
762918435
dukuso

Posts: 479
Joined: 25 June 2005

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?
Moschopulus

Posts: 256
Joined: 16 July 2005

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
dukuso

Posts: 479
Joined: 25 June 2005

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, ...)
r.e.s.

Posts: 337
Joined: 31 August 2005

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