|
View previous topic :: View next topic |
Author |
Message |
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Sun Aug 07, 2005 9:41 am Post subject: Re: Nishio vs Supercolouring |
|
|
angusj wrote: | I guess that leaves Nick70 there on his lonesome. |
don't say that
angusj wrote: | On a related note - I do like advanced/super colourings from a theoretical perspective. However, I really can't see how it helps the average Joe Bloggs who wants to solve a puzzle visually (ie without the aid of a computer). |
I agree with that, that's the reason why I preferred to implement forcing chains. Forcing chains are much easier to understand, and it's easier for a solver to rate them. The problem with forcing chains is... finding them.
Supercoloring, on the other hand, is completely mechanical, and it finds all the implications that would derive from double forcing chains, all at the same time. It is efficient, but the conclusions it makes are difficult to understand. |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sun Aug 07, 2005 9:19 pm Post subject: Re: Nishio vs Supercolouring |
|
|
angusj wrote: | On a related note - I do like advanced/super colourings from a theoretical perspective. However, I really can't see how it helps the average Joe Bloggs who wants to solve a puzzle visually (ie without the aid of a computer) |
Yes, I agree. I can't speak for Nick's advanced coloring, since I've never seen the full algorithm. Simple colouring was conceived as a method of linking conjugate pairs together which could potentially be done by hand. Supercolouring identities simply extend these linked colours across different possible digits and then back to the original possible to reveal new conjugate pairs - this could also be done using coloured pencils. Implication chains and contradictions are harder to visualise but could I suppose be shown as coloured arrows superimposed on a big copy of the grid or just drawn off-sheet as arrows and boxes - just like fishy cycles and forcing chains.
The computer transcripts do look forbidding - but that's just because they merely walk through the underlying structure rather than revealing it.
It would be satisfying to know that the suspicious T&E of Nishio isn't necessary - even if it's only of use to computers. But you could argue that computing the implications of a colour is merely a stealthy surrogate from forcing a cell value and seeing what happens.
Andrew |
|
Back to top |
|
|
| Gennadog
| Joined: 03 Jun 2005 | Posts: 5 | : | | Items |
|
Posted: Mon Aug 08, 2005 8:12 am Post subject: Re: Nishio vs Supercolouring |
|
|
AMcK wrote: |
Don,
I've edited the original post to bring it up to date with the latest supercolourer transcript showing an identity and a conflict.
I still don't guarantee it's bug free but it's the general principles that matter. I may update it again to make it more usable.
I'm also 10 steps behind everybody else ... I've only now accepted n-swordfish as a necessary companion to supercolouring.
Regards
Andrew |
Thanks. I've actually found the "deliberate mistake' that I put into my own code to see if I was awake (!!!) [basically I was not implimenting the transitive closure properly - it was leaving out some possible values] and I can now obtain the same basic results as you describe.
I don't bother about renaming the colours when I find that they are "the same" - the additional stuffing about with my matricies and their various relationships is not worth it. It is easier to let the code run through a few more iterations for each colour.
Do you have any examples where the 'fishy cycles' are not covered by at least one of the colouring schemes?
Cheers,
Don |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Mon Aug 08, 2005 9:10 am Post subject: Re: Nishio vs Supercolouring |
|
|
Gennadog wrote: | Do you have any examples where the 'fishy cycles' are not covered by at least one of the colouring schemes? |
I've not had the time to implement fishy cycle/forcing chain algorithms myself since I'm too busy inserting bugs into my own code .
I tend to rely on others' postings and always check published examples. I do note that the cells targeted by forcing chains are almost always different from the ones where my code discovers colouring conflicts, which is worrying. This may be simply because each of us is choosing the first candidate of many, but it would be interesting at some stage to compare specific solutions.
FYI I'm currently working on a greatly simplified definition of "N-Wings" for N=3..8 with a high speed algorithm which almost but not quite works yet.
Andrew |
|
Back to top |
|
|
| Doug
| Joined: 28 May 2005 | Posts: 42 | : | | Items |
|
Posted: Mon Aug 08, 2005 10:41 am Post subject: |
|
|
I haven't proved this carefully, but I'm pretty sure that Fish Cycles is equivalent to Andrew's original coloring algorithm. So all extensions of it should cover FC as well.
Cheers,
Doug _________________ Doug Bowman
www.flickr.com/photos/bistrosavage |
|
Back to top |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Tue Aug 09, 2005 5:50 am Post subject: |
|
|
I think it's about time to explain my way to do "supercoloring". It is extremely simple and just needs one table. No need for a "conjugate" table, no need for a "implies" table.
1) Assign colors to conjugates
Assign a different colour pair to every chain of conjugate possibles in the partial grid. Use even/odd pairs of colors, so 0/1 are conjugate, 2/3 are conjugate, and so on. Using the dancing links data structures, this is done very easily and efficiently using a recursive algorithm.
At the end of step 1) all possibles that have a conjugate are colored, using the minimal number of colors. We don't need a "conjugate" table, because the conjugation property is embedded in the color.
Keep track of how many colors have been assigned to conjugates--I'll refer to this as Cc.
2) Assign colors to the remaining possibles
Scan the grid again and assign a unique color to all remaining possibles. To be consistent with step 1), each possible will be assigned an even color--4, 6, 8, and so on. Odd colors will not be used.
Keep track of how many colors have been assigned in total--I'll refer to this as Ct.
3) Create the exclusion table
excludes(x,y) = true if colors x and y exclude each other--that is they are the colors of two possibles in the same cell, or the colors of two possibles for the same number in a unit. Of course all conjugate pairs will be automatically added to the excludes table.
4) Compute the closure of the exclusion table
We need only one rule to do that:
if a excludes b and b is conjugate of c and c excludes d, then a excludes d. That's because:
- if a is true then b is false then c is true then d is false
- if d is true then c is false then b is true then a is false
Using our exclusion table, this becomes
if excludes(x,y) and excludes(y^1,z) then excludes(x,z)
5) Compute the truth table of colors
We need only one rule:
if excludes(x,x) then x is false
Strictly speaking, the solver can just limit to excluding all possibles that have a false color; due to the nature of conjugate pairs, big numbers will automatically be placed in the next step. We can do it as part of supercoloring however.
Note that 5) is better done as an integral part of 4) and 3), every time an exclusion is added to the table.
Finally, an important note about the efficiency of step 4).
A naive approach would scan the whole exclusion table repeatedly until no more new exclusions are found. This would have a cost of roughly Ct^3.
A substantially faster algorithm computes the closure in two steps, by observing that the colors above Cc don't have a conjugate, so they cannot be y in the if statement above. Actually, the only reason why we need to care about non-conjugate colors is to see if they are falsified by the conjugate ones. To check if x is falsified, we just need to do
if excludes(x,y) and excludes(x,z) and excludes(y^1,z^1) then x is false
Therefore:
- compute the closure of the exclusion table, limited to the first Cc colors
- check if the non-conjugate colors are falsified by the conjugate ones
This has an overall cost of roughly Cc^3 + Cc^2 (Ct - Cc) = Ct Cc^2
Last edited by Nick70 on Tue Aug 09, 2005 10:15 am; edited 1 time in total |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Tue Aug 09, 2005 8:19 am Post subject: |
|
|
Thanks for such a clear explanation. You originally called your approach "advanced" coloring and so I used the term "supercoloring" to differentiate mine - not to make it sound superior but so that there would be no confusion.
I certainly like your computational simplicity, although none of these matrix algorithms are slow on modern computers. I suspect that transitive closure of the implications will add more links that that of exclusions because of its asymmetry . This will take longer but does it add any value?
The reason I went down the "implication" approach is that I was looking for identity chains across different possibles that would allow recolouring to feed back into simple colouring. These were well illustrated in the recent Jellyfish example. You first showed me the power of contradictions - which your version does well - but can you do identities?
I might give it a try back-to-back.
Many thanks
Andrew |
|
Back to top |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Tue Aug 09, 2005 10:11 am Post subject: |
|
|
AMcK wrote: | Thanks for such a clear explanation. You originally called your approach "advanced" coloring and so I used the term "supercoloring" to differentiate mine - not to make it sound superior but so that there would be no confusion. |
Sure, that's not a problem. I called it "advanced" because it requires coloring the pencilmarks instead of the whole cells.
I also have to add that the algorithm I'm now using is a complete rewrite of the previous one, born after the fresh look you introduced starting this thread.
AMcK wrote: | I certainly like your computational simplicity, although none of these matrix algorithms are slow on modern computers. |
To solve a set of 16,000 hard puzzles, the initial implementation I made of supercoloring took 7 minutes. With the optimisations explained above, it's now below 2 minutes. So it's a significant improvement.
Of course, braindead backtracking still takes just 7 seconds.
AMcK wrote: | I suspect that transitive closure of the implications will add more links that that of exclusions because of its asymmetry . This will take longer but does it add any value? |
As I said somewhere else in the thread, if think it doesn't add value, on the contrary it decreases it because you might be missing some consequences of the coloring.
To derive an implication from two implications, you use two exclusions and two conjugations. To derive an exclusion from two exclusions, you use two exclusions and one conjugation. Therefore, you can prove more.
AMcK wrote: | You first showed me the power of contradictions - which your version does well - but can you do identities? |
Of course.
If excludes(x,y^1) and excludes(x^1,y) then x=y.
But I'm not using it since it isn't needed by the algorithm, and recoloring appears to be just a waste of time with the data structures I'm using. |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Tue Aug 09, 2005 10:46 pm Post subject: |
|
|
I can confirm that Nick's simpler approach of computing the transitive closure of excludes[] rather than implies[] seems to find all the contradictions.
Using droid42's first Swordfish example ...
Code: | 9 5 2a7a ¦ 6 3 1a2b ¦ 4 1b7b 8
3 2c7b8a 1 ¦ 4 5 2d8b ¦ 2e7a 6 9
2f8b 4 6 ¦ 9 2g7e 1b2h7f8a ¦ 3 5 1a2i
-----------------+------------------------+------------------
6 3a9a 4 ¦ 1 2j9b 5 ¦ 8 2k3b 7
5 2a7a 2b7b ¦ 3 8 6 ¦ 9 1a4a 1b4b
1 3b9b 8 ¦ 2n7e 2o7f9a 4 ¦ 5 2j3a 6
-----------------+------------------------+------------------
2q8a 6 3 ¦ 2r5a7b 4 9 ¦ 1 7a8b 2s5b
7 2f8b 9 ¦ 2u5b 1 3 ¦ 6 4b8a 2v4a5a
4 1 5 ¦ 8 6 2e7a ¦ 2i7b 9 3
|
Nick's approach produces:
Contradiction: 1b excludes 1b
Contradiction: 2b excludes 2b
Contradiction: 2c excludes 2c
Contradiction: 2d excludes 2d
Contradiction: 2f excludes 2f
Contradiction: 2h excludes 2h
Contradiction: 2i excludes 2i
Contradiction: 2j excludes 2j
Contradiction: 2o excludes 2o
Contradiction: 2r excludes 2r
Contradiction: 2s excludes 2s
Contradiction: 2u excludes 2u
Contradiction: 3b excludes 3b
Contradiction: 4a excludes 4a
Contradiction: 5a excludes 5a
Contradiction: 7a excludes 7a
Contradiction: 7e excludes 7e
Contradiction: 8a excludes 8a
Contradiction: 9a excludes 9a
Computing the transitive closure takes 94 mS on my 3GHz AMD64 in VB6.
I agree that identities may be unneccesary but I'll continue to compare the algorithms on some more examples.
Supercoloring just became even simpler.
There may still be some mileage in finding the simplest exclude...conjugate chain - I still have hopes that the process might be possible manually on real paper with real colouring pencils.
Regards
Andrew |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Thu Aug 11, 2005 1:23 am Post subject: |
|
|
Nick70 wrote: | AMcK wrote: | ... can you do identities? |
Of course.
If excludes(x,y') and excludes(x',y) then x=y.
But I'm not using it since it isn't needed by the algorithm, and recoloring appears to be just a waste of time with the data structures I'm using. |
I have a puzzle that seems to require supercolour identities. The identities based on implications solve it but those based on exclusions don't. I'm checking everything carefully and will report if I can find the evidence - or fix the bug otherwise.
Andrew |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Mon Oct 03, 2005 5:17 am Post subject: |
|
|
After learning of Nick's delightful approach of using only exclusions, I think I've found the source of Andrew's discrepancy between that method and implications. It begins with an insight I encountered when posting here, and how forcing chains (of the sort found by Trebor's Sudoku Susser at least) could be viewed as an advanced coloring problem.
It basically boils down to this: If excludes(x,y), then either x' or y' or both must be true. Any cell/digit placement intersecting x' and y' can be eliminated. An example using simple coloring explains that more graphically.
When this method is applied to simple coloring, of course alongside Nick's transitivity rule that excludes(x,y) + excludes(y',z) -> excludes(x,z), it proves part of Doug's speculation that simple coloring and fishy cycles are equivalent. In actual fact, simple coloring with this rule is a superset of fishy cycles, since coloring will find contradictions that fishy cycles won't.
Has anyone else discovered this rule? It seems quite special in the fact that it does not require an either-or, but allows for at least one of a set of conditions to be true.
[edit]
Good grief, I finally got it. What I've been doing is identical to what Nick posted above. If excludes(x,y) and excludes(x,z) and excludes(y',z'), then excludes(x,x). The only reason I didn't see this before was that I wasn't considering these other positions as colors. (Strictly speaking, you don't have to, but I imagine Nick's method of assinging dummy non-conjugated colors is a great deal faster.) I think this has remained obscure up to now because of that. If you don't assign those extra dummy colors, you can still get the same results by intersecting the conjugates of two mutually exclusive colors. |
|
Back to top |
|
|
|
|
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
|