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

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

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

Postby 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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8373
Joined: 15 May 2006
Location: Berlin

Postby 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
Last edited by JPF on Sat Apr 28, 2007 11:10 am, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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 | . . .
udosuk
 
Posts: 2698
Joined: 17 July 2005

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

Postby 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...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby 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
Havard
 
Posts: 377
Joined: 25 December 2005

Postby 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.]
Last edited by daj95376 on Sun Apr 29, 2007 7:14 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby 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
Havard
 
Posts: 377
Joined: 25 December 2005

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

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

Postby 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
Havard
 
Posts: 377
Joined: 25 December 2005

Postby 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
Havard
 
Posts: 377
Joined: 25 December 2005

Postby 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...
udosuk
 
Posts: 2698
Joined: 17 July 2005

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

PreviousNext

Return to General