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   

Simple colouring, simple question

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Wed Aug 17, 2005 6:55 pm    Post subject: Simple colouring, simple question Reply with quote

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

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/
Back to top
View user's profile Send private message Visit poster's website
AMcK

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

Items
PostPosted: Sat Aug 27, 2005 8:44 am    Post subject: Re: Simple colouring, simple question Reply with quote

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

 
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