FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    xyt-chains Goto page 1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Fri Jun 15, 2007 1:20 pm    Post subject: xyt-chains Let me first introduce my representation of an xy-chain (of length 4): {1 2} - {2 3} - {3 4} - {4 1}. Here "-" stands for any type of link (row, column or block/box as you prefer) and 1, 2, 3, 4 are any values (they may be considered as shorthands for variables x1, x2, x3, x4). The curly brackets indicate that the sets of values in each cell of the chain are limited to the instantiations of the variables displayed. The xy-chain rule (as I formulate it) says that one can eliminate x1 from any target cell (any cell that shares a unit with both endpoints). In my book ("The Hidden Logic of Sudoku"), I define xyt-chains as a generalisation of xy-chains. The idea is that in an xy-chain a cell C in the chain may be allowed any additional value provided that this value is the right linking value of a previous cell C' in the chain such that C shares a unit with C'. Note that, whereas xy-chains are symmetric (head and tail can be reversed), this is no longer the case for xyt-chains. But the underlying logic is very similar and proving the validity of the xyt-chain rule : (one can eliminate x1 from any target cell) can be done straightforwardly, along the same lines as for an xy-chain. An xyt-chain (of length 4) is represented by the following pattern: {1 2} - {2 3} - {3 4 (2#1)} - {4 1 (2#1)(3#2)} , where values between normal brackets inside a cell are optional and are allowed in a cell provided this cell is linked to the cell whose number in the chain follows the # sign. In details: - cell 1 has exactly the 2 different values x1 and x2, - cell 2 has exactly the 2 different values x2 and x3, - cell 3 has the 2 different values x3 and x4 and it may have additional value x2, provided cell 3 is linked to cell 1, - cell 4 has the 2 different values x4 and x1 and it may have additional value x2 provided it is linked to cell 1 and it may have additional value x3 provided it is linked to cell 2. Similar definitions and representations apply for longerchains. In any case, the farther we go towards the tail of the chain, the more additional values we may have. Here is a simple example taken from my book (This is obtained from Royle17-2769, with obvious initial inferences) This example cannot be solved using only rules at level L4_0 of my hierarchy (for a definition of my levels, see my post "large families of rules) together with xy-chains, c-chains (and hidden xy-chains) of length 4 or less. But it can be solved simply with an xyt4 chain. 946512738 528600194 100849256 281405000 054000810 069108540 615084320 800201405 402050081 Solution path: number 6 : row R5 interaction with block B5 ==> 6 eliminated from the candidates for R4C5 number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3 ==> 9 eliminated from the candidates for R9C2 number 9 : hidden-single-in-block B7 ==> R8C2 = 9 number 9 : column C5 interaction with block B5 ==> 9 eliminated from the candidates for R5C4 numbers 3 and 7 : naked-pairs-in-row R5: R5C1-R5C4 ==> 7 eliminated from the candidates for R5C9 ==> 3 eliminated from the candidates for R5C9 ==> 7 eliminated from the candidates for R5C6 ==> 3 eliminated from the candidates for R5C6 ...(Naked-Singles and Hidden-Singles) 946512738 528637194 137849256 281475963 754396812 369128547 615784329 893261475 472953681 xyt-chains (of any length) are a very powerful tool, they can solve many more puzzles than simple xy-chains.They often make it unnecessary to use the notion of almost locked set. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Jun 15, 2007 10:46 pm    Post subject: In this puzzle, a simple unique rectangle in r38c23 is a much easier step. It would support your case better if you could provide an example that really simplifies the solving path. Also, this type of subnetting has already been introduced in early adaptations of Nice Loops. Carcul and Gurth often use these in their solutions. The lack of reversability brings it into the realm of T&E, which many consider a borderline solving technique. I never built it into my solver because it does not provide an acceptable alternative to table solving. Ruud _________________ Meet me at sudocue.net Back to top wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Fri Jun 15, 2007 11:25 pm    Post subject: Ruud wrote: I never built it into my solver because it does not provide an acceptable alternative to table solving. Ruud Just to clarify Ruud, table solving is a complex logical operation that humans would be unlikely to do? Back to top berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Sat Jun 16, 2007 7:19 am    Post subject: Ruud wrote: In this puzzle, a simple unique rectangle in r38c23 is a much easier step. It would support your case better if you could provide an example that really simplifies the solving path. Unique Rectangle supposes uniqueness, which my solution does not. Anyway, I'll post another example later. Ruud wrote: Also, this type of subnetting has already been introduced in early adaptations of Nice Loops. Carcul and Gurth often use these in their solutions. The lack of reversability brings it into the realm of T&E, which many consider a borderline solving technique. I never built it into my solver because it does not provide an acceptable alternative to table solving. Ruud The xyt-chain rule says: whenever you have detected an xyt-chain, then eliminate x1 from any cell that shares a unit with both endpoints. This elimination is definitive. Where do you see T&E here? xyt-chains are not nets but real chains. xyt-chains cannot be an adaptation of nice loops since they are not loops at all. I don't understand what you mean by: "there is no reversibility". In comparison, table solving is a very complex technique. For more information on xyt-chains, see also my posts on the sudoku.org.uk forum (threads on Eureka) Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Sat Jun 16, 2007 11:33 am    Post subject: wapati wrote: Just to clarify Ruud, table solving is a complex logical operation that humans would be unlikely to do? Yes. berthier wrote: The xyt-chain rule says: whenever you have detected an xyt-chain, then eliminate x1 from any cell that shares a unit with both endpoints. This elimination is definitive. Where do you see T&E here? xyt-chains are not nets but real chains. xyt-chains cannot be an adaptation of nice loops since they are not loops at all. I don't understand what you mean by: "there is no reversibility". Unlike xy-chains, the implication stream only flows in a single direction. The bottom line of an xyt-chain is: IF a<>X THEN z=X, whereas xy-chains say: IF a<>X THEN z=X AND IF z<>X THEN a=X, which can be simplified to a=X OR z=X. I'm sure you can see the reversability in this. The only difference between chains and loops is that the "victim" is included in a loop, where it is excluded from chains. However, "any cell that can see both end points" closes the loop. The difference between chains and nets is that chains follow a single implication stream, whereas nets branch and merge, thus combining implications. When you only look at the cells, the xyt-chain looks like a chain, but when you look at the implication stream, you are branching and merging. Let's break down your example: r9c2=9 => r9c8<>9 => r9c8=6 => r8c8<>6 => r8c8=7 r8c8=7 => r8c2<>7 r8c8=7 => r8c3<>7 => r8c3=3 => r8c2<>3 r8c2<>{3,7} => r8c2=9 => r9c2<>9 I definitely see branching and merging in this chain... About T&E: Since the implication stream is unidirectional, there is not a significant difference between your chain and finding a contradiction based on the assumption that r9c2=9. That, of course, is a personal opinion. Ruud _________________ Meet me at sudocue.net Back to top Steve Joined: 12 Apr 2006 Posts: 12 : Items Posted: Sun Jun 17, 2007 3:54 am    Post subject: I don’t know which side of the fence I’m on here. Berthier’s description of the method certainly involves branching in the general case. I do not share Ruud’s view that this is unacceptable. More to the point I do not believe that the chains produced are “irreversible.” What you get is a compound nice chain (or net, if you prefer) which can be read from right to left as well as left to right. It would not make the eliminations it does if this were not the case. My analysis of the example puzzle is the same as Ruud’s. The elimination may be written as a simple nice als loop: r9c2 -9- r9c8 – 6- r8c8 -7- {r8c2, r8c3} -9- r9c2 This illustrates the point that branching does not follow in all cases, just in some. In others the connections between some cells will be such that they may be amalgamated as almost locked sets. Steve Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Sun Jun 17, 2007 10:35 am    Post subject: Steve: The loop is reversable if you allow ALS into it. As far as I understood Berthier's posts here and on the UK forum, he does not (want to) consider ALS. The AIC for this loop is: (9)r9c2 - (9&37)r8c23 - (7=6)r8c8 - (6=9)r9c7 - (9)r9c2 When the xyt rules as described by Berthier are strictly followed, it is still possible to create chains in both directions, but these are slightly different: r8c3 > r8c2 > r8c8 > r9c7 vs. r8c2 < r8c3 < r8c8 < r9c7 Also, when r8c3 would have an extra candidate 9, the xyt chain can no longer be made, but the nice loop with the embedded ALS would still hold. My main concern is that this is presented as a new technique, although it has been known in the Sudoku community for a (relatively) long time. I've read similar objections to other "new" ideas by Berthier on the UK forum. Since I have not read Berthier's book yet, I cannot say that it does not introduce any new insights, but the bits he released so far look strangely familiar... Ruud Back to top berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Sun Jun 17, 2007 4:00 pm    Post subject: Steve, Ruud It may be the case that, in some particular examples, an xyt-chain is "reversible". But the general pattern is definitely NOT: {1 2} - {2 3} - {3 4 (2#1)} - {4 1 (2#1)(3#2)} (for length 4) Same thing for the proof of the rule, which goes from head to tail and cannot be reversed. Ruud wrote : Quote: The difference between chains and nets is that chains follow a single implication stream, whereas nets branch and merge, thus combining implications.When you only look at the cells, the xyt-chain looks like a chain Not "looks like" but "is". Ruud wrote : Quote: but when you look at the implication stream, you are branching and merging. The general proof of the xyt-chains rules relies only on reasoning by cases and on recursion on the length of the chain, two standard reasoning methods that no logician or mathematician would ever question. Unless you consider that any general mathematical proof that relies on reasoning by cases is "branching and merging", I can't make any sense out of this sentence. I think the point you are missing here is that an xyt-chain requires no reasoning of any kind on the part of the player. Just find on your grid the pattern defining this type of chain and apply the conclusion of the general rule, which has been proven once and for all in HLS. An xyt-chain does not include any loop. It does not rely on locked sets or on ALS. Since the xyt-chain resolution rules are more elementary than techniques relying on subsets (such as ALS) or on nets, the question I would logically ask is not whether they can be reduced to these techniques but conversely: do these complex techniques reduce to a combination of simpler rules (such as xyt-chains)? Or, in what cases don't they? At the present time I have no answer. Since my rules solve 97% of the randomly generated puzzles without resorting to these complex techniques (or to T&E), I'd be very interested to know about the remaining 3%, what gsf calls the "boundaries". Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jun 18, 2007 5:24 am    Post subject: berthier wrote: Since my rules solve 97% of the randomly generated puzzles without resorting to these complex techniques (or to T&E), I'd be very interested to know about the remaining 3%, what gsf calls the "boundaries". I've held off posting until I can check back on some random catalogs 1 with ~200M entries my main point about boundaries is that I don't think there is enough understanding about "random" puzzles to make any sense out of percentage claims there are so many ways for bias to enter the process it takes meticulous effort just to generate random solution grids look at the amount of work going into generating 17s how do we know that puzzles requiring "complex techniques" or "T&E" don't similarly foil our generators Back to top berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Mon Jun 18, 2007 8:41 am    Post subject: gsf wrote: berthier wrote: Since my rules solve 97% of the randomly generated puzzles without resorting to these complex techniques (or to T&E), I'd be very interested to know about the remaining 3%, what gsf calls the "boundaries". I've held off posting until I can check back on some random catalogs 1 with ~200M entries my main point about boundaries is that I don't think there is enough understanding about "random" puzzles to make any sense out of percentage claims there are so many ways for bias to enter the process it takes meticulous effort just to generate random solution grids look at the amount of work going into generating 17s how do we know that puzzles requiring "complex techniques" or "T&E" don't similarly foil our generators We already had this discussion on another forum. If you don't admit the randomness of generators and statistics in general, what could you CHECK on some RANDOM catalogs? Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jun 18, 2007 4:54 pm    Post subject: berthier wrote: We already had this discussion on another forum. If you don't admit the randomness of generators and statistics in general, what could you CHECK on some RANDOM catalogs? I apologize for posting to the wrong thread I don't dispute that bias can be removed from generating random solution grids, I don't dispute the statstics derived from such unbiased generators, I don't dispute the statistics that you have derived from the puzzles you have generated I do dispute that reliable solver-independent statistics can be derived from a miniscule sample of puzzles from one black-box generator specifically, I dispute that the (paraphrased) claim "my solver solves 97% of the (pseudo) random puzzles that I generated" has any meaningful relationship with the set of all puzzles, especially when so little is known about both your generator and the set of all puzzles Quote: what could you CHECK on some RANDOM catalogs? I could check for variations among the output of different generators we barely have a handle on characterizing the ~5e9 solution grids pick any one of them, and, besides unavoidable sets and automorphisms, we have almost no claims about the puzzles it contains Back to top berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Tue Jun 19, 2007 4:57 am    Post subject: gsf wrote: I don't dispute that bias can be removed from generating random solution grids, I don't dispute the statstics derived from such unbiased generators, I don't dispute the statistics that you have derived from the puzzles you have generated I do dispute that reliable solver-independent statistics can be derived from a miniscule sample of puzzles from one black-box generator Then what you are disputing is the basic principles of statistics. The precision of statistics obtained from random samples depends only on the size of the sample and NOT AT ALL on the size of the whole population. Said otherwise, with a random sample of 10,000 puzzles, the statistics you get are as good if there are bilions of billions of puzzles as if there were only 1 million. It may be counter intuitive, but that's how it is. Moreover, if there is any very rare pattern in the whole population and your sample doesn't contain any instance of it, that doesn't change the global statistics. The only thing that could be disputed here is the randomness of the sample. gsf wrote: specifically, I dispute that the (paraphrased) claim "my solver solves 97% of the (pseudo) random puzzles that I generated" has any meaningful relationship with the set of all puzzles, especially when so little is known about both your generator and the set of all puzzles First, it is not my generator, as your paraphrase suggests, but suexco from Magictour, in the development of which I've never been involved and whose generating principles are widely available. Second, I haven't modified it to fit any particular needs and you can re-generate my list yourself (I've even given the two seeds, 0 and 17, I used for the random numbers generator). I've used this generator because it was the only one I could find and run. gsf wrote: Denis wrote: what could you CHECK on some RANDOM catalogs? I could check for variations among the output of different generators we barely have a handle on characterizing the ~5e9 solution grids pick any one of them, and, besides unavoidable sets and automorphisms, we have almost no claims about the puzzles it contains Then, if you want everybody to benefit from this discussion, could you tell us which generators and where they are available? I'm most eager to try my solver on collections generated with various random generators. As I said in another thread, that's one way of avoiding potential bias in one single generator. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Tue Jun 19, 2007 5:45 am    Post subject: berthier wrote: Then what you are disputing is the basic principles of statistics. The precision of statistics obtained from random samples depends only on the size of the sample and NOT AT ALL on the size of the whole population. Said otherwise, with a random sample of 10,000 puzzles, the statistics you get are as good if there are bilions of billions of puzzles as if there were only 1 million. It may be counter intuitive, but that's how it is. Moreover, if there is any very rare pattern in the whole population and your sample doesn't contain any instance of it, that doesn't change the global statistics. The only thing that could be disputed here is the randomness of the sample. there are limits to the random sample principle based on the reasonable expectation of the size of the whole population 10^4 is representative -- by what criterion? an estimate of the total number of valid sudoku puzzles is 10^45 is 10^4 (miniscule in my post) a reasonable sample of that? Quote: gsf wrote: specifically, I dispute that the (paraphrased) claim "my solver solves 97% of the (pseudo) random puzzles that I generated" has any meaningful relationship with the set of all puzzles, especially when so little is known about both your generator and the set of all puzzles First, it is not my generator, as your paraphrase suggests, but suexco from Magictour, in the development of which I've never been involved and whose generating principles are widely available. Second, I haven't modified it to fit any particular needs and you can re-generate my list yourself (I've even given the two seeds, 0 and 17, I used for the random numbers generator). I've used this generator because it was the only one I could find and run. I did not purchase your book I have only read and responded to the posts on the players and programmers forums you mentioned random puzzles but not the source Denis wrote: Then, if you want everybody to benefit from this discussion, could you tell us which generators and where they are available? I'm most eager to try my solver on collections generated with various random generators. As I said in another thread, that's one way of avoiding potential bias in one single generator. in-forum search and/or google will point to numerous catalogs and generator programs I don't recall any requests for help from you on generators or how to run them in the forums the "constrained puzzles" thread from september 2005 has some stats on dukosu's and one of my old generators that started from an empty grid (my current generator starts from completed grids) those discussions show a non-trivial variance in the average number of clues in minimal puzzles from the various generation strategies there's ~130K puzzles on my site, along with documentation on how to generate puzzles with my solver there's gfroyles 22M 18s there's the collection of top* catalogs there's ruud's catalogs, including a new top10000 and numerous other "top" lists by the many forum contributors along with several method taxonomy catalogs some of the catalogs are general, some are targeted for specific constraint methods, some are targeted to foil all known constraint methods Back to top wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Tue Jun 19, 2007 6:20 am    Post subject: gsf wrote: I don't dispute that bias can be removed from generating random solution grids, We do not have a reliable random generator. They all need to be accepted for their limited bias. Back to top berthier Joined: 13 Jun 2007 Posts: 43 : Location: Paris, France Items Posted: Tue Jun 19, 2007 8:08 am    Post subject: gsf wrote: there are limits to the random sample principle based on the reasonable expectation of the size of the whole population No. Precison of the statistics on percentages are totally independent on the size of the population. See any elementary textbook on statistics (section on estimation of percentages and on confidence intervals). And 10,000 is a rather large sample size, much larger than any sample used in practice for ordinary statistics. It allows very good statistics except for rare events. For instance, for the 97% evaluation of the percentage of puzzles solved by SudoRules without T&E, it gives for the width of the confidence interval : 1% at the risk level of 5% 1,6% at the risk level of 5% Which means that I can state that SudoRules solves the following proportions of randomly generated puzzles: between 96% and 98% with a risk of error of 5%, between 95,4% and 98,6% with a risk of error of 1%. Of course, this supposes that the suexco generator is random, which is, as I said previously, the only question that can rationally be debated. gsf wrote: in-forum search and/or google will point to numerous catalogs and generator programs I don't recall any requests for help from you on generators or how to run them in the forums the "constrained puzzles" thread from september 2005 has some stats on dukosu's and one of my old generators that started from an empty grid (my current generator starts from completed grids) those discussions show a non-trivial variance in the average number of clues in minimal puzzles from the various generation strategies gsf, thanks for your spontaneous help. For all we know, the number of clues in a minimal puzzle is unrelated to the complexity of the rules necessary to solve it. This is one thing I could easily check on the collections I use. As a result, a generator may not be random if we consider it from the viewpoint of the number of clues but may nevertheless be random if we consider it from the viewpoint of, say, the complexities of the puzzles it generates. gsf wrote: there's ~130K puzzles on my site, along with documentation on how to generate puzzles with my solver there's gfroyles 22M 18s there's the collection of top* catalogs there's ruud's catalogs, including a new top10000 and numerous other "top" lists by the many forum contributors along with several method taxonomy catalogs some of the catalogs are general, some are targeted for specific constraint methods, some are targeted to foil all known constraint methods Yes, but this is a mixture of random and non random generators or collections. By definition, catalogs top-something are not random. Could you tell me which genrator(s) (one or two, preferably based on different generation principles) YOU would accept as random? It'd be a pleasure for me to run my solver on other random collections. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page 1, 2, 3  Next Page 1 of 3   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron