Fully supersymmetric chains

Advanced methods and approaches for solving Sudoku puzzles

Postby DonM » Thu Oct 02, 2008 12:20 pm

denis_berthier wrote:
StrmCkr wrote:how can u jutify easy
with 120+ lines of text (moves) to find the solution?
when it can be soled with fewer applications?
like champanes 14

In my resolution paths, I systematically give all the steps, even the simplest - so that anyone can check the solution. Champagne gives only some steps. Anyway, the number of steps can't be a measure of difficulty and I've never seen any proposal in this sense. A puzzle that uses only elementary rules to do lots of eliminations will have lots of elementary steps. As there is no general agreement on any rating system, discussions on such topics can be endless and sterile. I said "relatively easy". This is related to the hardest rule used, here NRCZT6. If I mention its SER: 9.0, it doesn't seem so easy. Conclusion: it seems easier with nrczt-chain rules than for SE. It may seem easier if you consider another set of rules. But the converse is likely to be true of other puzzles.

The purpose of this example was to illustrate whips, not to launch a debate about rating. I've another thread for this purpose, where different rating systems are compared.


If one makes a value judgement on the relative difficulty of a puzzle for which a solution has been given, then it is legitimate for someone to question that value judgement. Not to mention the fact that it is hardly fair to argue a point raised and then essentially declare the matter closed. While I generally favor the concept that the author of a thread should, in general & within limits, be able to guide the direction of the thread, there is a limit- this is an open forum after all & not one's personal blog.

As to the point in question, who says 'the number of steps can't be a measure of difficulty...' ?: It may be a measure or it may not be depending on the puzzle and the construct of the steps themselves. Those of us who solve manually know well the puzzle that refuses to 'die' in spite of many steps. As to 'As there is no general agreement on any rating system, discussions on such topics can be endless and sterile.': Interesting, considering the fact that 'I've another thread for this purpose, where different rating systems are compared.'.

Finally, IMO, comments about difficulty of a puzzle are almost irrelevant in a thread in which computer solutions seem to rule- relatively few puzzles are 'difficult' for a computer. If the solution in question is not the result of human manual effort, then either puzzle difficulty should be left out of the equation altogether from the get-go or, at least qualified such as 'this puzzle may be easy/difficult for a human solver because...'.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby Allan Barker » Thu Oct 02, 2008 7:26 pm

Denis wrote:As T&E is a very sensitive issue, I was expecting some reactions after my new T&E theorem.As everyone's sleeping.......

Good morning, Denis.

Denis wrote:One could argue that, as the result of T&E can always be obtained by braids, which are a kind of pattern, then it is absurd to reject T&E as a resolution technique.


I have the same questions. In the FM thread, I mentioned that my 'solver' uses only sets and works at the permutation level. Starting a set {A,B,C,D} will generate 4 initial permutations whose children must all be of the form AXXX, BXXX, CXXX, or DXXX. One of these families contains the solution and the others contain a contradiction.

I have long realized that starting a complete set might be interpreted as a hidden form of T&E. On the otherhand, the process proceeds by adding only more sets and never requires any kind of guessing or even, in principle, <if> logic. So, where is the T&E? Conclusion: I haven't been able to sleep.:)

That leads to a question that applies equally to myself, to which I don't know the answer. If braids are equal to, or can do the same as, T&E, can braids solve all puzzles and do so in a few milliseconds, like common back tracking (T&E). If not, then what is the difference?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Thu Oct 02, 2008 10:44 pm

DonM wrote:As to the point in question, who says 'the number of steps can't be a measure of difficulty...' ?: It may be a measure or it may not be depending on the puzzle and the construct of the steps themselves. Those of us who solve manually know well the puzzle that refuses to 'die' in spite of many steps. As to 'As there is no general agreement on any rating system, discussions on such topics can be endless and sterile.': Interesting, considering the fact that 'I've another thread for this purpose, where different rating systems are compared.'.

So, where's the disagreement? You're saying the same thing: the number of steps is not a measure in itself !!
Discussions will be sterile unless we discuss existing ratings, or at least elaborated proposals, as we try to do in the thread mentioned.

DonM wrote:Finally, IMO, comments about difficulty of a puzzle are almost irrelevant in a thread in which computer solutions seem to rule- relatively few puzzles are 'difficult' for a computer. If the solution in question is not the result of human manual effort, then either puzzle difficulty should be left out of the equation altogether from the get-go or, at least qualified such as 'this puzzle may be easy/difficult for a human solver because...'.

The rules I've defined don't depend on any computer implementation. They are used everyday by human players.
You're allergic to computers and that's your right.
But with computers, we can make large scale studies on series of puzzles that no human solver would have time to solve. And these studies show that a rule can't be rated in the absolute but only statistically.
That's all I'll say here, because this is not the topic of this thread.
I'm not forbidding you to discuss ratings, but I strongly suggest you do it in the rating thread.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby DonM » Thu Oct 02, 2008 11:10 pm

denis_berthier wrote:
DonM wrote:As to the point in question, who says 'the number of steps can't be a measure of difficulty...' ?: It may be a measure or it may not be depending on the puzzle and the construct of the steps themselves. Those of us who solve manually know well the puzzle that refuses to 'die' in spite of many steps. As to 'As there is no general agreement on any rating system, discussions on such topics can be endless and sterile.': Interesting, considering the fact that 'I've another thread for this purpose, where different rating systems are compared.'.

So, where's the disagreement? You're saying the same thing: the number of steps is not a measure in itself !!

No, please re-read: You said 'can't be a measure of difficulty'. I said it may or it may not be depending...

DonM wrote:Finally, IMO, comments about difficulty of a puzzle are almost irrelevant in a thread in which computer solutions seem to rule- relatively few puzzles are 'difficult' for a computer. If the solution in question is not the result of human manual effort, then either puzzle difficulty should be left out of the equation altogether from the get-go or, at least qualified such as 'this puzzle may be easy/difficult for a human solver because...'.


denis berthier
The rules I've defined don't depend on any computer implementation. They are used everyday by human players. You're allergic to computers and that's your right.


I both programmed and sold a sizeable business computer software package for several years so not only am I not 'allergic to computers', but also I am particularly aware of how easily that computer output can be relied upon to the point that the results are confused with what is possible from human effort. On the other hand, I would suggest that you are so wedded to the use of a computer output that you have lost sight of when you are crossing the line to the point of drawing conclusions that your data does not support such as whether it is relevant to the everyday human solver (as you inferred in another thread) and whether the puzzle is easy or hard (as you did in this thread). I will leave it at that.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby denis_berthier » Thu Oct 02, 2008 11:28 pm

DonM wrote:No, please re-read: I was saying the number of steps may be a measure of difficulty.

You said "it may be a measure or it may not be depending on the puzzle and the construct of the steps themselves."
Therefore, you're saying it can't be a measure in itself: the nature of the steps must be taken into account.

DonM wrote:On the other hand, I would suggest that you are so wedded to the use of a computer output that you have lost sight of when you are crossing the line to the point of drawing conclusions that your data does not support such as whether it is relevant to the everyday human solver (as you inferred in another thread) and whether the puzzle is easy or hard (as you did in this thread).

I can do some programming, but I'm not a programmer. I'm a mathematician.
All my approach is based on defining a logical framework modelling the one used by human players. But I never suggested that human players are logical machines or behave like computers - what you're criticising is your own imagination.
As you don't support with any evidence your comments about "drawing conclusions that your data does (sic) not support", there's nothing to answer.

I never say that a puzzle is easy or hard, but that it is easy or hard according to some rating system. And, if you read my rating thread, you'll see that I repeat every time I can that I don't believe in any universal rating system.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Oct 03, 2008 12:00 am

Hi Allan,
Allan Barker wrote:
Denis wrote:One could argue that, as the result of T&E can always be obtained by braids, which are a kind of pattern, then it is absurd to reject T&E as a resolution technique.

I have the same questions. In the FM thread, I mentioned that my 'solver' uses only sets and works at the permutation level. Starting a set {A,B,C,D} will generate 4 initial permutations whose children must all be of the form AXXX, BXXX, CXXX, or DXXX. One of these families contains the solution and the others contain a contradiction.
I have long realized that starting a complete set might be interpreted as a hidden form of T&E. On the otherhand, the process proceeds by adding only more sets and never requires any kind of guessing or even, in principle, <if> logic. So, where is the T&E? Conclusion: I haven't been able to sleep.:)

Fortunately for me, sudoku has never yet prevented me from sleeping.:)
There are versions of T&E that only add information and do no guessing; it's only a matter of programming choices.
It is difficult to answer about your solver:
- firstly, because, although I find your approach very interesting (with a sound mathematical grounding, contrary to many things discussed in this forum), I've never had all the time I wanted to study it in detail; it's still on my todo list but I've always several irons in the fire;
- secondly, I understand the maths of your approach but I have only a vague idea of their implementation in your solver; what I understood is that there are two different processes: solving and interpreting. It might be the case that the solving part is some hidden form of T&E and the interpretation part consists of extracting patterns from it. At the risk of upsetting Champagne once more, I'd say it is the difference between the short time (a few seconds) his solver needed to solve EM with tagging and the time (a few months) he needed to extract manually something readable from the computer output;
- indeed, I don't think T&E has much meaning in the context of second order logic, because nothing prevents one from defining it in terms of sets.

Allan Barker wrote:That leads to a question that applies equally to myself, to which I don't know the answer. If braids are equal to, or can do the same as, T&E, can braids solve all puzzles and do so in a few milliseconds, like common back tracking (T&E). If not, then what is the difference?


Here, my answers can be very clear.

But, first a few precisions: the version of T&E I use in my theorem is not "common backtracking", it is T&E in the sense commonly accepted by sudoku players:
- if a hypothesis doesn't lead to a contradiction, no candidate is eliminated, nothing is done; in particular, if a hypothesis leads to a solution, it is not accepted, i.e. no value is asserted (this would be called "guessing");
- it is not recursive, but limited to depth 1 (only 1 hypothesis at a time);
- as a result, it is not guaranteed to solve any puzzle - and it doesn't.
(This T&E is not the same thing as the recursive rT&E procedure I used for another theorem in the "concept of a resolution rule" thread - a name obviously ill chosen, if I consider the comments it raised).


1) Braids can't solve all the puzzles. They can solve all the puzzles that can be solved by T&E as defined above. These are almost all the puzzles (all in 1,000,000 of puzzles randomly generated by suexg - almost all upto SER 10.x in gsf's list of harderst), but not all of them.

2) In order to solve all the known puzzles, I have to extend ordinary T&E i.e. T&E(NS+HS) to depth 2, or use T&E(braids) at depth 1.

3) I'ven't yet implemented braids as such in SudoRules and I don't know if I'll do it (I currently don't have much time). But if I do it, it is certain that they won't solve in a few milliseconds all the puzzles they can solve.
If I use the equivalence with T&E, then T&E can solve any of these puzzles in a few milliseconds. I did this on 1,000,000 puzzles.

4) So, what's the difference? It is the difference between knowing something can be done and having it done effectively. If I solve a puzzle using T&E, it will be very fast. Then if I use the solution path to replace each elimination step by a braid that will do the same job, following the proof of my theorem, I'll get a fast solution with braids.
But is this what I'm expecting from a solution with braids? One may say yes. It's a matter of taste.
But, personally, I say NO.
What I want is the "simplest" solution, with braids as short as possible, and in addition, a solution with no braids at all if there is one based on chains (or whips) only.
In this case, if I want to use T&E to build such a solution, I'll have to explore all the possible solution paths based on T&E and that'll be very long.

5) Should we accept braids (or nets in general) if we don't accept T&E? From the above, it should be clear that T&E and braids are not the same thing. They can do the same thing but they are not the same thing.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Fri Oct 03, 2008 9:34 pm

one used by human players


i am a human player and i am telling you that your solving method is not any more clear nor conciese to the practicall application or even close to what a human can or cannot conceive on any given value seen or not seen.

a player is limited to skill. visual cues and degree of reasoning.
memory allocation as well.

a player learns.

each player sees diffrent adaptations of mnay given moves.
they are both simplistic and or complex.

a puzzle can collapse by many many simplistic adapations of moves.
or few complex ones.

you always list long chains of small moves. leading up to a hard move and justifing it as the most advance move needed.

it is not a question of what is needed its a apllication question. how many diffirent ways can i approach the puzzle?

if a puzzle has many options at each point of a solving path many more players with diffrent degrees of skill are open to solving the puzzle.

i have clearly listed this issue in my reply to rating a puzzle.

this was not my point here at all.

where is your human replication of visual bases? we can see complexities as well.
you are only focused on the simplistic version. we can comprehed and apply both. and may even fail to see the easer stuff as well.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby denis_berthier » Fri Oct 03, 2008 11:29 pm

StrmCkr wrote:i am a human player and i am telling you that your solving method is not any more clear nor conciese to the practicall application or even close to what a human can or cannot conceive on any given value seen or not seen.

What I discuss in this forum is resolution rules, which can be used by anyone independently of any solving method. The examples I give have only one purpose: illustrating how these rules work.
Concerning my rules, other human players use them daily and they combine them freely with other rules. See the sudoku-factory forum.

StrmCkr wrote:you always list long chains of small moves. leading up to a hard move and justifing it as the most advance move needed.

Not "the most advanced move needed" but "the length of the longest chain needed in any resolution path". That's very different. Many other paths are possible, but using my rules, you can't find one that will use only strictly shorter chains. Of course, if other rules are added, this may produce shorter chains (but this is the case for any set of rules).
What anyone can give is always ONE resolution path chosen between many different ones, according to some criterion.
But I have no global rigid solving method.

I think you are confusing two levels:
- the logic level, which is the level where resolution rules are defined and associated elimination theorems are proven once and for all;
- what I've called the strategic level, which is a heuristic level where different ways of using resolution rules are defined.

At the logic level, the purpose of any solver can't be to simulate a human player. In my approach, with the help of the SudoRules implementation, it is to explore the solving potential of some types of rules that human players can use independently in all the ways they like (notice that some existing solvers don't even have this purpose). It was also for me to check that I had forgotten no subtle conditions in my rules. In this process of formalising the logic of my first rules, I was led to powerful generalisations.

I know that, in SudoRules, as in any existing solver, the strategic level is very poor. SudoRules has all the logic tools allowing to define many different strategies. But what we all miss is knowledge about such players strategies. What you can see in any book about Sudoku is definition of rules and examples, but you can never see much about which patterns to look for on a grid in function of the current situation.
A human player is likely to have a very oportunistic strategy; a computer program always has a more rigid one; in SudoRules, the default strategy is biased towards short chains (with the advantage of producing the NRCZT rating of a puzzle); but other strategies may be defined. You should not confuse the rigidity of this default strategy with the many ways my rules can be used.
I've been planning for some time to write something about different types of resolution strategies one can define in general (and implement in SudoRules in particular) but I haven't yet had time. Be patient.

StrmCkr wrote:where is your human replication of visual bases? we can see complexities as well.

What visual clues are you speaking of? Can you give examples? Do you know any computer program that uses such clues?
I'd be very interested in any clear information on this.
Nothing in my approach prevents me from defining strategies based on visual clues, if such clues can be defined clearly. And if they can't, no solver will be able to use them.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sat Oct 04, 2008 2:03 am

denis_berthier wrote:What I want is the "simplest" solution, with braids as short as possible, and in addition, a solution with no braids at all if there is one based on chains (or whips) only.

Denis, the braid term already has a different meaning. See http://www.sudopedia.org/wiki/Braid_Analysis
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby denis_berthier » Sat Oct 04, 2008 2:18 am

ronk wrote:
denis_berthier wrote:What I want is the "simplest" solution, with braids as short as possible, and in addition, a solution with no braids at all if there is one based on chains (or whips) only.

Denis, the braid term already has a different meaning. See http://www.sudopedia.org/wiki/Braid_Analysis

Thanks for signalling this. But the possible alternative term (rope) is also already used.
I think there can't be any ambiguity because the two notions are unrelated and I always use qualifiers when it is not clear from the context: nrczt-braids.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby coloin » Sat Oct 04, 2008 4:44 am

Well , i thought it made sense:!:

using braid analysis [original def] could be used as a way of identifying the best level 4 tagging process.

c
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby denis_berthier » Sat Oct 04, 2008 5:01 am

coloin wrote:using braid analysis [original def] could be used as a way of identifying the best level 4 tagging process.

As you know that tagging is totally foreign to my approach, I can't make any sense of your post.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby DonM » Sat Oct 04, 2008 10:57 am

D.Berthier: Concerning my rules, other human players use them daily and they combine them freely with other rules. See the sudoku-factory forum.

Let's just keep this real. This is a bare handful of people. There's no doubt in my mind that humans can apply some of your methods to puzzles. The real question is whether most of us want to apply a few basic methods and then blow the puzzle up with a stick of dynamite. But more importantly, a mathematician should know that the exception doesn't prove the rule.

Again, your theory and threads are interesting, but the application to practical human solving is very much less than clear.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby denis_berthier » Sat Oct 04, 2008 12:07 pm

DonM wrote:D.Berthier: Concerning my rules, other human players use them daily and they combine them freely with other rules. See the sudoku-factory forum.
Let's just keep this real. This is a bare handful of people.

And you're ONE player. This handful of people are certainly among the best players in the world.
How many real players give their opinion here, among the millions all around the world?
What's the proportion of real players who know more than singles and pairs?

DonM wrote:There's no doubt in my mind that humans can apply some of your methods to puzzles. The real question is whether most of us want to apply a few basic methods and then blow the puzzle up with a stick of dynamite.

Who is "most of us"? Millions of players or a few among those that post here?
I've always said that everyone uses the rules he wants - including me. If playing with my stick of dynamite brings new results, as it still seems to do, why should I not do it?
I'm a researcher, I'm not looking for groupies. Time will tell what will remain and what will be forgotten.
If you prefer spending your time on things such as the thousand variants of fish, degenerate or not, sashimi or sushi or grilled, finned or not, filleted or not, with scales or fur, I have no objection. I even think there are a few interesting things among this fauna. But it is clear that the scope of what all this can solve is very different from the scope of the rules I'm dealing with.
If you prefer spending your time on falsely new patterns using ghost candidates or on other pseudo-patterns based on flawed logic, I have no objection. I'll just ask: is there any "application to practical human solving "?
But in the name of what would you prevent me from spending my time on things that interest me?

It's not an alternative: either my rules and Hell or your rules and Heaven. All the rules can be mixed.
As I'm exploring the potential of my set of rules, mixing them with lots of different ones would not prove much. But, in practice, a player can mix all the rules he wants.

DonM wrote:Again, your theory and threads are interesting, but the application to practical human solving is very much less than clear.

It is clear at least for those who tried to do it - even if they were only a handful. Did you ever try?
Did you ever try the progressive approach I've been advocating, using the extended sudoku board: xyt, hxyt, xyzt, hxyzt, nrct, nrczt ?
Did you ever look at the sudoku-factory forum to see how human players (whom I don't know more than I know you) use these rules in practice?
And if what I write is unclear for some players, why don't you undertake the task of writing a player's manual for my rules? Why should I do all the work alone?
My "job" is exploring the possibilities. It's your "job" to use (or decide to ignore) my results.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby DonM » Sat Oct 04, 2008 3:10 pm

DonM wrote:There's no doubt in my mind that humans can apply some of your methods to puzzles. The real question is whether most of us want to apply a few basic methods and then blow the puzzle up with a stick of dynamite.


denis_berthier wrote:Who is "most of us"? Millions of players or a few among those that post here?


'Most of us' would include the many (which doesn't include me) who have developed all of the various patterns and chains including fish & all their variants which, from your comments above you seem to look down your nose at, and the many of us (which does include me) who have spent a lot of time learning & using those methods over the last 3 years.

denis_berthier wrote:If you prefer spending your time on falsely new patterns using ghost candidates or on other pseudo-patterns based on flawed logic, I have no objection. I'll just ask: is there any "application to practical human solving "?


I have no idea what you're talking about.

denis_berthier wrote:But in the name of what would you prevent me from spending my time on things that interest me? It's not an alternative: either my rules and Hell or your rules and Heaven. All the rules can be mixed. As I'm exploring the potential of my set of rules, mixing them with lots of different ones would not prove much. But, in practice, a player can mix all the rules he wants.

Did you ever try the progressive approach I've been advocating, using the extended sudoku board: xyt, hxyt, xyzt, hxyzt, nrct, nrczt ?
Did you ever look at the sudoku-factory forum to see how human players (whom I don't know more than I know you) use these rules in practice?

And if what I write is unclear for some players, why don't you undertake the task of writing a player's manual for my rules? Why should I do all the work alone? My "job" is exploring the possibilities. It's your "job" to use (or decide to ignore) my results.


This is the crux of the issue I have. You are proposing new methods for players, methods that are totally different from the 'conventional methods'. I purchased your book and have studied the information in it and in your threads enough to know that on the one hand the methods & proposals are ingenious and even brilliant in concept. But, on the other hand, I have been totally dismayed at the disconnect between the brilliance of the concept and the almost total lack of an attempt to describe how it can be learned and applied for use by mere mortals, not to mention the daunting reliance on computer solver output for virtually every example in the book and in your threads here.

My core point is that if you are proposing your methods as an alternative way for humans to solve sudoku and if you are going to make value judgements as to their applicability to the everyday solver and/or the difficulty of puzzles then it is your job, not mine, to provide tutorials or manuals describing your methods. How can you expect the average human solver to commit to learning your methods when all you every use yourself is a computer solver and its output both here and in the book. How reassuring is it for the prospective player that he/she is not wasting their time learning methods that are allegedly applicable to manual solving when even the author doesn't solve with them manually and has never so much as provided at most a tutorial or at least some examples of manual solving?

However you may view the traditional methods that you appear to see your methods as being a replacement for, the fact is that the great contribution of the Player's forum has been to act as a source for manually-derived practical examples that have presented and described all the various 'traditional' methods over the last 3 years, examples that show how the methods can actually be manually applied.

Finally, make no mistake, I have no basic issue with your methods or your threads (although, digressing, from what I can see I prefer traditional methods). What I have a problem with is your directly or indirectly making assumptions as to their applicability to human solving when you have provided very little or no foundation for those assumptions.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

PreviousNext

Return to Advanced solving techniques