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 » Tue May 01, 2007 11:15 am

Indeed

Whatever the unavoidable sets are left in the solution grids - despite the low solution number they are disjoint enough to need 3 clues [i.e. no completions with 2 clues in either the 64 or 32 grid solution subgrids]there are plenty of valid puzzles with + 3 clues ...
... and the solutions looks like there is possibly 4 or 8-fold symmetry in them.

I did recall many of JPFs subgrids to be completable in 2 clues.

How many templates/grids have you searched to get the 32 grid solution subgrid ?

Perhaps better /easier to show that +1 clues is doable/impossible
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
rather than the +0 template.

To solve with +0 clues
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|. . .
. . .|. . .|. . .
there would have to be no unavoidable sets solely within these clues.

The ones which catch you out are the ones which cover 3 boxes
Code: Select all
. . .|. . .|. . .
. . .|. . .|. . .
. . .|1 2 .|. . .
-----+-----+-----
. 1 .|2 . .|. . .
. 2 .|. 1 .|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Havard » Tue May 01, 2007 12:07 pm

coloin wrote:How many templates/grids have you searched to get the 32 grid solution subgrid ?


Well, my program now examines about 1000 grids per second, and I have left it on for two days now, so roughly 172800000 grids so far...:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby JPF » Tue May 01, 2007 8:06 pm

Havard wrote:Well, my program now examines about 1000 grids per second, and I have left it on for two days now, so roughly 172800000 grids so far... :)Havard

I presume that you make a random search...
I'm not sure that there are so many essentially-different subgrids with this pattern.

You must have many equivalent subgrids in your 172800000+ trials.

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

Postby udosuk » Tue May 01, 2007 9:26 pm

coloin wrote:To solve with +0 clues
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|. . .
. . .|. . .|. . .
there would have to be no unavoidable sets solely within these clues.

The ones which catch you out are the ones which cover 3 boxes
Code: Select all
. . .|. . .|. . .
. . .|. . .|. . .
. . .|1 2 .|. . .
-----+-----+-----
. 1 .|2 . .|. . .
. 2 .|. 1 .|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

Thanks coloin, you've got my point.

Also unavoidable sets which cover 4 boxes:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | 1 . 2 | . . .
-------+-------+-------
 . 1 . | 2 . . | . . .
 . 2 . | . . . | 1 . .
 . . . | . . 1 | 2 . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

And 5 boxes:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | 1 2 . | . . .
-------+-------+-------
 . 1 . | 2 . . | . . .
 . 2 . | . . . | 1 . .
 . . . | . . 1 | 2 . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . 1 2 | . . .
 . . . | . . . | . . .

And then there are ones involving 3 or more digits...:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Havard » Tue May 01, 2007 9:50 pm

JPF wrote:
Havard wrote:Well, my program now examines about 1000 grids per second, and I have left it on for two days now, so roughly 172800000 grids so far... :)Havard

I presume that you make a random search...
I'm not sure that there are so many essentially-different subgrids with this pattern.

You must have many equivalent subgrids in your 172800000+ trials.

JPF


The search is recursive, trying all possibilities for all numbers in all cells. I guess 172800000 is the number of nodes visited. I have found a lot of 32 solution ones, but none so far with any less...

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby claudiarabia » Tue May 01, 2007 11:03 pm

udosuk"][quote="coloin wrote:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | 1 2 . | . . .
-------+-------+-------
 . 1 . | 2 . . | . . .
 . 2 . | . . . | 1 . .
 . . . | . . 1 | 2 . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . 1 2 | . . .
 . . . | . . . | . . .

And then there are ones involving 3 or more digits...:!:


Is there a real puzzle which contains a BUG-Lite (Unique Loop) lik this with 10 cells involved as a necessary solving strategy?
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby RW » Wed May 02, 2007 12:04 pm

udosuk wrote:And then there are ones involving 3 or more digits...

When it comes to unavoidable sets, the truth is usually not very simple. Here's all unavoidables in one solution to Havard's 32 and the digits involved:
Code: Select all
 *----------------------------------------------------------*
 | 1    2      3  |   4       5       6  |    7      8   9  |
 | 6    7      9  | bg8    beh2   begh3  |    5      4   1  |
 | 5    8      4  |  d7      d9      d1  |    6      3   2  |
 |----------------+----------------------+------------------|
 | 7 cfh3  aefg1  |   9  bcefh4  bcefh2  | cfh8  aefg6   5  |
 | 2 cfh4  cefg5  |acd6  cdefg7  cefgh8  | cfh9 acefg1   3  |
 | 8 cfh9 acefg6  |acd1  cefgh3  cdefg5  | cfh2  cefg7   4  |
 |----------------+----------------------+------------------|
 | 4    1      7  |  d5      d6      d9  |    3      2   8  |
 | 9    6      2  | bg3   begh8    beh4  |    1      5   7  |
 | 3    5      8  |   2       1       7  |    4      9   6  |
 *----------------------------------------------------------*

a - 16
b - 2348
c - 123456789
d - 15679
e - 12345678
f - 123456789
g - 1345678
h - 23489

Only one simple unavoidable, the rest are quite complex. Interesting that even though the puzzle has so few solutions, it can't be solved with less than three clues.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Wed May 02, 2007 12:37 pm

JPF wrote:I'm not sure that there are so many essentially-different subgrids with this pattern.
Therefore a simple matter of generating them all and confirming that no solution exists.....[?]

This could apply to all our potential patterns

Could we see all the 32 solution subgrids ? - there is a good chance that they are all similar

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Havard » Thu May 03, 2007 9:19 am

here are a few:

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



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


Code: Select all
. 2 3|4 5 6|. . 9
. . .|. . .|. 5 4
8 4 .|. . .|. 1 .
-----+-----+-----
. . .|. . .|. . .
2 . .|. . .|. . 6
9 . .|. . .|. . 7
-----+-----+-----
3 8 .|. . .|. 4 .
7 1 2|. . .|. 6 8
. 5 .|1 8 9|. 7 2
Havard
 
Posts: 377
Joined: 25 December 2005

Postby coloin » Thu May 03, 2007 10:23 am

Thanks, - the 4 subgrids with 32 sols that you have posted are all different !
How close are you with this perhaps more achievable one ?
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

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Havard » Thu May 03, 2007 10:31 am

Apperantly JPF has come quite close already:

udosuk wrote: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 | . . .


I can start a search and let you know in a few days!:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby RW » Thu May 03, 2007 6:26 pm

Thanks Havard for the 32s. Just out of curiosity, why do you submit the grids with those particular cells filled? You remove some clues from the template, yet they are far from minimal... For example from the second grid you can remove at least 9 clues and still have 32 solutions:

Code: Select all
 *-----------*
 |...|.56|..9|
 |.5.|...|..4|
 |7..|...|.3.|
 |---+---+---|
 |2..|...|...|
 |3..|...|..6|
 |4..|...|..1|
 |---+---+---|
 |.92|...|.1.|
 |61.|...|9.3|
 |5..|9.2|.7.|
 *-----------*


RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Red Ed » Thu May 03, 2007 7:15 pm

Havard wrote:I can start a search and let you know in a few days!:D
I shouldn't bother: there are no puzzles with that template.

udosuk had the right idea: ignore the givens and just search for a way of filling in the blanks (the inner cross shape) such that there are no unavoidables. An exhaustive depth-first search, with some additional trimming by testing partial fills for isomorphism & unavoidables, finishes in less than 2 hours on my computer.

Of course this result means that there are no puzzles with the original template, sans central clue, either.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Thu May 03, 2007 8:15 pm

Red Ed wrote:...there are no puzzles with that template.

Great, that will save some cpu time.

Red Ed wrote:Of course this result means that there are no puzzles with the original template, sans central clue, either.

Your french is perfect:)

Red Ed wrote:ignore the givens and just search for a way of filling in the blanks (the inner cross shape) such that there are no unavoidables. An exhaustive depth-first search, with some additional trimming by testing partial fills for isomorphism & unavoidables,...

Could you give us some more clues:?:
Thanks.

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

Postby Havard » Thu May 03, 2007 9:53 pm

RW wrote:Thanks Havard for the 32s. Just out of curiosity, why do you submit the grids with those particular cells filled? You remove some clues from the template, yet they are far from minimal... For example from the second grid you can remove at least 9 clues and still have 32 solutions:
RW


To explain that I would have to explain how the search works. Basically once the whole template is filled with a combination of placed clues and clues that are a direct result of the placed clues the generator spits out a sudoku. No effort is then done to minimize the output. It is the same problem you get if you have a generator that keeps adding clues until you have 1 solution. You will almost always get a sudoku that has a lot of excess clues.:)

I also second JPF request. How on earth can you, Red Ed, do a complete search in two hours? I am amazed and impressed to say the least!!! My search (trying all possibilities recursivly with a logic solver to prune the search tree and some tricks to avoid isomorphs) is working quite fast (1500 tries per sec now) and the best estimate I have there is that it will be finished in 5 years!:) So please enlighten us!

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

PreviousNext

Return to General