The New Sudoku Players' Forum

[tarek]

You're right RW, you need a different process to count NEEDED pointed pairs, my small modification would count fruitful pointing pairs not the Needed pointing pairs.

I still can't understand why do you need to know the NEEDED steps if you are not using these pointing pairs only, you are using any Fruitful pointing pair you may see, which as you pionted although not needed, it would shorten the solution path.

If you are looking for fruitful pointing pairs then I can understand how an experienced player would use them to shorten a puzzle & therefore the steps should have a different weighting.

tarek

[Ruud]

This is how I see it:

The modification suggested by Tarek is the way most computer solvers work.

Now what if we find 2 pointing pairs in a step? Or more? It could be that #1 will advance the puzzle a little further, but #2 is the one that really solves the puzzle, without the help of #1, which only makes it quicker.

The current counting method uses all pointing pairs. That is fair because they are there in the puzzle. Like RW, whose profession I do not know yet, I also often spot pointing pairs before singles.

I am now modifying the LowRater to perform a B1-requirement test. This test identifies all possible pointing pairs in the solving path, and then tries to solve the puzzle ignoring them one at a time. This will give us the number of pointing pairs that we cannot ignore. A test that tries every possible combination is better, but a little overkill at this time.

I will soon be able to report some results.

Ruud.

[RW]

Once again I'm making it more complicated, sorry... If you truly wish to simulate a human solver, then chained pointing pairs should count as only one step:

Code: Select all

-----|-----|* | *
* X X|. . .|X | X
* X X|. . .|X | X
-----+-----+-----
| X X|. . .|X | *
| * *|-----|--|--
| X X|. . .|X | *
-----+-----+-----
| . .|. . .|. | .
| . .|. . .|. | .
| . .|. . .|. A .

A computer would first exclude 'a' from r1c123, then in step 2 exclude 'a' from r456c1, in step 3 exclude 'a' from r5c79, in step 4 exclude 'a' from r1c9 solving r1c7=A. If you are a human solver that don't use pencilmarks (or memorize the previous pointing pairs in any other way) then the only way you can use the second, third and fourth pointing pair is by immidiately following up the first one. That's how slicing and dicing works, you don't stop as long as new lines are exposed. I don't mean that you should once again change your rating system, just worth thinking of for anybody who is about to develop the ultimate difficulty rating system.

RW

[ab]

I agree that's how humans solve puzzles, but it's very difficult to define steps like that. If you decide to follow the path that the first pointing pair takes you down, then rotating the puzzle will lead to a different solving path as will swapping rows or columns or reflecting the puzzle in a line of symmetry.

[Ocean]

Once again I'm making it more complicated, sorry... If you truly wish to simulate a human solver, then chained pointing pairs should count as only one step:

This is also the way I implemented step-counting, as a preliminary working algorithm. It gives the lowest possible step count, normally lower count than reported by Ruud and others. The advantage of using this method is that it is impossible to solve the puzzle in fewer steps (using F+B1 only), whichever solution path is chosen. For search purposes, I regarded this as a solid approach, to avoid false high counts. (But not necessarily more 'correct' than other counting principles!) (Ref also unanswered question in this post).

Anyway, implementation is simple: a small modification of Ruud's last 'technique' (extra loop added):

Here's the technique:

1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

Conditions:

a. The puzzle must be completely solved using the above steps (duuh)
b. The FN test must produce an (invalid) result.

Modified counting algorithm:
1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
---- If any new eliminations were done, go back to step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

I agree that's how humans solve puzzles, but it's very difficult to define steps like that. If you decide to follow the path that the first pointing pair takes you down, then rotating the puzzle will lead to a different solving path as will swapping rows or columns or reflecting the puzzle in a line of symmetry.

disagree.... the outlined counting algorithm (with extra loop added) should give exactly the same result for all isomorphic puzzle variations... (which might not be the case if only a single 'arbitrary' search scan is made)

[gsf]

Modified counting algorithm:
1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
---- If any new eliminations were done, go back to step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

can you list the steps labeld by { B N } constraint, something like this:

Code: Select all

1..3.52.8.2..4..6.3........8.......3.4.....1.7.......9........5.6..8..2.4.39.7..6
26:B7-B1-B1-B2-B2-B1-N5-N3-B3-B1-N1-B3-N1-B1-B1-B1-B2-B2-B2-B3-B3-B6-B4-B6-B6-B2


for independent verification
(this is probably not what you get because my B code does not detect naked singles
but it probably should -- any naked singles are counted at the end)

[tarek]

Modified counting algorithm:
1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
---- If any new eliminations were done, go back to step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

I have to disagree on this..........(how can you loop through 1 & 3 without hidden singles).... Any loop should always end by hidden singles... [what you're suggesting is similar to Ruud's previous counting IMO]

What I'm suggesting is a minor modification

Current (ab counting):
1. Pointing pairs (B1) (disregarding any naked single uncovered by 1 & 2)
2. Single elimination (disregarding any naked single uncovered by 1 & 2)
3. Hidden single Placement(including any naked single uncovered by 1&2 which has no other polyvalued cells in a shared sector)
4. loop (Step++)

Modification:
1. Single elimination (disregarding any naked single uncovered by 1 & 3)
2. Identefy Hidden singles1 (No action) (including any naked single uncovered by 1&3 that has no other polyvalued cells in a shared sector)
3. Pointing pairs (B1) (disregarding any naked single uncovered by 1 & 3)
4. Identefy Hidden singles2 (No action) (including any naked single uncovered by 1&3 that has no other polyvalued cells in a shared sector)
5. Hidden single Placement according to Point 4(including any naked single uncovered by 1&3 that has no other polyvalued cells in a shared sector)
6. loop (Step++)

The results should match & both should match ab's testing (TM)...
The modification would allow any hidden single uncovered as a direct result of point 3 ONLY to Count as a "Fruitful" pointing pair [which is not equivelanet to NEEDED or REQUIRED], No change in the number of Steps

Fruitful Pointing Pairs = (Hidden singles2-Hidden singles1)
Results are represented as Score=Steps + Fruitful Pointing pairs

Needed or required Pointing pairs (B1) can't be counted using this method, they can be counted using Pat's method which I highlighted earlier, which if needed has to be set up seperately [IMO I don't think it is needed]

tarek

[Ocean]

can you list the steps labeld by { B N } constraint, something like this:

Code: Select all

1..3.52.8.2..4..6.3........8.......3.4.....1.7.......9........5.6..8..2.4.39.7..6
26:B7-B1-B1-B2-B2-B1-N5-N3-B3-B1-N1-B3-N1-B1-B1-B1-B2-B2-B2-B3-B3-B6-B4-B6-B6-B2


for independent verification
(this is probably not what you get because my B code does not detect naked singles
but it probably should -- any naked singles are counted at the end)

Not sure if the reports from my program can be compared directly, but here is a try...

I have not implemented {B N} constraint specifically. The logical solver used to just solve the puzzles with methods at a fixed priority, and then report which methods it used. Step counting has not been an issue before, except for singles only - or {N F} constraint. For the recently implemented {B1 F} constraint I get this:

S12 [9-3-4-3-2-4-5-5-8-8-4-2]
LC19 {@24-24-33-33-33-36-36-36-40-43-45-45-49-54-59-59-67-67-75}

This means: Total step count ('hidden singles steps') is 12. To begin with there are two iterations of LC-eliminations (B1) (@24 means 24 cells are filled. The number of candidate eliminations is not reported, except when the code is compiled with a debug flag and reports lots of stuff). Next: 9 hidden singles, and 33 cells are filled. Then: 3 iterations of LC-eliminations {@33}. After this: 3 hidden singles, and 36 cells are filled. And so on.

Comment: The B-code detects (performs eliminations based on) hidden singles also. In 'normal mode', this is not an issue, as the hidden singles are assigned before the pointed bar operations. But it does matter when the order is changed.

[Also: the puzzle can not be solved with singles only (N+F), but one LC-scan {@42} is sufficient for solving - not reporting whether LC1 or LC2 were used, or how many candidate eliminations were done by the LC-method.]

In short, the counting method tends to underrate puzzles (reports low counts compared to other methods). This means that some 'good' puzzles might be 'lost' (not found among the highest reported counts). For lowsteppers it's the opposite - tends to overrate puzzles (by reporting too low counts compared to other methods).

I have to disagree on this......

OK. I just described the pragmatic counting method I had implemented (while waiting for an agreement). Not sure at all if this is the best way to do it! (It's probably not, but at least it is consistent).

[RW]

Modified counting algorithm:
1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
---- If any new eliminations were done, go back to step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

I have to disagree on this..........(how can you loop through 1 & 3 without hidden singles)....

As far as I can see, only steps 1 & 2 are looped. This should work in the same way as I do as a human solver, immediately follow up any pointing pairs uncovered by previous pointing pairs.

Needed or required Pointing pairs (B1) can't be counted using this method, they can be counted using Pat's method which I highlighted earlier, which if needed has to be set up seperately [IMO I don't think it is needed]

You are right, the amount of 'needed' pointing pairs is not very interesting, as long as there are some. We should be counting pointing pairs required for the lowest step count.

RW

[gsf]

Modified counting algorithm:
1. Find all locked pairs (type 1), but pretend they do not exist.
2. Make eliminations based on the locked pairs found in step 1.
---- If any new eliminations were done, go back to step 1.
3. Find all hidden singles, but pretend they do not exist.
4. Place the hidden singles found in step 3 and perform eliminations.
5. Increment step counter and repeat from step 1.

a problem with this and a few of the other proposals is that the step counter
is incremented at the end and may miss a bunch of uncounted moves in 2.

still no luck replicating anyone's step counts at any point in this thread
given that consensus was reached for what a step means in the inferior thread
maybe inferior counting can be extrapolated for ulterior and the inevitable
anterior excelsior exterior interior posterior senior threads to follow

motivation: come to an early and general agreement so that algorithms can
be designed to capture future threads like { inferior ulterior }

the basic principle is that the step count must be the same for all isomorphic
representations of a puzzle

this can be achieved by batching (the inferior choice), where all possible moves
at one step are first identified, and then they are applied as a group
alternatives would involve selecting subsets of possible moves, which
could become intractable

inferior step counts are easy
naked and hidden singles are batched
and the application of a batch of moves counts as a step

choices arise when more constraint techniques are added to the mix

first the techniques must be ordered -- easy enough
second, the place to increment the step must be identified
it seems each batch should count as a step, otherwise plugging inferior
requirements into e.g. ocean's modification above would result in 1 step
for all inferior puzzles

so here's the general proposal for step counting
let Ci, 1<=i<=n, be the constraint techniques to be applied in the order 1..n
count the steps leading to a solution by:

Code: Select all

  step = 0
count:
  for i 1 .. n
    if Ci progresses the solution (makes a placement or candidate elimination)
     identify all Ci moves (placements/eliminations)
     apply all Ci moves in one batch
     increment step
     goto count
  if no Ci progresses the solution then
     either the puzzle is solved or
     the puzzle does not meet the Ci constraints


for inferior: n=1, C1=singles
for ulterior: n=2, C1=box-line, C2=hidden-singles

[ab]

I like Ocean's suggestion, I'm sorry if I missed it before, and I agree it wouldn't alter the count if the puzzle is rotated etc.

It's curious that in this thread we've spent more time discussing the definition of the puzzles than submitting puzzles. For my part that's because I'm finding it hard to find these puzzles. The discussions are interesting though

PS if Ocean's counting is similar to Ruud's original idea, then this thread has mirrored the inferior thread even closer than it intended, because it took Vidarino to explain my idea for counting steps there

[Ocean]

the basic principle is that the step count must be the same for all isomorphic
representations of a puzzle

I agree, this is a crucial point.

so here's the general proposal for step counting
let Ci, 1<=i<=n, be the constraint techniques to be applied in the order 1..n
count the steps leading to a solution by:

maybe: count the steps Si leading to a solution. Where Si is the number of times Ci is applied.

It's curious that in this thread we've spent more time discussing the definition of the puzzles than submitting puzzles. For my part that's because I'm finding it hard to find these puzzles.

Ok. Here is a replacement for my first submission, which is now declared invalid (since it could be solved with singles only). That puzzle was easily found by scanning the set "oceanM20". With the new requirements, 72 of those 10117 puzzles qualify as ulterior. Statistics for that file (using the conservative counting method) : 10xS10; 12xS11; 15xS12; 13xS13; 4xS14; 6xS15; 5xS16; 1xS17; 4xS18; 2xS19. - in case anybody cares to reproduce or give alternative counting stats.

This one (a newer puzzle) got a conservative stepcount of 20:

Code: Select all

# Type I (M20)
 *-----------*
 |..1|...|2..|
 |.2.|.3.|.4.|
 |5..|...|..3|
 |---+---+---|
 |...|1.6|...|
 |.7.|...|.5.|
 |...|3.8|...|
 |---+---+---|
 |6..|...|..1|
 |.5.|.4.|.2.|
 |..4|...|7..|
 *-----------*

Also a replacement for the type V - puzzle (after a bug fix - some LC2-eliminations slipped through when picking the previous.)

Code: Select all

# Type V (M20)
 *-----------*
 |...|...|..1|
 |...|..2|...|
 |.3.|.4.|2.5|
 |---+---+---|
 |...|..4|.62|
 |.7.|...|.8.|
 |91.|7..|...|
 |---+---+---|
 |4.5|.9.|.7.|
 |...|5..|...|
 |6..|...|...|
 *-----------*

[tarek]

I have optimised the solver/generator to account for friutful steps...

Having done that, I realised that ab's method is the one really needed...........

1st Box line (type 1)
2nd Single eliminations (if elimination happened) then return to 1st
3rd Hidden single
4th Steps++
5th goto 1st

I misunderstood Ocean completely, so I stand corrected on that...
The reason why we had to do it as above is that for computers as opposed to the human eye everything must be laid clear to draw a conclusion......putting single eliminations 1st would eliminate valuable information & increase the step count...

Anyway....
.
[Edit: The next paragraph has been modified since 1st posted]

Al optimised now.The fruitful type 1 box line elimination is not A Needed one, but it gives a statisfaction of achieving more placemnts in a step than if delayed (occasionally they are needed)........Ocean's 27 stepper has 3 fruitful pointing pair steps (Steps 6,8,13) out of 9 steps where pointed pairs could be used (33% fruitfulness). You can consider puzzles with more fruitful pointing pairs as being more challanging & 100% fruitfulness would make RW a happy player

happy hunting

tarek

[tarek]

I was checking previous puzzles to compare results, The step count most of the time is similar, however some problems still persist....

for RW's puzzle #4 I had an invalid result..our results diverged from step 1.... could you provide the log for that puzzle,,thanx

tarek

[Ruud]

I'm glad this thread has opened this unexpected discussion. This middle ground was long neglected as a subject of discussion, even when the majority of published puzzles would probably fit into this category.

Ocean

Your results:

Code: Select all

20 clues, Symmetry Class I - Full dihedral
*-----------------*
|. . 1|. . .|2 . .|
|. 2 .|. 3 .|. 4 .|
|5 . .|. . .|. . 3|
|-----+-----+-----|
|. . .|1 . 6|. . .|
|. 7 .|. . .|. 5 .|
|. . .|3 . 8|. . .|
|-----+-----+-----|
|6 . .|. . .|. . 1|
|. 5 .|. 4 .|. 2 .|
|. . 4|. . .|7 . .|
*-----------------*
Ulterior (FB) Rating: 25 steps (1 2 2 2 3 2 1 2 2 2 2 2 3 3 2 2 2 1 4 4 2 4 4 6 1)
Other test results:
 F  : (invalid)
 FN : (invalid)
 N  : (invalid)
 FNB: 20 steps

20 clues, Symmetry Class V - 180-degree rotational
*-----------------*
|. . .|. . .|. . 1|
|. . .|. . 2|. . .|
|. 3 .|. 4 .|2 . 5|
|-----+-----+-----|
|. . .|. . 4|. 6 2|
|. 7 .|. . .|. 8 .|
|9 1 .|7 . .|. . .|
|-----+-----+-----|
|4 . 5|. 9 .|. 7 .|
|. . .|5 . .|. . .|
|6 . .|. . .|. . .|
*-----------------*
Ulterior (FB) Rating: 26 steps (3 2 2 1 1 2 2 1 1 2 1 1 2 1 1 2 2 2 2 3 7 7 5 3 3 2)
Other test results:
 F  : (invalid)
 FN : (invalid)
 N  : (invalid)
 FNB: 13 steps

Tarek, you asked for the log of RW#4, here it is:

Step 1

Digit 8 locked in B1R3
Eliminate 8 in R3C7
Eliminate 8 in R3C9
Digit 9 locked in B2C5
Eliminate 9 in R5C5
Digit 8 locked in B4R5
Eliminate 8 in R5C5
Eliminate 8 in R5C6
Digit 5 locked in B7R9
Eliminate 5 in R9C7
Digit 7 locked in B7R7
Eliminate 7 in R7C4
Eliminate 7 in R7C5
Single in R1D5
Single in C1D5
Single in R2D9
Single in C2D9
Single in B3D9
Single in C4D9
Single in B5D8
Single in C6D8
Single in C8D9
Place 5 in R1C3
Place 5 in R9C1
Place 9 in R2C5
Place 9 in R9C2
Place 9 in R3C9
Place 9 in R5C4
Place 8 in R6C5
Place 8 in R9C6
Place 9 in R7C8

Step 2

Digit 1 locked in B1R3
Eliminate 1 in R3C5
Eliminate 1 in R3C6
Digit 6 locked in B1R2
Eliminate 6 in R2C6
Digit 1 locked in B7C3
Eliminate 1 in R3C3
Digit 4 locked in B8C5
Eliminate 4 in R3C5
Digit 2 locked in B9C7
Eliminate 2 in R1C7
Eliminate 2 in R3C7
Single in B1D1
Single in B2D4
Single in B3D2
Place 1 in R3C2
Place 4 in R3C6
Place 2 in R1C8

Step 3

Digit 3 locked in B3C7
Eliminate 3 in R4C7
Eliminate 3 in R5C7
Single in B1D8
Single in C2D8
Place 8 in R3C1
Place 8 in R5C2

Step 4

Digit 2 locked in B4C3
Eliminate 2 in R2C3
Eliminate 2 in R3C3
Single in B1D2
Single in R3D2
Place 2 in R2C2
Place 2 in R3C5

Step 5

Digit 7 locked in B2R1
Eliminate 7 in R1C7
Eliminate 7 in R1C9
Digit 2 locked in B8C4
Eliminate 2 in R6C4
Single in C2D7
Single in B3D7
Single in B5D2
Single in R6D2
Single in C9D7
Place 7 in R4C2
Place 7 in R3C7
Place 2 in R5C6
Place 2 in R6C3
Place 7 in R5C9

Step 6

Digit 4 locked in B4R5
Eliminate 4 in R5C8
Digit 5 locked in B6C7
Eliminate 5 in R8C7
Single in R3D3
Single in B3D3
Single in R8D5
Place 3 in R3C3
Place 3 in R1C7
Place 5 in R8C9

Step 7

Single in R1D8
Single in R2D3
Single in C7D8
Place 8 in R1C9
Place 3 in R2C6
Place 8 in R7C7

Step 8

Single in R7D2
Single in C7D2
Place 2 in R7C4
Place 2 in R9C7

Step 9

Digit 1 locked in B9R8
Eliminate 1 in R8C4
Eliminate 1 in R8C5
Single in B9D6
Place 6 in R7C9

Step 10

Single in R6D6
Single in C9D4
Single in B9D4
Place 6 in R6C4
Place 4 in R6C9
Place 4 in R8C8

Step 11

Digit 3 locked in B5C5
Eliminate 3 in R8C5
Single in C4D3
Single in R6D3
Single in C6D6
Single in R8D1
Single in C8D1
Single in B8D6
Place 3 in R8C4
Place 3 in R6C8
Place 6 in R1C6
Place 1 in R8C7
Place 1 in R5C8
Place 6 in R9C5

Step 12

Single in C4D7
Single in C5D4
Single in C6D1
Single in R8D7
Single in R9D4
Place 7 in R1C4
Place 4 in R7C5
Place 1 in R4C6
Place 7 in R8C5
Place 4 in R9C3

Step 13

Single in R1D1
Single in C1D4
Single in C3D1
Single in C4D1
Place 1 in R1C5
Place 4 in R5C1
Place 1 in R7C3
Place 1 in R9C4

Step 14

Single in C1D3
Single in C3D7
Single in R5D3
Single in R7D7
Place 3 in R4C1
Place 7 in R2C3
Place 3 in R5C5
Place 7 in R7C1

Step 15

Single in C1D6
Single in C3D6
Single in R4D6
Single in R5D5
Single in C5D5
Place 6 in R2C1
Place 6 in R5C3
Place 6 in R4C7
Place 5 in R5C7
Place 5 in R4C5

Ruud.