Puzzles needing lots of locked candidates

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

Puzzles needing lots of locked candidates

Postby 999_Springs » Sun Apr 15, 2007 3:17 pm

There are puzzles which cannot be solved with singles only, but can be solved with singles and locked candidates type 1. Out of these puzzles, which require the most locked candidates and what is the maximum number of locked candidates needed to solve such a puzzle?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby tarek » Sun Apr 15, 2007 4:21 pm

I think there are several threads which such examples (but not direclty addressing your question)....

The one which I remeber last is in these fora

search for MrHamilton and/Or travelling pairs.....


tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Mike Barker » Mon Apr 16, 2007 3:19 am

Deleted post
Last edited by Mike Barker on Tue Apr 17, 2007 8:26 pm, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

re: needing lots of "locked candidates"

Postby Pat » Sun Apr 22, 2007 12:31 pm

999_Springs wrote:There are puzzles which cannot be solved with singles only,
but can be solved with singles and locked candidates type 1.

Out of these puzzles,
which require the most locked candidates
and what is the maximum number of locked candidates needed to solve such a puzzle?



good question!
let's get this started with some examples --


#1
Pat (2007.Feb.28) wrote:
      [ 65 clues ]
Code: Select all
 9 7 . | . 4 8 | 3 1 6
 3 6 8 | 1 . 7 | . 4 .
 1 4 . | . 3 6 | 7 . 8
-------+-------+------
 2 1 9 | 3 7 5 | 8 6 4
 8 3 6 | 4 1 9 | 2 5 7
 7 5 4 | 8 6 2 | 1 3 9
-------+-------+------
 5 . 7 | 6 . 3 | 4 8 1
 4 8 3 | 7 . 1 | 6 . .
 6 . 1 | . 8 4 | . 7 3




#2
Pat (2007.Jan.18) wrote:
gsf (2007.Jan.17) wrote:
      [ 30 clues ]
Code: Select all
 7 4 . | 3 . 9 | . 5 1
 . 2 . | . . . | . 8 .
 5 . . | . 2 . | . . 3
-------+-------+------
 2 . . | 6 . 3 | . . 7
 . . . | . . . | . . .
 1 . . | 2 . 5 | . . 6
-------+-------+------
 6 . . | . 3 . | . . 2
 . 3 . | . . . | . 7 .
 9 5 . | 1 . 7 | . 3 8




#3
Pat (2006.Oct.12) wrote:
Heuresement (2006.Oct.6) wrote:
The Times (2006.Jul.27) wrote:
      qualification-puzzle

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




#4
Pat (2006.Jun.4) wrote:
RW (2006.May.29) wrote:
      #3

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




#5
Pat (2007.Jan.1) wrote:
rubylips (2005.Apr.18) wrote:
      [ 22 clues ]
Code: Select all
 . 6 . | . . 4 | 9 1 .
 . . 4 | . . . | . . .
 3 . . | 5 . 8 | . . .
-------+-------+------
 . . . | . 4 . | . . 3
 5 . . | . . . | . . 7
 2 . . | . 9 . | . . .
-------+-------+------
 . . . | 7 . 2 | . . 5
 . . . | . . . | 8 . .
 . 1 3 | 8 . . | . 6 .




#6
Eioru (2007.Apr.16) wrote:
      [ 23 clues ]
Code: Select all
 7 . . | 1 . 5 | . . 3
 . 9 . | . . . | . 5 .
 . . . | 3 . 8 | . . .
-------+-------+------
 4 . 3 | . . . | 7 . 2
 . . . | . . . | . . .
 8 . 2 | . . . | 9 . 4
-------+-------+------
 . . . | 7 . 6 | . . .
 . 3 . | . . . | . 6 .
 1 . . | 4 . 9 | . . .




#7
Eioru (2007.Apr.20) wrote:
      [ 22 clues ]
Code: Select all
 . . . | 2 . 8 | . . 7
 . 4 . | . . . | . 9 .
 . . . | 5 . 6 | . . .
-------+-------+------
 3 . 7 | . . . | 6 . .
 . . . | . . . | . . .
 6 . 5 | . . . | 1 . 2
-------+-------+------
 . . . | 4 . 5 | . . .
 . 1 . | . . . | . 3 .
 9 . . | 7 . 2 | . . 4


User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby 999_Springs » Sun Apr 22, 2007 5:03 pm

I chucked the seven puzzles into my solver. The first six didn't need very many. The last puzzle needed 17 locked candidate steps.

Are there any puzzles around with 20+?

Pat wrote:[65 clues]
Code: Select all
 9 7 . | . 4 8 | 3 1 6
 3 6 8 | 1 . 7 | . 4 .
 1 4 . | . 3 6 | 7 . 8
-------+-------+------
 2 1 9 | 3 7 5 | 8 6 4
 8 3 6 | 4 1 9 | 2 5 7
 7 5 4 | 8 6 2 | 1 3 9
-------+-------+------
 5 . 7 | 6 . 3 | 4 8 1
 4 8 3 | 7 . 1 | 6 . .
 6 . 1 | . 8 4 | . 7 3

I don't think that is the maximum because I remember trying to solve a puzzle rated "Easy" and with 11 cells left there were no singles but there was a locked candidate type 1 which solved it. I don't have the puzzle.
(Although I might have just made a mistake writing down the candidates, but I do remember doing the puzzle.)
Is there such a puzzle around?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby daj95376 » Sun Apr 22, 2007 5:25 pm

999_Springs wrote:I chucked the seven puzzles into my solver. The first six didn't need very many. The last puzzle needed 17 locked candidate steps.

Your results don't match mine. If I have Naked/Hidden Singles before Locked Candidate (1), my solver only finds four LC1s. Even if I place LC1s first in my hierarchy, I only encounter 11 LC1s.

Pat, what were your results for puzzle #7 -- inluding heirarchy?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

re: #7

Postby Pat » Thu Apr 26, 2007 6:47 am

daj95376 wrote:
999_Springs wrote:The last puzzle needed 17 locked candidate steps.


Your results don't match mine -- my solver only finds four LC1s.


thanks, daj95376!
i did it on paper and used 7,
now i'll have to go back and try for less --

~ Pat
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

re(2): #7

Postby Pat » Fri Apr 27, 2007 9:15 am

well, i took some time to re-do #7, now knowing that 7 are more than the minimum needed.
and yes, this time i found a solution-path using only 5 box-to-line exclusions.
    not yet 4 -- will i be stubborn enough to try again??
    or will i surrender and get some help from the computer??
doing it on paper, i never know if i found the simplest solution-path.
    daj95376, could you please tell us a little about your software -- how does it find the simplest solution-path?? checking all the possible combinations??
~ Pat
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby re'born » Fri Apr 27, 2007 11:23 am

The best I could do was 4 LC steps.

At the start use LC 3 times on row 5, candidates 1,3,4. Then place all available singles. An LC in box 5 for 9 then leaves only singles.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: re(2): #7

Postby daj95376 » Fri Apr 27, 2007 2:21 pm

Pat wrote:daj95376, could you please tell us a little about your software -- how does it find the simplest solution-path??

Pat: My solver is not sophisticated. I simply reordered the hierarchy to Singles and Locked Candidate (1) before any other techniques. The results then match those of rep'nA.

FWIW: I'm hoping to write a new version of my solver that'll be based on bitmaps for most of the solving techniques. If anyone knows of a good way to do XY-Wings and XYZ-Wings with bitmaps, please drop me a private message. TIA!!!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: re(2): #7

Postby gsf » Fri Apr 27, 2007 3:50 pm

Pat wrote:doing it on paper, i never know if i found the simplest solution-path.
    daj95376, could you please tell us a little about your software -- how does it find the simplest solution-path?? checking all the possible combinations??
~ Pat

interesting
unless the coding specifically avoids it most sudoku algorithms are probably biased to input puzzle permutations
for i 0 .. 80 for i 1 .. 81 etc
in my solver with -S (step) on, it finds 5 box-line, committing each one separately before checking for the next
committing in a different order can give slightly different step results
one way around is to randomize the selection order and do multiple runs

my solver code is riddled with 0..80 0..8 0..27 0..2 loops
randomizing those would be a debugging (and testing) nightmare

an alternnative is to throw a bunch of isomorphic permutations at the solver and select those that minimize/maximize moves
this is how suexrat determines its ratings

you can do this multi-stage with my solver (as always grab the latest version)

for this problem minimizing the default R rating should do
first look at the range of ratings for ~100 permutations
Code: Select all
g -r1 -J99 -S -f'%v %Q' ...2.8..7.4.....9....5.6...3.7...6...........6.5...1.2...4.5....1.....3.9..7.2..4

-r1 sets the pseudo random seed so that results are reproducable between runs

from this it looks like 30 is the lowest
use that to filter lower ratings from the same sample
Code: Select all
g -e 'R<30' -r1 -J99 -S -f'%v %Q' ...2.8..7.4.....9....5.6...3.7...6...........6.5...1.2...4.5....1.....3.9..7.2..4

this results in
Code: Select all
3.7...6..6.5...12..........9..2.7.4....5.4....1......3.4......9...8.2.7....6.5...    29 FNB         C22.m/F9.56/N2.3/B4.13.13
.........8.6....252.5....74.9....3..7..2...4....16.....4....1.....57.......63..9.    29 FB          C22.m/F9.59/B5.19.19
..........86...25..25...74.9.......3...1.6....7.2..4.....6.39.....5.7...4.......1    29 FB          C22.m/F9.59/B5.19.19

so we can get 4 box-line with rating 29
next see if that can be bettered over a larger sample
Code: Select all
g -e 'R<29&&B<5' -r1 -J9999 -S -f'%v %Q' ...2.8..7.4.....9....5.6...3.7...6...........6.5...1.2...4.5....1.....3.9..7.2..4

and there's one
Code: Select all
.....6.37...2.1.65..........274...9..54..........3.1......9.4...827......65......    28 FNB         C22.m/F8.56/N2.3/B4.13.13

F8: 8 naked singles, N2: 2 hidden singles, B4: 4 box-line

now the -p cyclic permutation option can be used to map the move
although randomizing the inner loops would be a pain, all of my -v trace output is done in
one place, so, given the cyclic permutations that map one puzzle to another, that permutation
can be used to map the -v output (showing the move trace) relative to another puzzle

first determine the cyclic permutation from the "minimal" puzzle (isomorphic to the original)
Code: Select all
g -p ...6..3.7...12.6.5.........2.7.4.9.......3.1.5.4...........9.4.6.5......8.2.7....

which produces
Code: Select all
r(149)(267)(358)c(168259347)

(all of this math keeps the coding chops in shape)
then run the solver on the "minimal" puzzle with the trace output mapped
Code: Select all
g -S -v2 -p'r(149)(267)(358)c(168259347)' ...6..3.7...12.6.5.........2.7.4.9.......3.1.5.4...........9.4.6.5......8.2.7....

to get
Code: Select all
[1]  F1  [86]=9
         box-line 3 b/2    [56][55][54][55][52][53]
     B3  [56][55][54]^3
         box-line 1 b/2    [56][55][54][57][59][58]
     B3  [56][55][54]^1
         box-line 4 b/2    [56][55][54][57][59][58]
     B4  [56][55][57][58]^4
     F1  [56]=7
     N2  [68]=7 [48]=4
     F3  [46][64]=1 [66]=3
     F2  [66]=4 [65]=7
     N1  [64]=3
         box-line 9 b/2    [45][65][55][95][85][75]
     B3  [45][65][55]^9
     F5  [65][84]=8 [62]=9 [85]=6 [89]=5
     F10 [44]=9 [49][52][97]=8 [42]=2 [54][69]=6 [58][25]=5 [28]=1
     F9  [45]=5 [55][78]=2 [98]=6 [93][69]=3 [68]=8 [62]=7 [27]=4
     F16 [59][77][63][25]=9 [95][79][65]=1 [92]=5 [87]=7 [75][22]=3
         [72][23]=6 [73]=8 [63][67]=2
     F9  [57]=3 [55][83][65]=4 [53]=1 [85]=2 [75]=7 [67]=5 [65]=8
     S

which shows the original minimal box-line application order from the given sample

are you sorry you asked about someone's solver?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby daj95376 » Fri Apr 27, 2007 7:09 pm

gsf, Your Monte Carlo approach using isomorphic permutations is probably sufficient to find a solution with the minimal number of Locked Candidates (1) for this puzzle, but only a BFS approach using Singles and Locked Candidates (1) is going to guarantee a simplest-solution path.

My original reply and count was simply to let 999_Springs know that he might have a problem in his solver if it needed 17 Locked Candidates (1) to solve the puzzle. I wasn't trying to say that I'd found the fewest -- only significantly fewer, even when I put LC1s first in the hierarchy.

Sudoku doesn't seem to fit a minimal-path solution approach since there's no agreement on technique hierarchy -- let alone what constitutes a minimal-path.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Fri Apr 27, 2007 8:18 pm

daj95376 wrote:I wasn't trying to say that I'd found the fewest -- only significantly fewer, even when I put LC1s first in the hierarchy.

Sudoku doesn't seem to fit a minimal-path solution approach since there's no agreement on technique hierarchy -- let alone what constitutes a minimal-path.

right
we can get away with a bit here because singles before box-line is a reasonable assumption
so really the only choice is the order to apply the 4 box-lines, and a few thousand random
samples were sufficient for that

as far as constraint order, the best a solver can do is make that programmable
then the only drawback will be constraints not programmed
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ravel » Sat Apr 28, 2007 11:43 am

gsf wrote:we can get away with a bit here because singles before box-line is a reasonable assumption
Yes, but like Sudoku Explainer suggests, direct hidden pairs can be ranked before box-line.
Especially when you solve without (or only a few) pencilmarks, hidden pairs are often easier to spot than box-line and many would apply them earlier, when they directly lead to a single.
You can see in SE, that at the beginning you have 5 hidden pairs (one leading to the 6 in box 5) and 6 box-lines. The whole puzzle can be solved with singles and direct hidden pairs only without using any box-line.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Sat Apr 28, 2007 3:23 pm

ravel wrote:Yes, but like Sudoku Explainer suggests, direct hidden pairs can be ranked before box-line.
I don't fool with SE much because of its performance
but I stated
gsf wrote:as far as constraint order, the best a solver can do is make that programmable

so, e.g., anyone who prefers hidden pair before box-line can use
Code: Select all
-qT1H1H2B...
to analyze puzzles with my solver

what this really means is that problem statements like "how many x constraint (method/technique) steps"
must be qualified by a constraint order
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next

Return to General