Empty Boxes - I

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

Postby 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
coloin
 
Posts: 1637
Joined: 05 May 2005

A Possible Solution for Coloin's Puzzle

Postby 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
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby 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.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby 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
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby 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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
Last edited by JPF on Mon Aug 07, 2006 6:43 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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

Last edited by JPF on Mon Aug 07, 2006 6:34 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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.
skYrth
 
Posts: 3
Joined: 28 July 2006

PreviousNext

Return to General