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

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?
Once upon a time I was a teenager who was active on here 2007-2011
ocean and eleven should have paired up to make a sudoku-solving duo called Ocean's Eleven
999_Springs

Posts: 438
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

The one which I remeber last is in these fora

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

tarek

tarek

Posts: 2761
Joined: 05 January 2006

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"

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 `

Pat

Posts: 3676
Joined: 18 July 2005

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?
Once upon a time I was a teenager who was active on here 2007-2011
ocean and eleven should have paired up to make a sudoku-solving duo called Ocean's Eleven
999_Springs

Posts: 438
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

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

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

Pat

Posts: 3676
Joined: 18 July 2005

### re(2): #7

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

Pat

Posts: 3676
Joined: 18 July 2005

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

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

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

gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

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

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

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

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