|
View previous topic :: View next topic |
Author |
Message |
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Wed Aug 17, 2005 6:55 pm Post subject: Simple colouring, simple question |
|
|
I want to try and implement colouring (at least simple colouring) but I can't wrap my head around a fairly simple facet of the algorithm: Assigning the initial colours to the conjugate pairs.
As I see it I need to search each row/col/block (house) for all instances where there are only two cells that hold a given number N. These are my conjugate pairs.
Now I need to label each of the cells with a given colour. How do I assign the colours? What algorithm do I use to assign them? I was under the impression that you assign colours from 1 to x for each cell in the conjugate pair, but if that colour is already in use in that row/col/block, it get's the next colour in the list?
Help? Whilst I'm thinking about this, I'll work on forcing chains...
Gaby _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sat Aug 27, 2005 8:44 am Post subject: Re: Simple colouring, simple question |
|
|
gaby wrote: | I want to try and implement colouring (at least simple colouring) but I can't wrap my head around a fairly simple facet of the algorithm: Assigning the initial colours to the conjugate pairs.
As I see it I need to search each row/col/block (house) for all instances where there are only two cells that hold a given number N. These are my conjugate pairs.
Now I need to label each of the cells with a given colour. How do I assign the colours? What algorithm do I use to assign them? I was under the impression that you assign colours from 1 to x for each cell in the conjugate pair, but if that colour is already in use in that row/col/block, it get's the next colour in the list?
Gaby |
There have been at least three published algorithms to do assign simple colours:
1) My original algorithm simply looked for houses (rows/columns/boxes) containing exactly two instances of a given possible and assigned colour pairs.
a) If neither cell was coloured it assigns a new colour pair
b) If just one was already coloured then it assigns its conjugate colour to the other
c) If they were both already coloured as conjugates then it would leave them alone.
d) If they were both already coloured with non-conjugate colours p,q then it would "merge" the two conjugate pairs by equating p=q' and p'=q
2) Nick70's improvement looked recursively along conected houses every time a cell is coloured so as to anticipate and avoid the case (d) merge above.
3) My current algorithm simply starts by colouring every possible in every cell sequentially in idiot fashion. It then adds an entry in the matrix conjugate[u,v] every time a conjugate pair is discovered. The real work is then done by a "transitive closure" operation by iteratively scanning the matrix using the equation ...
if conjugate[u,v] and conjugate[v,w] then u=w
It then recolours all instances of the w with the u and discards w.
This algorithm is very easy to program
Simple colouring performs this algorithm independently for each possible in turn. Supercolouring performs this for all possibles simultaneously and adds another type of "conjugate". Where there are only two possibles in a cell then either one or the other must be true and therefore the colours of the two different possibles may be added into the conjugate[u,v] table. The transitive closure often reveals colour identities across different possibles.
Hope that helps
Regards
Andrew |
|
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
|