The New Sudoku Players' Forum

by **coloin** » Sun Apr 22, 2007 10:15 pm

Thanks Mike.........my attempts to generate puzzles are obviously very crude.

I scanned a template of this pattern over a million random grids and got one puzzle........[I made no attempts to improve possible puzzles with low grid solution counts]

Repeating it with an equivalent template - I got only 2 puzzles per million.........

Unless my "random grids" arnt that random !

Im not sure how yours and JPFs techniques work ! [obviously better !]

C

by **m_b_metcalf** » Mon Apr 23, 2007 12:03 am

coloin wrote:Im not sure how yours and JPF's techniques work ! [obviously better !]

I once made a post on this subject that I can't find now. Basically, there are two techniques:

1) generate a grid, overlay the template, check that the clues yield only one solution.

2) from the template generate a set of sudoku-compatible values for the clues; check that the clues yield one and only one solution.

In my experience, method 2 has a higher yield that method 1 [edit: I don't know why

].

You can, of course, add various refinements, such as demanding in method 2 that all values in a house are distinct.

JPF may have found yet another algorithm.

Regards,

Mike Metcalf

by **JPF** » Fri Apr 27, 2007 4:43 pm

tso wrote:I do not believe you can create a valid puzzle or even determine more than 2 of the central cells with this mask:
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

I'm sure that an exhaustive search can be made to answer tso's question about the existence of a valid puzzle with this pattern.
Some experts like Red Ed and gsf know how to do it.
I don't.

Meanwhile, here are some results.

The minimum number of solutions is less than 80 :

80 solutions

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

I give all the different possibilities that I found about the number n of calculated cells and their positions in the boxes B.

n=0 ; 152 solutions

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

n=1 ; B5(r5c5=4) ; 581 solutions

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

n=2 ; B5(r4c5=4),B5(r6c6=5) diagonal ; 780 solutions

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

n=2 ; B5(r4c4=2),B5(r5c4=1) vertical ; RW ; 1200 solutions

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

n=2 ; B5(r5c5=4),B8(r8c6=4) ; 242 solutions

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

n=2 ; B4(r6c3=2),B6(r5c7=4) ; 332 solutions

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

n=3 ; B5(r4c5=1),B5(r5c6=2),B5(r6c4=3) ; RW ; 1872 solutions

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

n=3 ; B5(r4c5=4),B5(r5c5=6),B6(r5c8=4) ; 326 solutions

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

n=3 ; B2(r2c6=3),B4(r6c2=3),B5(r5c5=3) ; 242 solutions

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

JPF

by **udosuk** » Sat Apr 28, 2007 2:06 pm

JPF, this is from your earlier results:

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

by **JPF** » Sat Apr 28, 2007 3:17 pm

udosuk wrote:JPF, this is from your earlier results...

Yes, but it's not the same pattern...

I edited my previous post which apparently was confusing.
I removed from the grid the calculated cells.

JPF

by **udosuk** » Sun Apr 29, 2007 8:47 am

Sorry JPF... I get your concept now...

Sorry my programming power (or the lack of it) can't help you there...

by **Havard** » Sun Apr 29, 2007 9:33 pm

JPF wrote:
tso wrote:I do not believe you can create a valid puzzle or even determine more than 2 of the central cells with this mask:
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

I'm sure that an exhaustive search can be made to answer tso's question about the existence of a valid puzzle with this pattern.
Some experts like Red Ed and gsf know how to do it.
I don't.

Meanwhile, here are some results.

The minimum number of solutions is less than 80 :

Here you have one with 64 solutions:

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

Havard

by **daj95376** » Sun Apr 29, 2007 10:51 pm

While I was working on Havard's first puzzle, he replaced it.

Code: Select all: # Havard's (renumbered) puzzle after resolving Naked Singles and Pairs # -- still 64 solutions. # Candidate <1>: 4 boxes/columns/rows; Templates <1>: 8 (all powers of 2) # Candidate <2>: 4 boxes/columns/rows; Templates <2>: 4 # Candidate <3>: 5 boxes/columns/rows; Templates <3>: 16 # Candidate <4>: 2 boxes/columns/rows; Templates <4>: 2 # Candidate <5>: 3 boxes/columns/rows; Templates <5>: 4 # Candidate <6>: 2 boxes/columns/rows; Templates <6>: 2 # Candidate <7>: 4 boxes/columns/rows; Templates <7>: 8 # Candidate <8>: 5 boxes/columns/rows; Templates <8>: 16 # Candidate <9>: 3 boxes/columns/rows; Templates <9>: 4 ^--------------------------------------------------------------------^ | 1 2 3 | 4 5 6 | 7 8 9 | | 5 7 9 | 238 38 238 | 1 6 4 | | 8 4 6 | 179 17 179 | 5 3 2 | |----------------------+----------------------+----------------------| | 7 368 12 | 1389 46 1389 | 348 29 5 | | 4 38 15 | 1579 2 1579 | 38 79 6 | | 9 368 25 | 3578 46 3578 | 348 27 1 | |----------------------+----------------------+----------------------| | 2 9 8 | 157 17 157 | 6 4 3 | | 6 5 4 | 238 38 238 | 9 1 7 | | 3 1 7 | 6 9 4 | 2 5 8 | ^--------------------------------------------------------------------^

[Addendum: It might be interesting to see the canonical form of all 64 solutions.]

by **Havard** » Sun Apr 29, 2007 11:01 pm

daj95376 wrote:While I was working on Havard's first puzzle, he replaced it.

ah, sorry mate. I just saw that JPF had 123456789 in the first row, so I wanted to fit it to his format

Same puzzle, just swapped the numbers.

Havard

by **JPF** » Mon Apr 30, 2007 7:09 am

Havard wrote:Here you have one with 64 solutions ...

Great !

daj95376 wrote:[Addendum: It might be interesting to see the canonical form of all 64 solutions.]

Here are the 64 solutions.
Note that starting from the normalized pattern, r5c5=2 is the only calculated cell (case n=1; B5),

123456789579832164846971532732168495481529376965347821298715643654283917317694258
123456789579238164846971532762143895481529376935867421298715643654382917317694258
123456789579283164846971532732168495481529376965347821298715643654832917317694258
123456789579382164846971532762143895481529376935867421298715643654238917317694258
123456789579832164846971532762148395431529876985367421298715643654283917317694258
123456789579238164846971532782163495431529876965847321298715643654382917317694258
123456789579283164846971532762148395431529876985367421298715643654832917317694258
123456789579382164846971532782163495431529876965847321298715643654238917317694258
123456789579238164846179532732861495481925376965743821298517643654382917317694258
123456789579832164846179532762341895481925376935768421298517643654283917317694258
123456789579382164846179532732861495481925376965743821298517643654238917317694258
123456789579283164846179532762341895481925376935768421298517643654832917317694258
123456789579238164846179532762841395431925876985763421298517643654382917317694258
123456789579832164846179532782361495431925876965748321298517643654283917317694258
123456789579382164846179532762841395431925876985763421298517643654238917317694258
123456789579283164846179532782361495431925876965748321298517643654832917317694258
123456789579238164846971532731869425485127396962543871298715643654382917317694258
123456789579832164846971532761349825485127396932568471298715643654283917317694258
123456789579382164846971532731869425485127396962543871298715643654238917317694258
123456789579283164846971532761349825485127396932568471298715643654832917317694258
123456789579238164846971532761849325435127896982563471298715643654382917317694258
123456789579832164846971532781369425435127896962548371298715643654283917317694258
123456789579382164846971532761849325435127896982563471298715643654238917317694258
123456789579283164846971532781369425435127896962548371298715643654832917317694258
123456789579832164846179532731968425485721396962345871298517643654283917317694258
123456789579238164846179532761943825485721396932865471298517643654382917317694258
123456789579283164846179532731968425485721396962345871298517643654832917317694258
123456789579382164846179532761943825485721396932865471298517643654238917317694258
123456789579832164846179532761948325435721896982365471298517643654283917317694258
123456789579238164846179532781963425435721896962845371298517643654382917317694258
123456789579283164846179532761948325435721896982365471298517643654832917317694258
123456789579382164846179532781963425435721896962845371298517643654238917317694258
123456789579238164846917532732861495481529376965743821298175643654382917317694258
123456789579832164846917532762341895481529376935768421298175643654283917317694258
123456789579382164846917532732861495481529376965743821298175643654238917317694258
123456789579283164846917532762341895481529376935768421298175643654832917317694258
123456789579238164846917532762841395431529876985763421298175643654382917317694258
123456789579832164846917532782361495431529876965748321298175643654283917317694258
123456789579382164846917532762841395431529876985763421298175643654238917317694258
123456789579283164846917532782361495431529876965748321298175643654832917317694258
123456789579832164846719532732168495481925376965347821298571643654283917317694258
123456789579238164846719532762143895481925376935867421298571643654382917317694258
123456789579283164846719532732168495481925376965347821298571643654832917317694258
123456789579382164846719532762143895481925376935867421298571643654238917317694258
123456789579832164846719532762148395431925876985367421298571643654283917317694258
123456789579238164846719532782163495431925876965847321298571643654382917317694258
123456789579283164846719532762148395431925876985367421298571643654832917317694258
123456789579382164846719532782163495431925876965847321298571643654238917317694258
123456789579238164846917532731869425485721396962543871298175643654382917317694258
123456789579832164846917532761349825485721396932568471298175643654283917317694258
123456789579382164846917532731869425485721396962543871298175643654238917317694258
123456789579283164846917532761349825485721396932568471298175643654832917317694258
123456789579238164846917532761849325435721896982563471298175643654382917317694258
123456789579832164846917532781369425435721896962548371298175643654283917317694258
123456789579382164846917532761849325435721896982563471298175643654238917317694258
123456789579283164846917532781369425435721896962548371298175643654832917317694258
123456789579832164846719532731968425485127396962345871298571643654283917317694258
123456789579238164846719532761943825485127396932865471298571643654382917317694258
123456789579283164846719532731968425485127396962345871298571643654832917317694258
123456789579382164846719532761943825485127396932865471298571643654238917317694258
123456789579832164846719532761948325435127896982365471298571643654283917317694258
123456789579238164846719532781963425435127896962845371298571643654382917317694258
123456789579283164846719532761948325435127896982365471298571643654832917317694258
123456789579382164846719532781963425435127896962845371298571643654238917317694258

JPF

by **daj95376** » Mon Apr 30, 2007 7:14 pm

Combining my PM (above) with JPF's 64 solutions, and every candidate in the PM appears in at least one solution. If I'm not mistaken, then the PM can't be reduced any further. (Thanks JPF!)

by **Havard** » Tue May 01, 2007 1:57 am

I have a search going and have two more results to report:

48 solutions:

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

32 solutions:

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

Havard

by **Havard** » Tue May 01, 2007 2:07 am

it is a bit freaky that the last minimum solutions discovered are:
80 - 64 - 48 - 32, since each of these can be derived by a -16 (80-16 = 64, 64-16=48 etc). Does this mean that we can find a grid with 16 solutions but none with 1 (only with 16-16=0)???

`

Havard

by **udosuk** » Tue May 01, 2007 5:47 am

This looks like a stupid idea but has anyone studied the following pattern:

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

And worked out the number of unavoidables in there? Perhaps the factor of 16 has something to do about it?

I'm no expert in unavoidables (Red Ed, coloin, Moschopulus are the experts), so nothing too insightful I can bring here...

by **JPF** » Tue May 01, 2007 8:56 am

Havard wrote:I have a search going and have two more results to report:
48 solutions
32 solutions
...

Interesting ...

udosuk wrote:This looks like a stupid idea but has anyone studied the following pattern:
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|. . . . . .|. . .|. . .

And worked out the number of unavoidables in there? Perhaps the factor of 16 has something to do about it?

Note that there is no valid puzzle with this pattern

Code: Select all: 0X0 XXX 0X0

see here

JPF

The New Sudoku Players' Forum

Ask for some patterns that they don't have puzzles.