The New Sudoku Players' Forum

by **coloin** » Fri Jul 07, 2006 9:36 am

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

by **Carcul** » Fri Jul 07, 2006 12:36 pm

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

by **ravel** » Fri Jul 07, 2006 2:49 pm

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.

by **coloin** » Tue Jul 11, 2006 6:42 pm

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

by **daj95376** » Wed Jul 12, 2006 7:21 am

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

by **JPF** » Wed Jul 12, 2006 1:13 pm

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: 000000031000407000000600000600300000407000000500080000030010000020000700000000450 000000109400050000000020300000109000500007000000300000013000000080000040009000020 000000210780000000000000400000000305000014000000060000201000040000800007060500000 000000280000310000000060000500000040703000000000000001000502300016000700040000000 000000308400050000000020100000103000500007000000800000013000000080000020009000040 000028000000010070000000035050600200037000000000000100800400000000305000100000000 000028000000010070000000063030500200067000000000000100800400000000306000100000000 000200080000000350000604000000000204700900000500000000140070000026000000000030000 000308000460000000500000000000000150000064000000000300008120000000500200070000004 000320000850000000010000000000016000000000203000005090000000610300400000200800000 000320000850000000010000000000016000000000302000005090000000610300800000200400000 000320000860000000010000000000041000000000203000006090000000410300500000200800000 000320000860000000010000000000051000000000302000006090000000510300800000200400000 000600100040200000030000070500000084102000000600000000000089000000030600000000002 001430600300000050000800000000201000750000000080000000000000408000075000000000200 001430700300000050000800000000201000560000000080000000000000408000065000000000200 150000000040200000000030000603070000000000510008000000000500200000401000000000708 150000000040200000000030000706080000000000510003000000000500200000401000000000806 200000500000000960800000000010380000060000400000020070000000081000506000000700000 200600030040000090000010000700300000105000000000809000080000500000000107030000000 420000000000000910000000600000416000750000000000090000000500082601000000000300000 600000507300080200000000400210000000000430000005700000000502000000000010000000090 600000507300080200000000400210000000000460000005700000000502000000000010000000090 701000000000904000000300000090000300000000409200000000000700028600010050040000000

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

by **JPF** » Sun Aug 06, 2006 11:10 am

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

by **Red Ed** » Sun Aug 06, 2006 2:09 pm

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.

by **JPF** » Sun Aug 06, 2006 4:18 pm

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

by **Red Ed** » Sun Aug 06, 2006 6:45 pm

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.

by **JPF** » Sun Aug 06, 2006 10:10 pm

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

by **JPF** » Mon Aug 07, 2006 3:46 pm

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

by **Red Ed** » Mon Aug 07, 2006 5:55 pm

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 1 5 6 7|8 9 1|2 3 4 8 9 1|2 3 4|5 6 7 -----+-----+----- 3 4 5|6 7 8|9 1 2 6 7 8|9 1 2|3 4 5 9 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!

by **JPF** » Mon Aug 07, 2006 10:41 pm

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

by **skYrth** » Tue Aug 08, 2006 12:03 am

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.

The New Sudoku Players' Forum

Empty Boxes - I

A Possible Solution for Coloin's Puzzle