FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Confused over Colouring Goto page Previous  1, 2, 3          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 12:04 pm    Post subject: coconut wrote: Perhaps, I shouldnt have mentioned nishio since it is not always consider as a "logical step". That's not a problem with me - nishio is undoubtedly a logical procedure. What I'm saying is that it is more difficult to apply than coloring, because you have to guess on which cell to apply it to. And you have to try all possible numbers (usually two) on that cell if you want to be sure to prove the solution is unique. Coloring doesn't require any of that. You color, then deduct. Back to top coconut Joined: 13 May 2005 Posts: 12 : Location: Oxford Items Posted: Wed Jul 06, 2005 1:25 pm    Post subject: Just a note on notation. Isnt it better to denote the conjugate of a as a* instead of b? This will be more concise and informative. coconut Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Wed Jul 06, 2005 1:35 pm    Post subject: coconut wrote: Just a note on notation. Isnt it better to denote the conjugate of a as a* instead of b? This will be more concise and informative. No, I personally would discourage that. It'd require all grids to be 2 chars wide for each digit, breaking the existing convention for text grids and also make it harder to visualize. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 1:51 pm    Post subject: coconut wrote: Just a note on notation. Isnt it better to denote the conjugate of a as a* instead of b? This will be more concise and informative. I don't like a/b myself, but a* is two characters so it complicates things on the screen. I had thought of using lower and upper case: Aa, Bb, Cc ... but when you get to Cc you have a problem on paper Back to top Goran Joined: 13 Aug 2005 Posts: 10 : Items Posted: Fri Sep 02, 2005 6:19 pm    Post subject: Does colouring subsume other rules/techniques? I'm impressed by what seems to be an ongoing colloborative effort by some of you deep guys on this and other forums (same guys :-), where you seem to have discovered and named solving techniques over the last months. Colouring seem to have arrived later, thus this question: Does removal of candidates by colouring subsume other techniques, for instance XY-wings, Swordfish, and possibly other exotic named ones? I mean, is it the case that colouring is more powerful and always discovers the same eliminations as the other ones, but possibly more? Best, Goran Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Fri Sep 02, 2005 10:09 pm    Post subject: Re: Does colouring subsume other rules/techniques? Goran wrote: I mean, is it the case that colouring is more powerful and always discovers the same eliminations as the other ones, but possibly more? No. There may be some overlap but they are different weapons for different occasions. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sat Sep 03, 2005 12:35 am    Post subject: Re: Does colouring subsume other rules/techniques? Goran wrote: I'm impressed by what seems to be an ongoing colloborative effort by some of you deep guys on this and other forums (same guys , where you seem to have discovered and named solving techniques over the last months. Colouring seem to have arrived later, thus this question: Does removal of candidates by colouring subsume other techniques, for instance XY-wings, Swordfish, and possibly other exotic named ones? I mean, is it the case that colouring is more powerful and always discovers the same eliminations as the other ones, but possibly more? Best, Goran Ultracolouring (i.e. version 3 of colouring with multi-possible contradictions and ver(ac)ities) does seem to subsume all winged and fishy variants - and seems to be able to solve all published Nishio puzzles - but does not yet quite match the power of tabling - this is still under investigation. However, the big problem with anything more than simple colouring is that its solutions are quite unintelligible by humans - even those who programmed it It does not always find the most obvious solution routes for complex puzzles, but its behaviour with simple puzzles (e.g. Times fiendish) is more predictable AMcK Back to top Goran Joined: 13 Aug 2005 Posts: 10 : Items Posted: Sat Sep 03, 2005 7:44 am    Post subject: On programming tabling The basic idea behind tabling, i.e. following assertions and implications, is lovely. Could any one of you who have implemented it hint on how you implemented it? I presume you did not build a complete Prolog evaluator? And I have read dark hints about Knuth's Dancing Links algorithm... Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sat Sep 03, 2005 9:23 am    Post subject: Re: On programming tabling Goran wrote: The basic idea behind tabling, i.e. following assertions and implications, is lovely. Could any one of you who have implemented it hint on how you implemented it? I presume you did not build a complete Prolog evaluator? And I have read dark hints about Knuth's Dancing Links algorithm... Following assertions does not seem to require Prolog or Dancing Links, since all you're doing is scanning the partial grid and recursively expanding the implications of SuDouk rules. Once you have a good data model for representing implication chains, the programming of the algorithm is relatively easy - particularly if you use matrices rather than tables. AMcK Back to top Goran Joined: 13 Aug 2005 Posts: 10 : Items Posted: Sat Sep 03, 2005 10:01 am    Post subject: AMcK wrote: --- Once you have a good data model for representing implication chains --- That's exactly what I was hoping to get some suggestions on :-) Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sat Sep 03, 2005 1:10 pm    Post subject: Goran wrote: AMcK wrote: --- Once you have a good data model for representing implication chains --- That's exactly what I was hoping to get some suggestions on OK, understood. This is what works for me - but bear in mind that I'm still tracking down some apparent blindspots so it's all subject to change. I use the following matrices excludes[u,v] if u -> ¬v and v -> ¬u a) u,v are colours using the same possible then they occur together in a house (row/column/box) b) u, v are colours using different possibles which sit in the same cell nexcludes[u,v] if excludes[¬u,¬v] implies[u,v] if u -> v impliesTF[u,v] if u -> ¬v impliesFT[u,v] if ¬u -> v impliesFF[u,v] if ¬u -> ¬v identical[u,v] if u -> v and ¬u -> ¬v and v -> u and ¬v -> ¬u conjugated[u,v] if u and v are conjugates a) if u,v are the only two instances of a given possible within a house b) if u,v are the only two possibles within a cell I know that this model is redundant, but it speeds up some of the ver(ac)ity searches and enables me to spot bugs as inconsistencies between the matrices. I know it's a bit clumsy but it is experimental and work in progress. I did consider 4D or 2Nx2N matrices as more elegant representations of the true/false implications and exclusions and will probably switch to one of these in the next version. Hope that helps Regards Andrew 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 Previous  1, 2, 3 Page 3 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