Ulterior Puzzles

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

Postby ab » Sat May 27, 2006 9:39 pm

I think I understand why I am not getting the same number of steps as you Ruud and I'm not happy about it.

First we need to agree on a definition of a step. For me it is: given the current state of the puzzle, what can i infer from it immediately.
In the inferior puzzles thread this is not a problem. What singles can I infer from the state of the puzzle? work them all out without
placing them, then place them all in one sweep. Some singles could be considered hidden singles or naked singles, but it doesn't matter, because we place them all at the same time.
With ulterior puzzles there are two very different types of things, there are the pointing
pairs and there are the hidden singles. I think at the start of the puzzle we should ask what pointing pairs are there? but not do any of the eliminations.
Then do all the eliminations in one sweep. Then ask what hidden singles there are, without placing them, then place them all in one sweep. Then rinse and repeat.

It doesn't look like this is what you're doing. It looks like you're applying the eliminations from pointing pairs as soon as you see them. Here's one reason why I
disagree with this: Suppose 5 is a candidate in r1c1, r1c3, r2c3 and r3c3 and nowhere else in the top left 3x3 box. If there is a pointing pair on 5s in row 1, then
if you apply the eliminations immediately you uncover a pointing pair in 5s in column 3. This pointing pair cannot be inferred immediately from the current position,
so should not be counted on this step, but I fear your current method of counting steps would count it on this step. Now if the pointing pair on row 1 uncovers a hidden
single, then this will be counted on this step, as we don't search for hidden singles until we have carried out all the eliminations from pointing pairs. I have no problem
with pointing pairs uncovering hidden singles on the same step, but they shouldn't uncover other pointing pairs on the same step.
ab
 
Posts: 451
Joined: 06 September 2005

Postby Ocean » Sat May 27, 2006 10:52 pm

Not sure if I count correctly, but here is a test candidate:

Code: Select all
 *-----------*
 |...|...|...|
 |..1|...|2..|
 |.3.|1.4|.5.|
 |---+---+---|
 |..2|.4.|6..|
 |...|7.5|...|
 |..8|.2.|1..|
 |---+---+---|
 |.5.|9.3|.7.|
 |..6|...|9..|
 |...|...|...|
 *-----------*
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Ruud » Sat May 27, 2006 11:09 pm

Ab & Tarek,

I get both your points. In stead of caving in too quickly, as I did with Motris' request, I would like to explain why I count the way I do. This has everything to do with the way I solve sudokus manually.

When I use the computer, I cycle through digit highlighting (the Watch tool in SudoCue) and perform every elimination and placement that I can infer from the pattern, before I move on to the next digit. When I cannot advance this way any further, I switch on the pencilmarks.

When I solve with pen and paper, I can mentally focus on each digit and do exactly the same thing. Solve locked pairs and hidden singles in one sweep. But I cannot easily turn pencilmarks on and off on paper. That is why I started this thread, to find the best puzzles that I can solve in the way I like to do it. There you have it. My ulterior motive.

If I wanted to emulate completely the way I solve puzzle manually, I would have to work digit by digit, but that would cause a dependency on the permutation of the digits. A scrambled puzzle would solve differently. So, the consession I made is to scan the state of the puzzle, in infer everything you can infer from the candidate pattern of each digit, forcefully ignoring dependencies between digits.

A hidden single is also a locked candidate, and often it was a locked candidate richt before it became a hidden single. The split you are trying to make between locked candidates and hidden singles has strong arguments, but it would deviate too much from my manual solving.

I would like to have the real players to step forward and express their opinion on this. Maybe I am the only person in the world who solves sudokus like this...

My last argument: The fact that this counting method lowers the number of steps makes the few puzzles that do produce high stepcount extra special. I'm having a field time solving that type IV 20 stepper. After the initial opening, there are 8 consecutive steps of 1.

The discussion is still open, but I like to hear more opinions.

Ruud.

Ocean: I was about to submit this post when I saw your 23-stepper.

YES!!!!!

Code: Select all
20 clues, Symmetry Class I - Full dihedral (Ocean)
*-----------------*
|. . .|. . .|. . .|
|. . 1|. . .|2 . .|
|. 3 .|1 . 4|. 5 .|
|-----+-----+-----|
|. . 2|. 4 .|6 . .|
|. . .|7 . 5|. . .|
|. . 8|. 2 .|1 . .|
|-----+-----+-----|
|. 5 .|9 . 3|. 7 .|
|. . 6|. . .|9 . .|
|. . .|. . .|. . .|
*-----------------*
Ulterior (FB) Rating: 23 steps (4 3 2 1 2 2 2 2 2 2 2 1 3 3 2 4 1 1 3 5 6 4 4)
Other test results:
 F  : 28 steps
 FN : 14 steps
 N  : (invalid)
 FNB: 13 steps
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby tarek » Sun May 28, 2006 7:39 am

It is me who is going to cave in if you insist on your methods Ruud:D , I'm happy to abide by any rules you suggest.

I'm only suggesting what IMO we agreed before was the definition of a step......

Look at the current state of the puzzle (No pencilmarks), just original clues, placements, & blanks......all placements that can be achieved using information from that state of puzzle are in one step.

for programmers: Placemts are the last thing in a step, so any deduction that follows a placement should be in the next step.....

Because you decided not to uncover naked singles as NAKED SINGLES means for programmers that we should be blind to the fact that a cell has only one candidate if that conclusion was reached by SINGLE candidtae eliminations &/or by locked candidates eliminations....we can't use it for locked candidates & we can't use it for single candidate eliminations.......Only after uncovering it as a hidden single [which would happen when all palcements in one of the shared sectors have been achieved] that we can do that.

I can't see how you Hidden single placement -Locked candidates-Hidden single placement can be in one step...... because it follows that Hidden single placement -Locked candidates - Hidden single placement - Locked candidates - Hidden single placement should also be in 1 step:?:

the way I see it would increase the number of steps considerably, Ocean's last puzzle has 27 steps (it would take an effor to beat that) the step count is 030102020202020201010202020103030202020101020406040402 & the log for comparison is
Code: Select all
.
.
.
.
.
Eliminating 2 From r1c1 (Box 2 & Row 1 Box-Line interaction)
Eliminating 2 From r1c2 (Box 2 & Row 1 Box-Line interaction)
Eliminating 5 From r1c1 (Box 4 & Column 1 Box-Line interaction)
Eliminating 5 From r2c1 (Box 4 & Column 1 Box-Line interaction)
Eliminating 5 From r8c9 (Box 6 & Column 9 Box-Line interaction)
Eliminating 5 From r9c9 (Box 6 & Column 9 Box-Line interaction)
Eliminating 7 From r1c9 (Box 6 & Column 9 Box-Line interaction)
Eliminating 7 From r2c9 (Box 6 & Column 9 Box-Line interaction)
Eliminating 7 From r3c9 (Box 6 & Column 9 Box-Line interaction)
r1c3 value MUST be 5 (Hidden Single in Column 3)
r9c7 value MUST be 5 (Hidden Single in Column 7)
r3c1 value MUST be 2 (Hidden Single in Row 3)
End of Step 1

Eliminating 5 From r1c4 (Naked Single in Row 1)
Eliminating 5 From r1c5 (Naked Single in Row 1)
Eliminating 2 From r7c1 (Naked Single in Column 1)
Eliminating 2 From r8c1 (Naked Single in Column 1)
Eliminating 2 From r9c1 (Naked Single in Column 1)
Eliminating 5 From r9c4 (Naked Single in Row 9)
Eliminating 5 From r9c5 (Naked Single in Row 9)
r7c9 value MUST be 2 (Hidden Single in Row 7)
End of Step 2
.
.
.
.
End of Step 25

Eliminating 8 From r1c2 (Naked Single in Box 1)
Eliminating 9 From r4c1 (Naked Single in Box 4)
r6c1 value MUST be 4 (Hidden Single in Column 1)
r6c2 value MUST be 7 (Hidden Single in Column 2)
r1c2 value MUST be 4 (Hidden Single in Row 1)
r4c9 value MUST be 7 (Hidden Single in Row 4)
End of Step 26

Eliminating 7 From r6c9 (Naked Single in Box 6)
r4c1 value MUST be 5 (Hidden Single in Column 1)
r6c9 value MUST be 5 (Hidden Single in Column 9)
End of Step 27


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

re: box-line interaction

Postby Pat » Sun May 28, 2006 10:13 am

hi Ruud,

i like to solve SuDoku on paper,
and without making lists of the possibilities in each cell;
so, i certainly agree with you about preferring the "hidden" stuff over the "naked".

( i'm not so sure about preferring box-line interaction over "naked singles" - but i'll go along with your rule. )

but i would like you to allow both types of box-line interaction (as already suggested by motris); i use the 2 types equally.


what really bothers me is the definition of the steps in solving - would you consider an alternative somewhere along these lines:
  • solve by "hidden singles" as far as possible (not using box-line interaction at all)
  • when stuck, use all box-line interactions available at that point; then revert to using only "hidden singles" until stuck again.
( even that does not really get me what i'd like to know, which is: how many box-line interactions were actually needed for solving the puzzle. )


~~~~~ following puzzle taken from a recent newspaper -
i'm curious as to its rating:
Code: Select all
 1 . . | 3 . 5 | 2 . 8
 . 2 . | . 4 . | . 6 .
 3 . . | . . . | . . .
-------+-------+------
 8 . . | . . . | . . 3
 . 4 . | . . . | . 1 .
 7 . . | . . . | . . 9
-------+-------+------
 . . . | . . . | . . 5
 . 6 . | . 8 . | . 2 .
 4 . 3 | 9 . 7 | . . 6
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

Re: re: box-line interaction

Postby tarek » Sun May 28, 2006 11:36 am

Pat wrote:what really bothers me is the definition of the steps in solving - would you consider an alternative somewhere along these lines:
  • solve by "hidden singles" as far as possible (not using box-line interaction at all)
  • when stuck, use all box-line interactions available at that point; then revert to using only "hidden singles" until stuck again.
( even that does not really get me what i'd like to know, which is: how many box-line interactions were actually needed for solving the puzzle.


This sounds logical....It means that you must have an F invalid puzzle to start with (even better if FN invalid).......Let's hear it Ruud & let's adjust our solvers.....

Programmer suggestion:

Code: Select all
Innermost loop......hidden singles (batch)

2nd loop:
a. if Inner loop scores a placement or placements then Steps++
b. Singles elimination (batch)......
c. if any elimination achieved, go to innermost loop

Outermost loop:
a. Box line interaction (batch) -----(decide if type 2 or 1+2)
b. c. if any elimination achieved, go to innermost loop


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

Postby ab » Sun May 28, 2006 12:42 pm

Here's another reason to adopt the counting method I suggest.

I don't think anyone else understands your counting method, Ruud.
The Litmus test is how many people have written software which counts the same
number of steps for these puzzles as you:?: If you adopt the counting method
I suggest, everyone will very quickly write software which will arrive at
the same number of steps.
ab
 
Posts: 451
Joined: 06 September 2005

Postby Ruud » Sun May 28, 2006 2:01 pm

We're having a very good discussion here.:)

I'm not convinced by the "how many people have written software which counts the same number of steps for these puzzles as you" argument. This thread is intended to step away from the way we look at these puzzles as a programmer, and look at them as a human solver. In my software, I can implement hidden singles and locked pairs as two distinct techniques. But as a human, it all blends into a single picture.

Take the excellent puzzle submitted by Ocean, for example.
This is how I see the starting position with my "#2 glasses" on:

Image

You could argue that there are 4 distinct steps in this picture:
1. Identify the pointing pair in box 2;
2. Identify the hidden single in box 1 & row 3;
3. Identify the hidden single in row 7;
4. Identify the hidden single in box 6 & column 8;

As a programmer, I need to program these steps one by one.
As a human solver, I can see all these possibilities in a few seconds.

Am I so wrong in my determination to count everything I can solve by looking at this picture as a single step? I am surprised by Pat's response. When you ignore locked candidates in your initial sweep, you miss a lot of opportunities, which slows down your solving speed considerably. The way you use locked pairs is such, that there is no real difference between type 1 and type 2. If more people solve that way, then it's time to rethink my strategies.

On the brink of caving in,

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

re: puzzle submitted by Ocean

Postby Pat » Sun May 28, 2006 2:21 pm

Ruud wrote:Take the excellent puzzle submitted by Ocean, for example---
Symmetry Class I - Full dihedral
20 clues
Code: Select all
*-----------------*
|. . .|. . .|. . .|
|. . 1|. . .|2 . .|
|. 3 .|1 . 4|. 5 .|
|-----+-----+-----|
|. . 2|. 4 .|6 . .|
|. . .|7 . 5|. . .|
|. . 8|. 2 .|1 . .|
|-----+-----+-----|
|. 5 .|9 . 3|. 7 .|
|. . 6|. . .|9 . .|
|. . .|. . .|. . .|
*-----------------*


When you ignore locked candidates in your initial sweep,
you miss a lot of opportunities,
which slows down your solving speed considerably.


this puzzle was actually a disappointment for me,
as i solved it entirely by "hidden singles"
- never needing any box-line interaction.

( i'd like to tackle only those puzzles which do need something beyond Basic Elimination.
now i realize that F : (invalid) flags the puzzles i do wish to solve.
)


~~~~~ in addition to the newspaper puzzle i posted above,
here are 2 more puzzles - how would they rate?
( all 3 do need box-line interaction )
Wayne Gould wrote:2.69
Code: Select all
 . . 1 | . 4 . | 2 . .
 . . . | 7 . 3 | . . .
 3 . 5 | . . . | 8 . 1
-------+-------+------
 . 2 . | . . . | . 8 .
 . . . | 6 . 9 | . . .
 . 9 . | . . . | . 5 .
-------+-------+------
 5 . 6 | . . . | 1 . 3
 . . . | 5 . 1 | . . .
 . . 8 | . 6 . | 4 . .


2.73
Code: Select all
 . 4 . | 1 . 8 | 2 . .
 . 5 7 | . . . | . . .
 . . . | . . 2 | 6 . .
-------+-------+------
 . . 4 | 6 . . | . . .
 6 . 8 | . . . | 4 . 9
 . . . | . . 7 | 5 . .
-------+-------+------
 . . 1 | 3 . . | . . .
 . . . | . . . | 7 3 .
 . . 9 | 5 . 1 | . 6 .
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

Postby ab » Sun May 28, 2006 4:15 pm

Ruud wrote:We're having a very good discussion here.:)


Agreed
Ruud wrote:Take the excellent puzzle submitted by Ocean, for example.
This is how I see the starting position with my "#2 glasses" on:

Image

You could argue that there are 4 distinct steps in this picture:
1. Identify the pointing pair in box 2;
2. Identify the hidden single in box 1 & row 3;
3. Identify the hidden single in row 7;

This is where I disagree with you, as does Tarek, I think. The hidden single in row 7 is identified as a result of carrying out the eliminations of the pointing pair and placing the hidden single in box 1, row 3 and therefore should be placed on the next step.
ab
 
Posts: 451
Joined: 06 September 2005

Postby tarek » Sun May 28, 2006 4:29 pm

Ruud wrote:4. Identify the hidden single in box 6 & column 8


You could not have made that conclusion without placing 2 r7c9 which in turn could not be placed without placing 2 in r3c1 (I did try it by hand & it still looks as three steps to me). I still insist on that Placemnts should be the last thing in a step.

Now, if you insist on that Ruud I will submit but I really think you should reconsider. I think that my solving method (whichsounds the same as ab's) although pure programming, it is still logical for human solvers.

Also, I understand why this intends to provide puzzles for the non PM crowd, As programmers we should design puzzles that would not allow us to cut through corners....these puzzles should be F=invalid & FN=invalid (As Pat mentioned)....

& to make things tougher but still producing a good puzzle full FNB steps (including type 1+2) should be = to Ulterior Steps........

That would provide us with a good puzzle which is Reproducable however you solve it.

A choice of methods
1. Pat's : Sweep with single eliminations Then place hidden singles...if no placemnts then sweep with locked candidates Then place hidden singles
2. My method +/- ab's: Sweep with single eliminations & locked candidates then place hidden singles
3. Ruud's method (I think): Hidden singles/locked candidates looping then single eliminations.

Also about to cave in,

tarek
Last edited by tarek on Sun May 28, 2006 12:39 pm, edited 2 times in total.
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby gsf » Sun May 28, 2006 4:35 pm

(summarizing, restating, and opining)

it would seem to make sense to extrapolate step based on the inferior thread consensus
inferior step counting washes the affects of the order in which cells in a position
are examined: scan [11] to [99] in reverse, row-col, random order -- it doesn't matter
because identification of moves is separated from acting on them

for inferiors only { naked-single hidden-single } constraints are considered
and they are considered together, so a step consists of
(1) identify all { naked-single hidden-single } moves but take no action
(2) make all moves identified by (1) in one batch of moves
(3) start a new step

for ulterior the constraints in scope are { hidden-single box-line }
(box-line: candidates in box confined to one line, line-box: candidates in line confined to one box)
it doesn't seem to make sense to lump hidden-single with box-line
so a step would have to order the constraints to get reproducable counts

(1) identify all { hidden-single } moves but take no action
(2) make all moves identified by (1) in one batch of moves -- if there were moves start a new step (goto (5))
(3) identify all { box-line } moves but take no action
(4) make all moves identified by (3) in one batch of moves
(5) start a new step

as noted earler in this thread the absense of naked-single works in ulterior
because there are positions where naked-single can be considered and detectd
as a degenerate hidden-single

here are the shorthand and explicit steps based on the above for ocean's last puzzle
Code: Select all
...........1...2...3.1.4.5...2.4.6.....7.5.....8.2.1...5.9.3.7...6...9...........

28:3-1-2-2-2-2-2-2-1-1-2-2-2-1-3-3-2-3-1-1-1-1-2-5-5-3-4-2
28:N3-N1-N2-N2-N2-N2-N2-N2-N1-N1-N2-N2-N2-N1-N3-N3-N2-N3-N1-N1-N1-N1-N2-N5-N5-N3-N4-N2

[1]  N3  [31]=2 [13]=5 [97]=5
     N1  [79]=2
     N2  [58]=2 [75]=6
     N2  [39]=6 [71]=1
     N2  [77]=8 [98]=6
     N2  [35]=8 [73]=4
     N2  [33]=9 [59]=8
     N2  [37]=7 [93]=7
     N1  [53]=3
     N1  [17]=3
     N2  [25]=3 [57]=4
     N2  [24]=5 [85]=5
     N2  [86]=7 [15]=7
     N1  [55]=9
     N3  [52]=1 [95]=1 [46]=1
     N3  [44]=8 [51]=6 [96]=8
     N2  [64]=3 [16]=2
     N3  [66]=6 [14]=6 [26]=9
     N1  [22]=6
     N1  [21]=7
     N1  [28]=8
     N1  [29]=4
     N2  [94]=4 [88]=4
     N5  [89]=1 [92]=2 [84]=2 [18]=1 [48]=3
     N5  [19]=9 [81]=3 [91]=9 [68]=9 [99]=3
     N3  [42]=9 [82]=8 [11]=8
     N4  [12]=4 [49]=7 [61]=4 [62]=7
     N2  [41]=5 [69]=5
     S


I'm pretty sure the difference between this and tarek's is when naked-singles are counted as degenerate hidden-singles
I delay the degenerate hidden-singles until the last step
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Sun May 28, 2006 4:51 pm

gsf wrote:as noted earler in this thread the absense of naked-single works in ulterior because there are positions where naked-single can be considered and detectd as a degenerate hidden-single


I do not leave them last, when that degenerate hidden single is in the only uncovered cell in a sector.... the answer to what would occupy that cell & where can I place the candidate are equivalent and a placement wiuld be possible

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

Postby ab » Sun May 28, 2006 6:09 pm

Ruud wrote:We're having a very good discussion here.:)


As a human solver, I can see all these possibilities in a few seconds.


Here's the rub. You're looking for puzzles which suit your solving style. That is a very subjective thing, it may be different to my solving style. However in order to compile a list of ulterior puzzles we need an objective test, which is what Tarek, gsf and I are suggesting. You will probably find that puzzles that pass this objective test will invariably also suit your solving style.

gsf wrote:(1) identify all { hidden-single } moves but take no action
(2) make all moves identified by (1) in one batch of moves -- if there were moves start a new step (goto (5))
(3) identify all { box-line } moves but take no action
(4) make all moves identified by (3) in one batch of moves
(5) start a new step

I disagree with this order. On the second step and subsequent steps some hidden singles will be uncovered by pointing pairs on the first step, so in a sense the first step is a different kind of step from all the others. I think you should look for pointing pairs first, after all they exist in the initial state of the puzzle. That way all steps will be the same.
ab
 
Posts: 451
Joined: 06 September 2005

Postby gsf » Sun May 28, 2006 9:36 pm

tarek wrote:I do not leave them last, when that degenerate hidden single is in the only uncovered cell in a sector.... the answer to what would occupy that cell & where can I place the candidate are equivalent and a placement wiuld be possible

that was my guess
delaying to the last is an artifact of solver order and technique partitioning
in mine singles are handled first and completely
then box-line/line-box is coded assuming singles were already done
this works fine until you fiddle the works by disabling naked-singles
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General