## Empty Boxes - I

Everything about Sudoku that doesn't fit in one of the other sections
Here is a minimal puzzle with 33 clues.....and 3 empty boxes !

Cant get a 34 though

Code: Select all
`+---+---+---+|123|...|.8.||78.|...|.5.||.56|...|1.3|+---+---+---+|...|56.|8.7||...|..7|231||...|..1|56.|+---+---+---+|312|64.|...||6..|.78|...||..8|31.|...|+---+---+---+`

Questions

......Why is this a difficult puzzle ?
......How do you solve it without backtracking ?

C
coloin

Posts: 1790
Joined: 05 May 2005

### A Possible Solution for Coloin's Puzzle

Code: Select all
` *--------------------------------------------------------------------* | 1      2      3      | 479    5      469    | 4679   8      469    | | 7      8      49     | 1      239    23469  | 469    5      2469   | | 49     5      6      | 24789  289    249    | 1      2479   3      | |----------------------+----------------------+----------------------| | 249    349    1      | 5      6      2349   | 8      49     7      | | 4589   6      459    | 489    89     7      | 2      3      1      | | 2489   349    7      | 2489   2389   1      | 5      6      49     | |----------------------+----------------------+----------------------| | 3      1      2      | 6      4      5      | 79     79     8      | | 6      49     459    | 29     7      8      | 3      1      245    | | 459    7      8      | 3      1      29     | 46     24     2456   | *--------------------------------------------------------------------*`

Let's note that we have an almost Type-E3 Almost Unique Rectangle in cells r56c14 (if r6c14 are not "2" and r5c1 is not "5"), and also the Almost Nice Loop in cells {r3c1|r3c5|r5c5|r56c14} if also r3c5 is not "2". Finally, consider r3c8 as our "problem cell".
Ok, so we could write:

[r6c5]=3=[r6c2]-3-[r4c2]{={ATILA(4): r8c2|r4c2|r4c8|r6c9|r8c9}=3|5=
[r8c9]-5-[r8c23]({ATILA(4,9): r3c8|r3c1|r2c3|r8c3|r8c2|r4c2|r4c8}-4,9-
r3c8)-9-[r8c4](-2-[r6c4])=9=[r9c6]-9-[r3c6]}-4,9-[r4c1]-2-[r4c6]=2=
=[r6c5]-2-[r3c5]-{Nice Loop: [r3c1]-9-[r3c5]=9=[r5c5]-9-[r56c4]=9=
=[r56c1]-9-[r3c1]}-9-[r3c1](-4-[r3c6]-2-[r3c8])=9=[r2c3]-9-[r8c3]=9=
=[r8c2]-9-[r4c2]=9=[r4c8]-9-[r7c8]-7-[r3c8],

which implies that r6c2<>3 and that solve the puzzle.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

coloin wrote:......Why is this a difficult puzzle ?

Because it cannot be solved with basic methods I noticed that minimal high clue puzzles tend to be more difficult than e.g. 17-clues. So i suppose that the necessity to keep them minimal leads to harder puzzles.
ravel

Posts: 998
Joined: 21 February 2006

Thank-you Carcul,
Showing how it can be done.......thinking about it some more made me conclude that "any" method which leads to a contradiction is essentially the same as any other. Your method [though I cant follow it exactly] shows me why I cant solve these difficult puzzles !

The clues are non synergistic witheach other [deliberately] The point is reached in the puzzle where there is only one way to complete - yet this is only obvious when the alternative ways lead to a contradiction.

One more strategically placed clue would make the puzzle very very easy - but then it would not be minimal !

All in all it is not a good puzzle.

Im trying to find a 34 with this pattern......by doing that you are deliberately compressing the clues/unavoidable sets........this might mean there will be a 36 when you use previously unavailable clues in the 3 empty boxes.

c
coloin

Posts: 1790
Joined: 05 May 2005

Although it (probably) adds nothing to solving coloin's puzzle, an XY-Wing in Carcul's grid results in [r4c6]<>9 and the grid below. I haven't found a simple way to solve this puzzle. However, I did observe that [r2c9]<>4|9. Is there a non-chain technique that'd catch [r2c9]'s reductions? Now, I just wish that I could find a simple reduction for [r2c9]<>2.

Code: Select all
`*--------------------------------------------------------------------*| 1      2      3      | 479    5      469    | 4679   8      469    || 7      8      49     | 1      239    23469  | 469    5      26-49  || 49     5      6      | 24789  289    249    | 1      2479   3      ||----------------------+----------------------+----------------------|| 249    349    1      | 5      6      234-9  | 8      49     7      || 4589   6      459    | 489    89     7      | 2      3      1      || 2489   349    7      | 2489   2389   1      | 5      6      49     ||----------------------+----------------------+----------------------|| 3      1      2      | 6      4      5      | 79     79     8      || 6      49     459    | 29     7      8      | 3      1      245    || 459    7      8      | 3      1      29     | 46     24     2456   |*--------------------------------------------------------------------*[r2c9]=4 => {[r2c3]=9,[r6c9]=9} => [b3]=INVALID[r2c9]=9 => {[r2c3]=4,[r6c9]=4} => [b3]=INVALID`
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

coloin wrote:Here is a minimal puzzle with 33 clues.....and 3 empty boxes !
....
C

On the other hand, from the 17 clues gfroyle list :

no puzzle with 3 empty boxes
24 puzzles with 2 empty boxes.

All are isomorphic to :
0XX
X0X
XXX

Here is the updated list (see the previous list from Ocean here) :

Code: Select all
`000000031000407000000600000600300000407000000500080000030010000020000700000000450000000109400050000000020300000109000500007000000300000013000000080000040009000020000000210780000000000000400000000305000014000000060000201000040000800007060500000000000280000310000000060000500000040703000000000000001000502300016000700040000000000000308400050000000020100000103000500007000000800000013000000080000020009000040000028000000010070000000035050600200037000000000000100800400000000305000100000000000028000000010070000000063030500200067000000000000100800400000000306000100000000000200080000000350000604000000000204700900000500000000140070000026000000000030000000308000460000000500000000000000150000064000000000300008120000000500200070000004000320000850000000010000000000016000000000203000005090000000610300400000200800000000320000850000000010000000000016000000000302000005090000000610300800000200400000000320000860000000010000000000041000000000203000006090000000410300500000200800000000320000860000000010000000000051000000000302000006090000000510300800000200400000000600100040200000030000070500000084102000000600000000000089000000030600000000002001430600300000050000800000000201000750000000080000000000000408000075000000000200001430700300000050000800000000201000560000000080000000000000408000065000000000200150000000040200000000030000603070000000000510008000000000500200000401000000000708150000000040200000000030000706080000000000510003000000000500200000401000000000806200000500000000960800000000010380000060000400000020070000000081000506000000700000200600030040000090000010000700300000105000000000809000080000500000000107030000000420000000000000910000000600000416000750000000000090000000500082601000000000300000600000507300080200000000400210000000000430000005700000000502000000000010000000090600000507300080200000000400210000000000460000005700000000502000000000010000000090701000000000904000000300000090000300000000409200000000000700028600010050040000000`

All of them seem to be rather easy.

The most difficult (?) one (#2)
Code: Select all
` . . . | . . . | 1 . 9 4 . . | . 5 . | . . . . . . | . 2 . | 3 . .-------+-------+------- . . . | 1 . 9 | . . . 5 . . | . . 7 | . . . . . . | 3 . . | . . .-------+-------+------- . 1 3 | . . . | . . . . 8 . | . . . | . 4 . . . 9 | . . . | . 2 .`

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

I propose this conjecture on the empty boxes.

This puzzle (B3B5B7=0):
Code: Select all
` x x x | x x x | . . . x x x | x x x | . . . x x x | x x x | . . .-------+-------+------- x x x | . . . | x x x x x x | . . . | x x x x x x | . . . | x x x-------+-------+------- . . . | x x x | x x x . . . | x x x | x x x . . . | x x x | x x x`

can only have 0 or 1 solution.

Any proof or counter-example ?

PS : one can start with an easiest one (B3=0 for example).

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Assuming that each partial band and stack obeys the basic rules of sudoku, your conjecture follows from the facts that
• Completed B1,B2,B6,B9 => at most one choice for B3
• Completed B4,B6,B2,B8 => at most one choice for B5
• Completed B8,B9,B1,B4 => at most one choice for B7
I'll grind through the first of those in what follows.

Row 1 has six values filled in, leaving three to go in r1c7-9 in some order: call these three choices n1,n2,n3. Same goes for row 2, with choices n4,n5,n6 say; and row 3 with choices n7,n8,n9. Since the total collection of filled-in numbers (B1,B2) plus choices (for B3) contains three copies of each digit 1-9 (one copy per row), and the (B1,B2) part accounts for two of those copies (one in B1, the other in B2), it must be the case that {n*} are the digits 1-9 in some order.

So, whatever digit d you think of, you know what minirow in B3 it must appear in. By similar reasoning, you know what minicol it must appear in. In other words, each digit 1-9 has only one allowed position in B3. If these nine positions are all distinct, you have one solution for B3; if not, you have no solutions.
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks Red Ed.

Your proof is perfectly clear.
The conjecture is now an easy lemma.

What about this new conjecture :

This puzzle (B1B2=0):
Code: Select all
` . . . | . . . | x x x . . . | . . . | x x x . . . | . . . | x x x-------+-------+------- x x x | x x x | x x x x x x | x x x | x x x x x x | x x x | x x x-------+-------+------- x x x | x x x | x x x x x x | x x x | x x x x x x | x x x | x x x`

can only have 0 or 2^k solutions (k=0,1,2,3)

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Yes, that conjecture is true too. I checked by computer: fix the minicolumn arrangement[*] for B1; loop over all 280 minicol arrangements for B2; loop over all 280 minirow arrangements for B3. For each of the 280^2 cases within the double loop, count how many of the 3!^6 perms of the B1/B2 minicol contents are valid, hoping this is equal to 0, 1, 2, 4 or 8. You end up with:
• no solution in 33904 cases
• 1 solution in 25056 cases
• 2 solutions in 15624 cases
• 4 solutions in 3564 cases
• 8 solutions in 252 cases
This shows that the number of solutions cannot be anything outside of {0,1,2,4,8}. Then you just need to demonstrate at least one example grid for each of those, which I imagine you've done already, or you could just appeal to the fact that every valid band can be embedded in a valid grid.

[*] by minicol arrangement I mean: the three values in each minicol are specified, but not their order; and we have minicol 1 > minicol 2 > minicol 3 for any convenient meaning of ">". There are 9! / 3!^4 = 280 possible minicol arrangements.
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks again, Red Ed.
The real question for the B1B2 conjecture was to know if it was true for k=4.

Here is a new one.

Conjecture III :

This puzzle (B1B2B4B9=0)
Code: Select all
` . . . | . . . | x x x . . . | . . . | x . x . . . | . . . | x x x-------+-------+------- . . . | x x x | x x x . . . | x . x | x . x . . . | x x x | x x x-------+-------+------- x x x | x x x | . . . x . x | x . x | . . . x x x | x x x | . . .`

can only have 0 or k solutions ; k=2,3,4,...,27,28*.

I removed the redundant clues in the middle of boxes B3,B5,B6,B7,B8 and the box B9 (B3B5B7 Lemma).

* same question mark for 28.

JPF
Last edited by JPF on Mon Aug 07, 2006 6:43 pm, edited 1 time in total.
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Conjecture IV

This puzzle (B1B2B3=0)
Code: Select all
` . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- x x x | x x x | x x x x x x | x x x | x x x x x x | x x x | x x x-------+-------+------- x x x | x x x | x x x x x x | x x x | x x x x x x | x x x | x x x`

Can only have 0 or 12k solutions.
(k is one of these 16 numbers : 8,10,12,13,14,15,16,18,19,22,23,24,43,48,72,144 )

[Edit : k=144 was missing in my initial list. In the following post, Red Ed proves that 144 is part of the list
]

As a consequence, when the puzzle has at least one solution, the minimum number of solutions is 96 and the maximum is 1728.

[Edit : conjectures I & II were proved or verified by Red Ed in his previous posts]
Conjectures III, IV are still conjectures.
They need to be proved or... disproved.

JPF

Last edited by JPF on Mon Aug 07, 2006 6:34 pm, edited 1 time in total.
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

JPF wrote:This puzzle (B1B2B3=0)
...
Can only have 0 or 12k solutions.
(k is one of these 15 numbers : 8,10,12,13,14,15,16,18,19,22,23,24,43,48,72 )
No. You can have k=144 as well, e.g. like this ...
Code: Select all
`. . .|. . .|. . .. . .|. . .|. . .. . .|. . .|. . .-----+-----+-----2 3 4|5 6 7|8 9 15 6 7|8 9 1|2 3 48 9 1|2 3 4|5 6 7-----+-----+-----3 4 5|6 7 8|9 1 26 7 8|9 1 2|3 4 59 1 2|3 4 5|6 7 8`
... but apart from that, your list is complete.

Conjectures II, III, IV are still conjectures.
They need to be proved or... disproved.
I verified conjecture II in my previous post!
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks again, Red Ed, for the comprehensive check of conjecture IV.

I made my statement after looking at the results of some (~ 100000) simulations.
It appears that it was not enough.
The probability to get 1728 (=12x144) solutions must be very low.

I will accordingly modify the list in my initial post.

I don't see any obvious logical relations beetwen the 16 elements of the sequence.
What about the factor 12 ?

Red Ed wrote:I verified conjecture II in my previous post!
Sorry for that, it was a typo.

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

here was one i just recently did (easy)

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

and another one (can't find it tho)

x . x|. x . |x . x|
. x . |x . x|. x . |
x . x|. x . |x . x|
-----+----+------
that was the top and bottom, the middle wasn't at all pattern.
skYrth

Posts: 3
Joined: 28 July 2006

PreviousNext

Return to General