Ulterior Puzzles

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

Postby tarek » Mon Jun 05, 2006 4:56 pm

I was under the impression from Ruud's initial post that the pointing pairs type we're after was type 1 (B1), I have been using B1 & FB1 because of that.

The rules are the rules, however I still insist on keeping pointing pairs as >1 candidate per line per box, The reason being that 1 candidtae per line per box B elimination is exactly the same elimination are achieved by the Hidden single (Therefore I could argue that you are eliminating using an uncovered hidden single, something which should wait until the following step. IMO, when this situation occurs The single should take preference as it is the end of the step). There is no room for obvious but there is room for debate:D

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

Postby gsf » Mon Jun 05, 2006 5:57 pm

tarek wrote:(Therefore I could argue that you are eliminating using an uncovered hidden single, something which should wait until the following step. IMO, when this situation occurs The single should take preference as it is the end of the step). There is no room for obvious but there is room for debate:D

so you want to count hidden singles before box-line?
or you want to count the hidden singeles except those that are also box-line before box-line?
when it gets complicated enough no-one can reproduce results and it becomes a guessing
game to see which submissions make the cut
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Mon Jun 05, 2006 6:41 pm

I'm not trying to complicate things at all.

I'm trying to say that a Box hidden single is EXACTLY similar to a TYPE 1 pointing pair. (a similar statement can be made about Type 2, with the hidden single in a line & therefore the same argument holds for full FB1B2)

It is simpler to explain when looking at it as an empty cell on a piece of paper [It is actually a hidden single].

The human would say " candidate x is either here or here, oh both of them are in a line that means no other x's are possible outside the box in that line" ---- That is a pointing pair (The train of thought spans 1 step)

However when he says " candidate x is here, therefore no other x's are possible outside the box in that line" ---That is a hidden single (The train of thought spans 2 steps)

What I'm saying is easy, >1 candidate per box (all in 1 line) are pointing pairs. 1 Candidate per box (happens also to be in a line) is a hidden single.

Ruud is apparantly off on vacation somewhere (somewhere sunny I hope) hopefully when he returns more light can be shed on this matter...

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

Postby gsf » Mon Jun 05, 2006 7:07 pm

tarek wrote:I'm not trying to complicate things at all.

I'm trying to say that a Box hidden single is EXACTLY similar to a TYPE 1 pointing pair. (a similar statement can be made about Type 2, with the hidden single in a line & therefore the same argument holds for full FB1B2)

right
but the ulterior premise is to do box-line before hidden singles

suppose we wanted to program this
we'd need two flavors of box-line constraints and/or two-flavors of hidden singles
something like this:
(1) identify the box-line moves that are hidden singles
(2) commit the moves in (1)
(3) identify box-line moves that are not hidden singles
(4) commit the moves in (3)
(5) identify the hidden single moves that are not box-line moves
(6) commit the moves in (5)
(7) increment the step count and repeat

I'm just saying that we should build upon the constraints we already have
rather than invent hybrid constraints to model playing preferences

not that playing preferences are a bad thing -- they can lead to optimizations
its just that they can really confuse the implementation of metrics llike step count
which are, after all, mechanical
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Mon Jun 05, 2006 7:29 pm

gsf wrote:step count which are, after all, mechanical


True, We decided at the start on 1 absolute "Placements should be the end of the step", as you know placements can only be uncovered as hidden singles or naked singles (for the ulterior thread we diceided that only hidden singles can uncover the placemnts). This is why I'm insisting on my point of view becuase the "Pointing pairs which are hidden singles" are doing in 1 step what should really be done over 2.

The problem here as I see it, is a problem of definition. if you would allow the definition of pointing pairs to be >1 candidates then by definition we wouldn't go into this discussion. It shouldn't be difficult to program it that way...doing that will automatically skip any "Pointing pairs which are hidden singles".

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

Postby gsf » Mon Jun 05, 2006 9:23 pm

tarek wrote:The problem here as I see it, is a problem of definition. if you would allow the definition of pointing pairs to be >1 candidates then by definition we wouldn't go into this discussion. It shouldn't be difficult to program it that way...doing that will automatically skip any "Pointing pairs which are hidden singles".

exactly

reprogramming for this one case is no problem
its the specter of this (a specialized redefinition for something that has already been
defined and programmed to get specialized counts) happening in other similar future
threads that bothers me
can we stick with agreed upon non-special-cased definitions for at least
1..n hidden/naked tuples, box-line and line-box, and basic 2,3,4 generalized x-wing?
otherwise why bother defining constraint techniques in the first place?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Mon Jun 05, 2006 11:29 pm

gsf wrote:can we stick with agreed upon non-special-cased definitions for at least
1..n hidden/naked tuples, box-line and line-box, and basic 2,3,4 generalized x-wing?
otherwise why bother defining constraint techniques in the first place


I share the same sentiments about agreed upon non-special-cased definitions.....

But could you point out definitions to box-line interaction (pointing pairs) where FN constraints haven't been exhausted beforehand...... I myself have programmed my solver always to pick up pointing pairs of >1 candidates because I know that the the =1 candidate has already been chewed up by the FN constraints [All definitions seem to reflect this fact]

There was NO pointing pair that is a hidden single, not until THIS thread......... So I totally understand your point of view, I hope you understand mine [You think That my definition of the pointing pairs is the special case when I think that yours is the special case, because although it the general rule, it only applies here]

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

Postby gsf » Tue Jun 06, 2006 11:57 am

tarek wrote:But could you point out definitions to box-line interaction (pointing pairs) where FN constraints haven't been exhausted beforehand...... I myself have programmed my solver always to pick up pointing pairs of >1 candidates because I know that the the =1 candidate has already been chewed up by the FN constraints [All definitions seem to reflect this fact]

There was NO pointing pair that is a hidden single, not until THIS thread......... So I totally understand your point of view, I hope you understand mine [You think That my definition of the pointing pairs is the special case when I think that yours is the special case, because although it the general rule, it only applies here]

"locked candidates" from the beginning of this thread
"pointing pairs" was added as an aside (I never used that term before this thread)
ruud wrote:There are 2 types of locked candidates.
Type 1 occurs when all candidates in a box are confined to a single row or column.
Type 2 occurs when all candidates in a row or column are confined to a single box.

until this thread my solver had fixed constraint order too
ab's rule of box-line before hidden-single got me to finally make constraint order an option
and like you I optimized singles out of box-line and line-box
but when the condition for the optimization is removed the optimization must go too

the intro definition above says nothing about how many candidates must be confined,
so when singles are taken out, 1 cell in confinment fits the definition
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Tue Jun 06, 2006 2:18 pm

Here is an attempt to improve on the type III.
Code: Select all
#Type III. (M22).
...|.1.|...
..2|...|3..
43.|...|.56
---+---+---
5..|4.6|..7
...|...|...
6..|8.7|..9
---+---+---
31.|...|.78
..5|...|4..
...|.2.|...

Have not yet implemented the 'proper' step counting - waiting for conclusions from the ongoing discussion.
Therefore two other alternatives:

000102000003000400100000005030050040056000710080040060200000009007000600000308000
001000200200000003040050060050407080000000000060208090090040070100000005003000800
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby tarek » Tue Jun 06, 2006 2:56 pm

gsf, I agree that you have a valid point for your argument, I hope that we could reach an agreement on this quickly because I know you have loads of puzzles waiting to be submitted:D

I think that the discussion would be more fruitful if more participated. This thread attempts to tackle these very issues.

Nice ones Ocean, my reckoning is 24,21,24 steps respectively. The last one probably stands out because it has 4 fruitful out of Total 6 possible B1 steps.

I'm still hovering around 19 steps at the moment...... For low steppers I've managed an 8 stepper FB1 & FN invalid.

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

Postby gsf » Tue Jun 06, 2006 5:00 pm

tarek wrote:Nice ones Ocean, my reckoning is 24,21,24 steps respectively. The last one probably stands out because it has 4 fruitful out of Total 6 possible B1 steps.

ok, here are the steps I get with constraint name and placement/elimination count

box can have 1 candidate:
Code: Select all
21 B12+N4 B5+N1 B4+N1 B4+N1 B2+N2 B5+N3 B3+N1 B3+N2 B3+N2
   B2+N1 B2+N2 N2 B2+N3 B1+N1 B3+N2 B2+N4 B1+N2 B2+N4 B4+N8
   B4+N11 N2
20 B18+N4 B12+N3 B11+N2 B6+N2 B3+N1 B2+N1 B2+N3 B2+N2 B5+N2
   B3+N3 B1+N3 B9+N4 B2+N3 B5+N4 B5+N4 B3+N3 B1+N3 B2+N4
   B3+N6 N2
20 B11+N3 B6+N3 B3+N3 B2+N2 B3+N2 B4+N3 B4+N4 B5+N4 B4+N2
   B2+N2 B4+N2 B4+N2 B2+N3 B1+N2 B2+N4 B1+N2 B2+N3 B1+N3
   B4+N6 B1+N4


box must have >1 candidate:
Code: Select all
23 B12+N4 B5+N1 N1 B4+N1 B2+N2 N3 B3+N1 B3+N2 B2+N2 B2+N1
   B2+N2 N2 B1+N3 B1+N1 B2+N1 N3 N2 N2 N2 N6 N10 N6 N1
21 B16+N4 B3+N3 B11+N2 B1+N2 B3+N1 N1 N2 N2 N1 N2 N3 B1+N3 N4
   B1+N3 N4 B1+N4 N3 N3 N4 N6 N2
23 B5+N3 B6+N3 B2+N3 B2+N2 B2+N2 B3+N3 B3+N3 B3+N3 N2 N2
   B1+N2 N2 N2 N2 N1 N2 N4 N2 N2 N2 B2+N3 N4 N5


what are your broken out steps?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Tue Jun 06, 2006 5:44 pm

I had a quick look at my printout, the step count is
Code: Select all
24: 040101010203010202010101020301010302020206100601
21: 040302020101020201020303040304040303040602
24: 030303020202020302020202020202010204020202030405
I will review the algorithm this evening with a mug of dark coffee, & compare the lod differences.

your log out looks reasonable, it is good to be able to swith on/off both points of view:D

tarek
Last edited by tarek on Tue Jun 06, 2006 2:38 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby Ocean » Tue Jun 06, 2006 6:13 pm

Thanks tarek and gsf for helping with the stepcount! My own 'conservative' count ("infinitely nested pointing bar elimination") was 20 for all three - and every other counting algorithm should count N>=20 or disqualify them, as far as I can judge.

I am also curious about this, type V:
Code: Select all
#Type V (M20)
...|...|.1.
12.|...|.34
...|5.6|...
---+---+---
...|2.4|...
..7|...|5..
...|8.3|...
---+---+---
...|9.1|...
23.|...|.81
.4.|...|...


(Conservative stepcount: 24)

And of course I am curious about gsf's and Ruud's collections...


To the discussion: There is also another possible problem, which I can not see is mentioned: How long are candidate eliminations remembered? Are they permanent, or are they only remembered one cycle? When we solve without pencilmarks, we do not remember candidates long, but we calculate them over again next 'loop'. Which is different from writing them down, when all eliminations are permanent and need never be erased. With the described algorithm:
ab wrote:Here it is:
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.

chained eliminations as in RW's example may not apply immediately, but several steps later (that is, if eliminations are remembered until next loop). In principle there can also be loops with no placements - only eliminations (are those counted as steps?).
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby tarek » Tue Jun 06, 2006 8:31 pm

I've just analysed the log & I think I found the problem
here the log for the 2nd step from the first puzzle
Code: Select all
*--------------------------------------------------------------------------*
| 789     56789   6789   | 235679  1       234589 | 2789    2489    2      |
| 1       56789   2      | 5679    456789  4589   | 3       1489    14     |
| 4       3       1789   | 279     789     289    | 12789   5       6      |
|------------------------+------------------------+------------------------|
| 5       289     1389   | 4       39      6      | 128     1238    7      |
| 789     4789    34789  | 12359   359     12359  | 568     3468    345    |
| 6       24      134    | 8       35      7      | 125     1234    9      |
|------------------------+------------------------+------------------------|
| 3       1       469    | 569     4569    459    | 2       7       8      |
| 2       26789   5      | 13679   36789   1389   | 4       1369    13     |
| 789     46789   46789  | 135679  2       134589 | 1569    1369    135    |
*--------------------------------------------------------------------------*
Eliminating 1 From r3c3 (Box 4 & Column 3 Box-Line interaction)
Eliminating 2 From r8c2 (Box 4 & Column 2 Box-Line interaction)
Eliminating 5 From r9c4 (Box 9 & Row 9 Box-Line interaction)
Eliminating 5 From r9c6 (Box 9 & Row 9 Box-Line interaction)
Eliminating 2 From r1c7 (Naked Single in Box 3)
Eliminating 2 From r1c8 (Naked Single in Box 3)
Eliminating 2 From r3c7 (Naked Single in Box 3)
Eliminating 2 From r1c4 (Naked Single in Row 1)
Eliminating 2 From r1c6 (Naked Single in Row 1)
Eliminating 1 From r3c3 (Naked Single in Box 1)
Eliminating 1 From r2c8 (Naked Single in Row 2)
Eliminating 1 From r2c9 (Naked Single in Row 2) ---> leaving 4 (your degenerate hidden single)

-----> 4 in r2c9 Can't be uncovered as a naked single, for it to eliminate it has to be uncovered as hidden single

Eliminating 2 From r4c7 (Naked Single in Column 7)
Eliminating 2 From r6c7 (Naked Single in Column 7)
Eliminating 2 From r8c2 (Naked Single in Box 7)
r3c7 value MUST be 1 (Hidden Single in Row 3)
End of Step 2


That is why Step 2 has to be B4+N1 (B5+N1 would result if that 4 was allowed to eliminate the 4s in cloumn 9 & therefore create a pointing pair in box 6)....

The problem should be easy to resolve if single eliminations should be carried out only by cells that have been uncovered as hidden singles.

Ocean wrote:
Code: Select all
#Type V (M20)
...|...|.1.
12.|...|.34
...|5.6|...
---+---+---
...|2.4|...
..7|...|5..
...|8.3|...
---+---+---
...|9.1|...
23.|...|.81
.4.|...|...


(Conservative stepcount: 24)


I've got 27 steps, 060302010101010101010101020201020201020302020505040602

2 Fruitful B1 steps out of 8 possible.........

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

Postby Ocean » Wed Jun 07, 2006 12:24 am

tarek wrote:I've got 27 steps, 060302010101010101010101020201020201020302020505040602

2 Fruitful B1 steps out of 8 possible.........

tarek

Thanks for analyzing the type V puzzle - it did beat the previous (if your count is matching Ruud's). Our stepcounts seem to differ between one and four in general. Also, those with highest stepcounts are often less 'fruitful' (less interesting in certain respects?). You can't get it all...

Interesting to see the logs for the type III puzzle(s) also. Will dig further into it... see how they map to the algorithms... It's a bit frustrating that there are so many different 'correct' ways of doing it...
Ocean
 
Posts: 442
Joined: 29 August 2005

PreviousNext

Return to General