The New Sudoku Players' Forum

[Mauricio]

A challenge.
What is the sudoku with the least number of clues such that it is not solvable using singles only, but if you add any one more clue to it, then it is solvable using singles only.
A starter:

Code: Select all

32 clues
+-------+-------+-------+
| . . . | . . . | . . 1 |
| . . . | . 2 3 | . 4 5 |
| . 4 5 | 6 1 7 | 8 3 . |
+-------+-------+-------+
| . . 7 | . . . | . . 6 |
| . 2 6 | 1 . 4 | 9 . 8 |
| 1 . . | 5 . 6 | . . . |
+-------+-------+-------+
| . 5 . | . . 8 | . 6 3 |
| . 9 . | . . . | 5 . . |
| 7 . 3 | . . . | 2 . . |
+-------+-------+-------+

Sorry for the non symmetry, I could later organise them for symmetry classes if enough replies are given.
Similar topics:
http://forum.enjoysudoku.com/viewtopic.php?t=3828
http://forum.enjoysudoku.com/viewtopic.php?t=4986

[Ruud]

I think the answer will be 17.

It should be easy to check Gordon's collection, filter out the non-trivial puzzles and check if any additional clue will make it trivial.

[Mauricio]

I will try that, Ruud; but no minimal puzzle with that property has crossed my path yet.

Beware (everybody) that the sense of "any one more clue ..." is "every other clue ..."

[Ruud]

Beware (everybody) that the sense of "any one more clue ..." is "every other clue ..."

I see. Now I'm pretty sure the answer will be more than 17. It wouldn't harm to test the collection anyway.

[re'born]

So is it correct to say that you're looking for a minimal sudoku with singles backdoor size 2 such that any additionaly given reduces the backdoor size to 1?

[gsf]

So is it correct to say that you're looking for a minimal sudoku with singles backdoor size 2 such that any additionaly given reduces the backdoor size to 1?

I think its: a sudoku with singles backdoor size 1 such that adding any clue reduces to singles backdoor size 0 (solvable by singles)
[edit minimal dropped as noted by maurico]

here is a filter expression for my solver:

Code: Select all

-qFN -e "M==1 && M1==(81-C)" -f"%v # %(C)x"

where:
-qFN : naked + hidden singles constraints
M==1 : backdoor size 1
C : #clues
M1==(81-C) : #backdoor cells equals the number of non-clues, or, in other words, every empty cell is a singles backdoor
-f : list the matching puzzle and #clues

[Mauricio]

So is it correct to say that you're looking for a minimal sudoku with singles backdoor size 2 such that any additionaly given reduces the backdoor size to 1?

I think its: a minimal sudoku with singles backdoor size 1 such that adding any clue reduces to singles backdoor size 0 (solvable by singles)

Neither is.

I can't see the equivalence between not being solvable by singles and having a backdoor size 1 (there is just one implication, having singles backdoor size 1=> not being solvable by singles).
[Edit]: After some work, the equivalence can be proven. Just drop the word "minimal", ie, it is equivalent to say " a sudoku with singles backdoor size 1 such that adding any clue reduces to singles backdoor size 0".[/Edit]

Besides, I never asked the puzzle to be minimal, in fact, I have not seen any minimal puzzle with the property I asked for.

I checked all puzzles in Gordon's list (47442 puzzles), and none qualified.

Improvement:

Code: Select all

31 clues
+-------+-------+-------+
| . . . | . . 1 | . . 2 |
| . . 1 | . 3 . | . . . |
| 4 5 . | 2 . . | 1 6 . |
+-------+-------+-------+
| . . 7 | . . . | 8 4 . |
| 8 . 6 | . . 3 | . 2 5 |
| 9 . . | . 2 . | . . . |
+-------+-------+-------+
| . 3 4 | 6 . . | . . 7 |
| 1 . . | . 9 . | . 3 . |
| 6 . . | 3 . 4 | 5 . 8 |
+-------+-------+-------+

[RW]

So is it correct to say that you're looking for a minimal sudoku with singles backdoor size 2 such that any additionaly given reduces the backdoor size to 1?

I think its: a minimal sudoku with singles backdoor size 1 such that adding any clue reduces to singles backdoor size 0 (solvable by singles)

Neither is.

I can't see the equivalence between not being solvable by singles and having a backdoor size 1 (there is just one implication, having singles backdoor size 1=> not being solvable by singles).

But there is an equivalence between not being solvable by singles, but being solvable by singles with one added clue and having a backdoor size 1.

Anyway, interesting property. I recall some puzzles posted here that start with a non-single move and the rest is singles. Those should be good candidates for this thread, but I can't remember where I have seen these...

RW

[re'born]

So is it correct to say that you're looking for a minimal sudoku with singles backdoor size 2 such that any additionaly given reduces the backdoor size to 1?

I think its: a sudoku with singles backdoor size 1 such that adding any clue reduces to singles backdoor size 0 (solvable by singles)
[edit minimal dropped as noted by maurico]

Oops. I had a little brain fart there. When I was writing minimal I was thinking in terms of the number of clues, not in the generally accepted sense of unable to remove a clue and still have a valid puzzle and I somehow shifted my backdoor sizes by 1. I'll just crawl back into my hole now and hope nobody can see me (Adam shuts his eyes so nobody can see him).

[Ruud]

I recall some puzzles posted here that start with a non-single move and the rest is singles. Those should be good candidates for this thread, but I can't remember where I have seen these...

Since every additional clue must produce a trivial puzzle, every one of those clues must avoid the non-singles step. The challenge is more difficult than one (including me) would imagine at first glance.

The upper limit is 70 clues. Anything above that would be trivial.

Example:

Code: Select all

3 . 4|2 6 1|7 5 .
2 1 5|9 7 8|4 6 3
7 6 .|4 3 5|. 1 .
-----+-----+-----
8 3 7|6 9 4|1 2 5
1 . .|3 5 7|6 8 4
4 5 6|1 8 2|3 9 7
-----+-----+-----
9 4 3|8 2 6|5 7 1
6 7 .|5 1 3|9 4 .
5 . 1|7 4 9|. 3 6

Ruud

Warning: this post contains a claim without any proof. You could help this forum by providing this proof.

[JPF]

The upper limit is 70 clues. Anything above that would be trivial.

Warning: this post contains a claim without any proof. You could help this forum by providing this proof.

Back to the old good posts

JPF

[RW]

I recall some puzzles posted here that start with a non-single move and the rest is singles. Those should be good candidates for this thread, but I can't remember where I have seen these...

Since every additional clue must produce a trivial puzzle, every one of those clues must avoid the non-singles step. The challenge is more difficult than one (including me) would imagine at first glance.

I can imagine that it is difficult. But any puzzle that satisfies the demands of this thread must start with one (ore more) non singles move and after the first single is solved, then the rest must be singles. So if there is a collection of puzzles like this somewhere, it wouldn't hurt to check them. Also, you can all speed up your search engines a lot if you immediately discard any puzzle that start with a single and discard any puzzle that after solving one or more singles comes to a point where no singles are available.

RW

[gsf]

Code: Select all

# 29 clues

. . . | 5 4 . | 2 . 3
. . . | . . 9 | 4 6 8
. 4 2 | . . 8 | . . .
------+-------+------
. . . | . . 3 | . 5 .
. 7 9 | . 8 . | . . .
. 3 . | . . 1 | 6 . 4
------+-------+------
. . . | . . . | . 7 .
. 2 7 | . 6 4 | . . .
1 . . | . 3 . | 9 4 .


I used these options in my solver to first filter pseudo random generated puzzles,
and then to refine successive off-on generations

Code: Select all

-qFN -e 'M==1&&min((81-C-M1)*100+C)' -f'%v # %(M)x %(C)x %(M1)x %(81-C-M1)x'

-qFN : singles only
M==1 : backdoor size 1
min(...) : only list puzzles that produce a smaller values for ... than the previous listed puzzle
C : #clues
M1 : #backdoors
(81-C-M1) : 0 for desired puzzles

[Mauricio]

Very impresive, gsf.

2 siblings to your puzzle, with 29 clues each:

Code: Select all

7..5..2.3.....9468.42..8........3.5..79.8.....3...16.4.......7..27.6....1...3794.
...5..2.3.....9468.42..8........3.5..79.8.....3.7.16.4.......7..27.6....1...3794.


How long took to generate it? I remember that my computer worked ~1 hour to generate that 31.

[gsf]

2 siblings to your puzzle, with 29 clues each:

Code: Select all

7..5..2.3.....9468.42..8........3.5..79.8.....3...16.4.......7..27.6....1...3794.
...5..2.3.....9468.42..8........3.5..79.8.....3.7.16.4.......7..27.6....1...3794.


How long took to generate it? I remember that my computer worked ~1 hour to generate that 31.

the hardest part was understanding the property

I let this generation fly for about a day

Code: Select all

-gp -mr100 -qFN -e 'M==1&&min((81-C-M1)*100+C)' -f'%v # %(M)x %(C)x %(M1)x %(81-C-M1)x'


and it produced

Code: Select all

...5..2.3.....9.68.42..8....1.....5..79.8.....3.7..6.4.......7..27.6........3.94. # 1 25 50 6


which has 6 non-backdoor empty cells
then 4 successive

Code: Select all

-go{-2+3} -qFN -e 'M==1&&min((81-C-M1)*100+C)' -f'%v # %(M)x %(C)x %(M1)x %(81-C-M1)x'


each ~5 min, led to the 29