Yet another sudoku property wanted

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

Yet another sudoku property wanted

Postby Mauricio » Mon Nov 12, 2007 10:18 am

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
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Ruud » Mon Nov 12, 2007 10:45 am

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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Mauricio » Mon Nov 12, 2007 11:28 am

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 ..."
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Ruud » Mon Nov 12, 2007 11:52 am

Mauricio wrote: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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby re'born » Mon Nov 12, 2007 2:36 pm

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?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby gsf » Mon Nov 12, 2007 8:29 pm

re'born wrote: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
Last edited by gsf on Mon Nov 12, 2007 5:58 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Mon Nov 12, 2007 9:23 pm

gsf wrote:
re'born wrote: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 |
+-------+-------+-------+
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby RW » Mon Nov 12, 2007 9:36 pm

Mauricio wrote:
gsf wrote:
re'born wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby re'born » Mon Nov 12, 2007 10:41 pm

gsf wrote:
re'born wrote: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).
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Ruud » Mon Nov 12, 2007 11:33 pm

RW wrote: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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby JPF » Tue Nov 13, 2007 2:12 am

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

Postby RW » Tue Nov 13, 2007 5:49 am

Ruud wrote:
RW wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Wed Nov 14, 2007 9:07 am

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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Wed Nov 14, 2007 10:07 am

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.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby gsf » Wed Nov 14, 2007 10:18 am

Mauricio wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next

Return to General