Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Nishio vs Supercolouring
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Sun Aug 07, 2005 9:41 am    Post subject: Re: Nishio vs Supercolouring Reply with quote

angusj wrote:
I guess that leaves Nick70 there on his lonesome. Very Happy

Embarassed 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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Sun Aug 07, 2005 9:19 pm    Post subject: Re: Nishio vs Supercolouring Reply with quote

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
View user's profile Send private message Send e-mail
Gennadog

Joined: 03 Jun 2005
Posts: 5
:

Items
PostPosted: Mon Aug 08, 2005 8:12 am    Post subject: Re: Nishio vs Supercolouring Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Mon Aug 08, 2005 9:10 am    Post subject: Re: Nishio vs Supercolouring Reply with quote

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 Sad .
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
View user's profile Send private message Send e-mail
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Mon Aug 08, 2005 10:41 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Tue Aug 09, 2005 5:50 am    Post subject: Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Tue Aug 09, 2005 8:19 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Tue Aug 09, 2005 10:11 am    Post subject: Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Tue Aug 09, 2005 10:46 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Thu Aug 11, 2005 1:23 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Mon Oct 03, 2005 5:17 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron