Empty Boxes - I

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

Postby Red Ed » Thu Aug 10, 2006 1:57 pm

JPF wrote:This puzzle (B1B2B4B9=0)
...
can only have 0 or k solutions ; k=2,3,4,...,27,28*.
Yes (verified with an exhaustive check).

Here's an example with k=28 solutions:
Code: Select all
. . .|1 5 9|3 4 8
. . .|2 . 8|1 . 7
. . .|3 4 7|2 6 9
-----+-----+-----
1 2 4|9 7 5|. . .
5 . 7|6 . 1|. . .
6 8 9|4 3 2|. . .
-----+-----+-----
2 1 5|. . .|. . .
3 . 8|. . .|. . .
4 9 6|. . .|. . .
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Tue Aug 15, 2006 11:24 pm

This puzzle B2B3B4B6B7B8 = 0

Code: Select all
+---+---+---+
|568|...|...|
|279|...|...|
|431|...|...|
+---+---+---+
|...|396|...|
|...|724|...|
|...|581|...|
+---+---+---+
|...|...|674|
|...|...|235|
|...|...|891|
+---+---+---+ 108558 solutions



This can have 0 or k solutions ;

Does k[min] = 108558 ?

How many essentially different B1B5B9 combinations are there ?

Code: Select all
108558 sol.      568......279......431.........396......724......581.........674......235......891
110635 sol.      179......254......638.........269......518......473.........421......573......896
............
............
262926 sol.      832......954......176.........761......328......495.........945......132......876
283576 sol.      123......456......789.........123......456......789.........123......456......789


C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby JPF » Thu Aug 17, 2006 6:37 pm

Red Ed wrote:...
Yes (verified with an exhaustive check).
Thanks for the check.

coloin wrote:This puzzle B2B3B4B6B7B8 = 0

Code: Select all
+---+---+---+
|568|...|...|
|279|...|...|
|431|...|...|
+---+---+---+
|...|396|...|
|...|724|...|
|...|581|...|
+---+---+---+
|...|...|674|
|...|...|235|
|...|...|891|
+---+---+---+ 108558 solutions


This can have 0 or k solutions ;
Does k[min] = 108558 ?

C

As far as I'm concerned, it's bit far from my program capacities.
It could do it, but it will take days.

Actually, I'm working on some easier cases :
B1B2B3B4=0 and B1B2B4B5=0

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Wed Aug 23, 2006 3:26 am

I was surprised when this one turned up - it is nearly 10% better than the next best !
Code: Select all
+---+---+---+
|125|...|...|
|836|...|...|
|749|...|...|
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|134|
|...|...|287|
|...|...|596|
+---+---+---+   95514 sol.


I do believe the B12347 and the accompaning B5689 or B1245 have been worked out.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby JPF » Wed Aug 23, 2006 10:31 pm

coloin wrote:I was surprised when this one turned up - it is nearly 10% better than the next best !
Good !
Is there any room for an improvement ?

coloin wrote:I do believe the B12347 and the accompaning B5689 or B1245 have been worked out.

Right, B1245=0 ( isomorphic to B5689=0 and equivalent to B15689=0) has been worked out by Dukuso and PatmaxDaddy :
Here
coloin wrote:...
Dukuso calculated the best
Code: Select all
XXX
XOO
XOO
had 1960 solutions
which was updated to 1152 solutions with PatmaxDadday
Code: Select all
+---+---+---+
|...|159|268|
|...|368|147|
|...|247|359|
+---+---+---+
|124|...|...|
|387|...|...|
|965|...|...|
+---+---+---+
|241|...|...|
|738|...|...|
|659|...|...|
+---+---+---+

I'm still looking at all the possible numbers of solutions for a given shape.
In the B1245=0 case, equivalent to :
Code: Select all
0FF
F00
F00
(F is a full box), I'm far to have reached any conclusion with only 5000 simulations

Meanwhile, I propose this new conjecture V :

This puzzle (B1B2B6B9=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 | . . .



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


JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Thu Aug 24, 2006 6:16 am

coloin wrote:I was surprised when this one turned up - it is nearly 10% better than the next best !
... 95514 sol.
That's the best possible, having exhaustively checked all 237083 essentially-different B1B5B9. I've no idea what the next best is, since I abort counts once they go past the best so far, but it's no greater than 96841 (so 95514 isn't as much an outlier as you first thought).

JPF wrote:This puzzle (B1B2B6B9=0):
...
can only have 0 or 2^k solutions (k=0,1,2,...,6)
The fact that no other number of solutions is possible is a simple corollary of your B1B2=0 proposition.

JPF wrote:I'm still looking at all the possible numbers of solutions for a given shape.
In the B1245=0 case
The range is 1152 to 11664. Next smallest/biggest are 1840 and 6280. Most of the solutions are in the low 2000s, apparently with no interesting patterns. I can't think why you'd want to study this (except for the coding challenge).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Thu Aug 24, 2006 3:58 pm

B1245=0 case
Thanks for these informations.
I’m a bit surprised by the maximum 11664 : with the few simulations I’ve made, I am still at a maximum of 4783.
As you say the average is around 2000 solutions/puzzle: it gives a lengthy search.
I will stop looking at this discouraging B1245 case.

puzzle (B1B2B4B6=0)
...
[Edit : deleted after Red Ed's exhaustive search ; see his post below]

JPF
Last edited by JPF on Wed Aug 30, 2006 11:48 am, edited 2 times in total.
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Fri Aug 25, 2006 9:20 am

Thank-you Red Ed for doing that - and for confirming the lowest B159.
I must admit that I did not search all of the "237083 essentially-different B1B5B9", I only searched 5000 or so of the essentially different -

Code: Select all
+---+---+---+
|1xx|...|...|
|xxx|...|...|
|xxx|...|...|
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|134|
|...|...|287|
|...|...|596|
+---+---+---+


I have been a bit fortunate - my next best around was 104000.

The way I have completed the B5B9 means that The B6 and B8 boxes both have only 392 completions each.

Thee are only 5 different ways 384,392,400,432 & 448 to complete these cross-combinations, as described by Frazer
Frazer wrote:In response to coloin, it takes a little thought to persuade yourself that there are 5 classes of constraints; then a computer determines all of the values 384,...,448. Let's assume that we are trying to count the number of ways to complete

??? ***
??? ***
??? ***
123
456
789

where we are given all the *, and want the ?. The situations are:

(1) The three rows of * have the same numbers as the three columns (in some order); for example, 147/258/369, or 825/417/693 [432 ways to fill in the ?].
(2) One of the three rows has the same numbers as a column, but the other two have just two; e.g., 147/259/368 [384 ways].
(3) All three rows have two numbers from a column; e.g., 148/259/367 [392 ways].
(4) Two rows have two numbers from a column, but the other has just one; e.g., 143/256/789 [400 ways].
(5) All three rows have one number from each column; e.g., 123/456/789 [448 ways].

It takes a little thought to convince yourself that there are no other possibilities.


There are 18 such pairs in a grid. The 400 option is by far the most common.

Edit - or are there 36 such pairs ?
C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby JPF » Tue Aug 29, 2006 6:33 pm

puzzle (B1B2B4B6=0)
[Edit Aug. 30]
Here is one with 10 solutions :

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


Question : Is it easy to prove that the following digits can be placed ?

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


I also edited the beginning of the thread in order to give links and the main results from past discussions.

JPF
Last edited by JPF on Wed Aug 30, 2006 11:56 am, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Tue Aug 29, 2006 8:16 pm

JPF wrote:Question : Is it easy to prove that the following digits can be placed ?

Box 6 and the 5 in r2c4, yes. r4c3=3 with a 4 cell forcing chain, r2c1=3 with a 6-cell forcing chain (eliminating 4 from r2c5). This gives the rest of box 2.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Red Ed » Wed Aug 30, 2006 12:19 pm

JPF wrote:This puzzle (B1B2B4B6=0)
...
can only have 0 or k solutions ; k=10, 11, 12,…, 176.
Note : again, I made a random search.
I got all these numbers of solutions except 12 numbers. (11,12,13,155,163,...)
Overnight, I did another exhaustive search. Apart from cases with no solutions, the full range of solutions is { 7...166, 168...170, 172, 174, 176, 178, 180, 184, 186, 188, 192, 208, 216, 224 }. Here are examples of the min and max of that range:
Code: Select all
  7 : 000314000000782000000965000000000743000000826000000915123478569456139278789256134
224 : 271000000538000000964000000000583000000721000000964000123479865456238179789156324
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Wed Aug 30, 2006 9:49 pm

B1B2B4B6=0

Red Ed wrote:Overnight, I did another exhaustive search. Apart from cases with no solutions, the full range of solutions is { 7...166, 168...170, 172, 174, 176, 178, 180, 184, 186, 188, 192, 208, 216, 224 }.

Thanks Red Ed for the exhaustive search.
Impressive and quick work !

There are 175 possibilities ; I only got 155 after "solving" 200000 puzzles.
I was far to find the exact min and max [7 ; 224]

It proves, if it was necessary, that a pure random search is not the more appropriate way to get all the possible numbers of items of a collection.

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby Eioru » Thu Sep 07, 2006 3:43 am

How about this pattern?

Code: Select all
*.*.*.*.*
.........
*.*.*.*.*
.........
*.*...*.*
.........
*.*.*.*.*
.........
*.*.*.*.*

24-clue
there are 8 empty rows and 1 empty box
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby daj95376 » Thu Sep 07, 2006 2:01 pm

Multiple solutions prevent your pattern from working. Rows/Columns 4 & 6 could be exchanged. (Thanks Ruud for pointing this out to me awhile back.)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby JPF » Thu Sep 07, 2006 2:25 pm

daj95376 wrote:Multiple solutions prevent your pattern from working. Rows/Columns 4 & 6 could be exchanged. (Thanks Ruud for pointing this out to me awhile back.)

Of course.
If you take some time to read the last posts of this thread, you will understand Eioru’s question :

number of solutions for puzzles having this pattern. (Min, Max, etc...)

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General