The New Sudoku Players' Forum

[ronk]

With so many names to choose from, why did you call it a y-cycle. It's is more meaning to call it a simple pure bivalue nice loop or more elegant to call it an xy-chain since all cells involved are bivalued which is what 'xy' implies.

Because to me they all still pretty much mean the same thing, and the more broadly defined "y-cycle" seemed the safest to say ... safest relative to those who tend to be pedantic, that is.

Ron

[tarek]

Thanx ronk,

I think your "solver log" should not tie all those placements and eliminations back to "Any Candidate in r1c1 ...". [

I'm happy for you to suggest a better wording for that phrase !

After the placement r1c2=9, the puzzle can be solved with only naked and hidden singles, so reporting the placements as such would greatly enhance understandability IMO. For example ...
Naked single: r3c2=5
Naked single: r3c7=9
Naked single: r2c8=5
Naked single: r6c7=8
Naked single: r7c7=5
Naked single: r5c8=9
---
---

I've used the type of notation similar to many others used over the forums. I can use the notation you suggested but it doesnt have the mathematical feeling of a chain where you have that long line that does not have any letter int . In the examples that I used only naked singles were used & a cell doesn't feature twice in a chain.

BTW Jeff and Carcul would (I think) apply a discontinuous Y-cycle nice loop to your double implication chains:

[r1c2]-1-[r1c1]-8-[r3c3]-2-[r7c3]-4-[r7c2]-1-[r1c2] which implies r1c2<>1 and r1c2=9

Thanx for confusing me there , So what is it now, because all the lines can be written the same way..... does make my the technique an xy-chain or a discontinuous Y-Cycle nice loop.

does this add to the discussion about T&E.

Tarek

[Jeff]

but you have to do a bit more convinicing regarding the "ERROR" part as the process in my opinion was not looking for something in particular.

Take this deduction for example:

Code: Select all

implications of r3c8 being 1
*--------------------------------------------------------*
| 4     5     2    | 479   4789  1    | 6     379   89   |
| 3     14    6    | 479   4789  2    | 57    579   589  |
| 7     8     9    | 3     5     6    | 2     1     4    |
|------------------+------------------+------------------|
| 9     6     4    | 5     3     7    | 1     8     2    |
| 12    12    3    | 8     6     4    | 57    579   59   |
| 8     7     5    | 1     2     9    | 4     6     3    |
|------------------+------------------+------------------|
| 6     49    1    | 49    489   5    | 3     2     7    |
| 24    24    8    | 6     47    3    | 9     5     1    |
| 5     39    7    | 2     1     3    | 8     4     6    |
*--------------------------------------------------------*
This leads to a contradiction (r8c6 & r9c6)
which makes the puzzle flawed

Implications of r3c8 being 5 = complete solution

Implications of r3c8 being 7
*-----------------------------------------------*
| 7    5    2   | 49   489  1   | 6    3    89  |
| 3    4    6   | 79   89   2   | 5    1    89  |
| 1    8    9   | 3    5    6   | 2    7    4   |
|---------------+---------------+---------------|
| 9    6    4   | 5    3    7   | 1    8    2   |
| 2    1    3   | 8    6    4   | 7    9    5   |
| 8    7    5   | 1    2    7   | 4    6    3   |
|---------------+---------------+---------------|
| 6    9    1   | 4    48   5   | 3    2    7   |
| 4    2    8   | 6    7    3   | 9    5    1   |
| 5    3    7   | 2    1    9   | 8    4    6   |
*-----------------------------------------------*
This leads to a contradiction
which makes the puzzle flawed


When you let r3c8=1, a contradiction (an error) was found. So, you backtracked and let r3c8=5. This solved the puzzle and you should have stopped there. Letting r3c8=7 was redundant.

Lets say you tried r3c8=1,5,8 in turns just to get a consistent result of r1c3=2 in all 3 cases. The point is that before you picked r3c8, you would have no idea that it would yield a valid triple implication. Of course, it's always easy to describe the result in hindsight. But, during the identification process, there is a fair chance that a valid triple implication wouldn't eventuate, and if it didn't, then its an error.

Now I will concede that if ALL double/triple/... implication chains are T&E then this is definitely a T&E technique.

The identification of an implication chain is T&E if you choose to use a T&E method to identify it, like the one you have used. There exist some advanced techniques such as bilocation/bivalue plot and advanced colouring table, which would remove the elements of trial and error from the identification process. Such identification process is termed 'pattern recognition' and is non-T&E.

[Jeff]

.........the more broadly defined "y-cycle" seemed the safest to say ... safest relative to those who tend to be pedantic, that is.

Hi Ronk, I am sure every name has earned its right to exist. Whilst I would like to point out that xy-chain is more broadly used in this forum, it is also more meaningful. Sorry to drag on.

[Jeff]

BTW Jeff and Carcul would (I think) apply a discontinuous Y-cycle nice loop to your double implication chains:

[r1c2]-1-[r1c1]-8-[r3c3]-2-[r7c3]-4-[r7c2]-1-[r1c2] which implies r1c2<>1 and r1c2=9

Thanx for confusing me there , So what is it now, because all the lines can be written the same way..... does make my the technique an xy-chain or a discontinuous Y-Cycle nice loop.

does this add to the discussion about T&E.

Hi Tarek, Yes, it could add to the discussion about T&E, because 'nice loop' is a technique that can be used to identify implication chains without T&E.

[tarek]

When you let r3c8=1, a contradiction (an error) was found. So, you backtracked and let r3c8=5. This solved the puzzle and you should have stopped there. Letting r3c8=7 was redundant.

The identification of an implication chain is T&E if you choose to use a T&E method to identify it, like the one you have used. There exist some advanced techniques such as bilocation/bivalue plot and advanced colouring table, which would remove the elements of trial and error from the identification process. Such identification process is termed 'pattern recognition' and is non-T&E.

Well, I was JUST ABOUT to be convinced.

But as u see the contradiction acts only as a STOP signal (No consequences) because I chose it to be so, I disagree on what you said that backtarcking after finding a contradiction then makes it T&E because then every technique that spots a contradiction would constitute T&E. I can easily choose the step before reaching the contradiction as the stop signal & avoid all of this, that can't be right .

Now the bit to me that was more convincing was the issue about "recognition patterns", but there are some issues hinged on that statement.

All pattern recognition techniques have to look for the pattern. LOOKING=TRIAL, the machine or solver goes through many dead ends before spitting out the pattern. what you describe as recognition patter is the end result of tedious search with trial in each step. The humans do the same to alesser extent but they become more machine-like as they use pencil-markings & solve it systematically.

Now I concede that the result came before the "How I did it ?", but knowing that the a demonstrable easily constructed non-T&E pattern does exist anyway for each step (which I did show), then I can bulid an argument from there stating that by the way " This non-T&E technique proves it". T&E can't do that.

Now if I can present EVERY result I have as consequences of a double implication chain or an xy-chain, then why shouldn't I use it in a helper program & in this forum ???

I still need more convincing, what about you ?

[Jeff]

But as u see the contradiction acts only as a STOP signal (No consequences) because I chose it to be so, I disagree on what you said that backtarcking after finding a contradiction then makes it T&E because then every technique that spots a contradiction would constitute T&E. I can easily choose the step before reaching the contradiction as the stop signal & avoid all of this, that can't be right .

That is right, every technique that have to spot a contradiction in order to made a deduction would constitute T&E. I don't understand the stop sign bit. Does it mean that you stop proceeding to solve the puzzle?

All pattern recognition techniques have to look for the pattern. LOOKING=TRIAL, ...........

'Looking' doesn't necessarily mean 'trial'. With a pattern in mind, you don't have to make any random trials. You look for a particular pattern and if you do spot one, the relevant deduction follows; no contradiction or proof of validity is required.

Now I concede that the result came before the "How I did it ?", but knowing that the a demonstrable easily constructed non-T&E pattern does exist anyway for each step (which I did show), then I can bulid an argument from there stating that by the way " This non-T&E technique proves it". T&E can't do that.

Sorry, I don't get this part.

Now if I can present EVERY result I have as consequences of a double implication chain or an xy-chain, then why shouldn't I use it in a helper program & in this forum ???

What make you feel that you shouldn't? I am confused with what you are trying to fulfill.

I still need more convincing, what about you ?

I don't need any more convincing. Don't forget I am the one who is trying to convince you. You might find some of my viewpoints difficult to accept. This is expected so due to different level of understanding of various techniques and perhaps different definition of T&E. Perhaps you would change your mind as you become more familiar with more advanced techniques.

[tarek]

Than Jeff,

I'm not trying to extend this any further,

I didn't want to post an analysis in the future which had a hint of T&E over it.

You'r telling me that if I use this technique & present the xy chian or a double implication chain to explain the results then it would a valid explanation!!!

That is all what I wanted to hear.

Because this function presents a valid non T&E technique (known to all) to explain all the conclusions, I don't see why I shouldn't use it in helper program.

It is very good, & I'll try it on the nice loops excercises to see how it does. According to you it should be slower (on occasions) than the nice loops algorithms because it can't spot the pattern

I will divide it into 2 or 3 levels for a helper program.

I will also see if a hidden singles can feature in an xy chain (it doesn't look so), or a double implication chain (I think so)...

The best name for it now seems to be a double/multi implication chains (because that is what I would use to explain the conclusion)

[Jeff]

The best name for it now seems to be a double/multi implication chains (because that is what I would use to explain the conclusion)

Hi Tarek, Multi-implication means that, in an implication stream, there is a cell which implies 2 or more cells downstream. Normally, each cell in an implication stream implies only the next cell downstream, and if this happens it is called a chain, otherwise net. Poly-implication means a chain or a net consists of more than one implication streams. Poly-implication is more appropriate for what you are trying to describe. All the best to your solver.

[tso]

"naked pairs", "swordfish", "forcing chains", "nice loops", etc are PATTERNS.

"trial and error" is a METHOD of FINDING a pattern.

All of these patterns and the rest can be found both by "trial and error" OR by other methods.

If you choose to equate "looking for" with "trial and error" there really is no where else to go. Yes, in a very broad sense, everything we do is trial and error. Solving the simplest Sudoku is completely trial and error -- you check a cell, try to fill it, find you cannot, move to the next.

[tarek]

Thanx Jeff, gsf, ronk, MythJellies & tso for all of your replies

[gsf]

I swept through ~225M canonical order puzzles and canonicalized the top1465 to eliminate duplicates (because the 225M contain random generated puzzles along with puzzles scraped from the forums)

Would you consider making the canonicalized form of the top1465 available on the web?

If "yes", thank you in advance, Ron

[I missed this post amidst the longer ones]
I should clarify
I wasn't saying that there are dups in the top1465
the 225M catalog is canonicalized with dups removed
by canonicalizing the top1465, dups between it and the 225M are easily identified

(edit 2006-01-12: Wolfgang gently pointed out that I used the canonical solution as the key in the original analysis which is just plain wrong -- I should have used the canonical puzzle -- only 300 and 307 are isomorphic -- bad analysis deleted)

you can use the command line solver executable posted at the bottom of http://www.research.att.com/~gsf/sudoku/
to canonicalize any puzzle list

(edit 2005-01-12: -f format fixed to generate the correct key)
this prints on one line per puzzle the canonical puzzle (key), the ordinal within the top1465, and the original puzzle, then sorts and uniq's

Code: Select all

sudoku -f%#.c%,%o%,%,%v top1465.dat | sort | uniq -w81 -c


the --man option lists the options and -f formats
this program is not the fast solver (sudocoup) -- that will be posted in the next week

[Wolfgang]

What do you mean with isomorphic ? I only identified 300 and 307 to be isomorphic. E.g. 204 and 224 have a different number of clues, so they cannot be isomorphic in my sense ([edit:] just the solution grids are isomorphic).

[ronk]

you can use the command line solver executable posted at the bottom of http://www.research.att.com/~gsf/sudoku/
to canonicalize any puzzle list

Upon downloading and then running the "windows executable" (I have XP Pro) I'm left looking at a blank "Command Prompt" window ... and that's the way it stays forever. What am I missing?

Hmmm! I see other sudoku.exe files on my computer, one or more of which might be in environment variable "Path". I'll try (at least temporarily) renaming all of those. [edit: Apparently that's not the problem.]

TIA, Ron

[gsf]

What do you mean with isomorphic ? I only identified 300 and 307 to be isomorphic. E.g. 204 and 224 have a different number of clues, so they cannot be isomorphic in my sense ([edit:] just the solution grids are isomorphic).

rats you are correct
I used the canonical solution as the key instead of the canonical puzzle
using the canonical puzzle yields { 300 307 } as the only isomorphic puzzles
I'm glad you caught it
next time I'll "think twice hit return once" -- hopefully that will be enough