The New Sudoku Players' Forum

[coloin]

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

[Havard]

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

[JPF]

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

[udosuk]

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

[Havard]

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

[claudiarabia]

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?

[RW]

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

[coloin]

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

[Havard]

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

[coloin]

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

[Havard]

Apperantly JPF has come quite close already:

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!

Havard

[RW]

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

[Red Ed]

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

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.

[JPF]

...there are no puzzles with that template.

Great, that will save some cpu time.

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

Your french is perfect

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

[Havard]

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