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 |
|
|
|