The New Sudoku Players' Forum

[999_Springs]

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?

[tarek]

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

[Mike Barker]

Deleted post

[Pat]

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

[ 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

[ 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

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

#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

[ 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

[ 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

[ 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



[999_Springs]

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+?

[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?

[daj95376]

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?

[Pat]

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]

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

[re'born]

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.

[daj95376]

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

[gsf]

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?

[daj95376]

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.

[gsf]

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

[ravel]

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.

[gsf]

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

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