Largest number of empty groups?

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

no 5 empty boxes after all?

Postby Big Blue » Mon Aug 22, 2005 12:47 pm

@gfroyle: thanks for pojnting this out - I am willing to believe it, but do you have some reference for this statement?

Actually, it appears that also

X00
0X0
X0X

does not help much - I manage to find clue grids easily such that it is possible to fill up to 3 cells each in boxes 4 and 8, but that's it.

So evidence points to a nogo result - but there seems to be no proof yet. The problem is that there are always several cells where you have only 3 possibilities - so I cannot exclude yet that there might be some clever forcing-chain-like argument which miraculously establishes some crucial cells uniquely.
Big Blue
 
Posts: 28
Joined: 01 August 2005

Re: no 5 empty boxes after all?

Postby gfroyle » Mon Aug 22, 2005 12:56 pm

Big Blue wrote:@gfroyle: thanks for pojnting this out - I am willing to believe it, but do you have some reference for this statement?


If you have two empty rows (or columns) in the same block, then you can just exchange the corresponding rows (or columns) in the completed grid, and get a different one...
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby tso » Tue Aug 23, 2005 5:26 am

Two consequtive empty boxes is no problem, but I'm convinced that 5 is impossible.

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



... though you can come close ...

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



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


Here are some with 5 empty 3x3 areas:

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




Code: Select all
 7 9 2 | 1 . . | . 8 4
 3 . . | . . . | . 6 1
 8 . . | . . . | . 7 3
-------+-------+------
 4 . . | . 7 9 | . . .
 . . . | 6 8 4 | . . .
 . . . | 5 2 1 | . . .
-------+-------+------
 . . . | . . . | 3 1 5
 9 1 6 | . . . | 4 2 7
 5 3 4 | . . . | 6 9 8
tso
 
Posts: 798
Joined: 22 June 2005

Postby tso » Tue Aug 23, 2005 6:31 am

I'm convinced that that 9 empty groups is the absolute maximum. There are several other similar patterns. Here's my pick for best of of the genre:

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


3 empty rows, 3 empty columns, 3 empty boxes plus a 5x5 empty area in the center. I also believe that this is the largest possible empty square area anywhere in the grid.

Here's one with the widest possible empty regular diagonal swath:
Code: Select all
 . . . | . 5 4 | 6 8 3
 . . . | . . 9 | . . 1
 . . . | . . . | 2 . 9
-------+-------+------
 . . . | . . . | . 7 8
 8 . . | . . . | . . 5
 6 9 . | . . . | . . .
-------+-------+------
 5 . 6 | . . . | . . .
 2 . . | 8 . . | . . .
 3 4 7 | 5 6 . | . . .



Unfortunately, just like the one I posted at the top of this thread, these examples are too easy, requiring only naked and hidden singles. Perhaps Nick70 will fix this for us?
tso
 
Posts: 798
Joined: 22 June 2005

Close... but no cigar..

Postby gfroyle » Tue Aug 23, 2005 6:36 am

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

0 0 0  1 0 0  9 4 7
0 0 0  0 0 0  8 5 3
0 0 0  0 0 0  6 1 2

0 0 0  8 9 6  1 3 4
0 0 0  4 1 2  5 7 9
0 0 0  7 5 3  2 6 8


1 7 4  0 0 0  0 0 0
6 8 5  0 0 0  0 0 0
9 3 2  0 0 0  0 0 0

0 0 0  1 0 0  8 4 7
0 0 0  0 0 0  9 1 5
0 0 0  0 0 0  6 2 3

0 0 0  9 8 6  1 5 2
0 0 0  4 5 1  3 7 6
0 0 0  7 3 2  4 9 8
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Tue Aug 23, 2005 8:37 am

these

0X0
x0x
0x0

are isomorphic to

00x
00x
xx0

but the lower right 0 is forced anyway.

So this ia essentially the same as

xxx
x00
x00

or B1B2B3B4B7 , which we examined exhaustedly
in another thread.

2802 nonisomorphic configurations with 1960-6280 solutions
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Tue Aug 23, 2005 9:12 am

By permuting bands and stacks there are only two possible configurations

XX0
00X
X00

and

XX0
00X
00X

(anyone for a game of X's and 0's ???)

The second of these is ruled out by previous work, as dukuso said in the previous message.
Would a similar computation do the first case? Maybe it is harder since the corner 0 is not so constrained.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Nick70 » Tue Aug 23, 2005 9:48 am

tso wrote:Perhaps Nick70 will fix this for us?

The second pattern is very redundant, I removed the corner clues to make the puzzles minimal. Maybe with a longer search it would be possible to remove r3c7 and r7c3 to have a 5x5 box in the middle.

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


. . . . 8 7 3 2 .
. . . . . 9 . . 4
. . . . . . 6 . 5
. . . . . . . 7 9
2 . . . . . . . 8
5 3 . . . . . . .
1 . 4 . . . . . .
6 . . 7 . . . . .
. 8 7 4 5 . . . .


. . . . 8 7 3 2 .
. . . . . 9 . . 4
. . . . . . 6 . 5
. . . . . . . 7 9
2 . . . . . . . 8
5 6 . . . . . . .
3 . 4 . . . . . .
6 . . 2 . . . . .
. 8 7 3 1 . . . .


. . . . 8 7 3 2 .
. . . . . 9 . . 4
. . . . . . 6 . 5
. . . . . . . 7 9
1 . . . . . . . 8
5 6 . . . . . . .
3 . 1 . . . . . .
6 . . 5 . . . . .
. 8 7 1 6 . . . .


The other pattern is much thougher, my program has been looking for half an hour and no puzzles yet.
Nick70
 
Posts: 156
Joined: 16 June 2005

remaining loophole

Postby Big Blue » Tue Aug 23, 2005 1:05 pm

@gfroyle: thanks for the simple answer to my naive question; in retrospect (as always) it appears trivial...

@dukuso: ok, great, so there is only one candidate pattern left, namely (adopting Moschopulus' convention of ordering the boxes)

XX0
00X
X00

or B1B2B6B7 in dukuso's nomenclature

Again, it is easy to construct the clue grid such that you can immediately fill in 3 cells each in B3 and B4, but that's it, it seems.

Is there also an exhaustive treatment available yet?

And if not, is anybody interested to feed his/her programme with this clue grid to finally establish the (non-)existence of Sudokus with 5 empty boxes?
Big Blue
 
Posts: 28
Joined: 01 August 2005

Postby gfroyle » Wed Aug 24, 2005 6:55 am

Nick70 wrote:The other pattern is much thougher, my program has been looking for half an hour and no puzzles yet.


I have put 150 (inequivalent) puzzles with Tso's pattern of 6 2x2 little boxes on the following URL.

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=5

Are they all simple to work?

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Wed Aug 24, 2005 9:31 am

@gordon: most of these (~80%) are difficult for my program

@B1B2B4B9:
there are about 56000 essentially different configurations
of B1B2B4. For each of these we have 9!/6/6 B9s
That's about 560million sudokus to solve.

It could take some days, I interrupted it after an hour.
Fewest so far: 84 solutions
Doesn't look like there could be one with 1 solutions.
Last edited by dukuso on Thu Aug 25, 2005 12:09 pm, edited 1 time in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby tso » Thu Aug 25, 2005 2:26 pm

[quote="gfroyle]I have put 150 (inequivalent) puzzles with Tso's pattern of 6 2x2 little boxes on the following URL.

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=5

Are they all simple to work?

Gordon[/quote]

Cool! I just tried one at random -- it was certainly NOT simple, requiring me to use coloring and naked quads.
tso
 
Posts: 798
Joined: 22 June 2005

Postby tso » Thu Aug 25, 2005 2:38 pm

Nick70 -- thanks for all the puzzles in the patterns I posted in this thread!


Nick70, Gorden, others: For the non-programmer in simple terms, how does your program go about creating a puzzle, especially one that fits a set pattern?
tso
 
Posts: 798
Joined: 22 June 2005

Postby Pappocom » Fri Aug 26, 2005 3:26 am

Just a reminder to all. The generation of puzzles is not a fit topic for the Sudoku Players Forums.

- Wayne.
Pappocom
 
Posts: 599
Joined: 05 March 2005

Postby dukuso » Fri Aug 26, 2005 10:04 am

Pappocom wrote:Just a reminder to all. The generation of puzzles is not a fit topic for the Sudoku Players Forums.

- Wayne.



well, it's in the "everything else" rubric.
How can anything "not fit" there ? ;-)

I'm curious about your strategy: are you just trying to ban
and remove this topic from this forum,
or are you somehow fighting against this discussion too in other
places worldwide ? What other activities did you take or are
you planning to take to diminish discussion about generating
sudokus ?

Can this be any successful ?
I mean, the more you say that you don't want this discussion,
the more people are getting curious...
Or is it just this, what you want : people becoming curious ? ;-)


- Guenter
dukuso
 
Posts: 479
Joined: 25 June 2005

Previous

Return to General