The New Sudoku Players' Forum

by **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|. . .|. . .

by **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

by **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

by **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

by **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

by **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).

by **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

by **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

by **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

by **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.

by **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

by **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

by **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

by **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.)

by **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

The New Sudoku Players' Forum

Empty Boxes - I