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   

Confused over Colouring
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Jul 01, 2005 8:04 am    Post subject: Confused over Colouring Reply with quote

Andrew,

I've been studying your posts on your colouring algorithm, and there's a step I just can't get my head around. It's where you decide that two different colour pairs are mutually exclusive.

Could you please explain to a dummy what logic you use to determine this exclusivity?

Thanks,
Simon
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Fri Jul 01, 2005 10:40 am    Post subject: Reply with quote

I gave a detailed version of the algorithm here:

http://www.setbb.com/phpbb/viewtopic.php?p=206&mforum=sudoku#206

The algorithm is equivalent to Fishy Cycles, but, I believe runs faster, and is easier to program.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Jul 01, 2005 11:54 am    Post subject: Reply with quote

Hi Doug,

Yep, I've seen and studied that post too, but I think there must be something more.

Looking at this post, http://www.setbb.com/phpbb/viewtopic.php?p=25&highlight=&mforum=sudoku#25

If I'm following your algorithm correctly (that's a big if!) I get a colour map of:
Code:
...|...|.ab
...|cd.|...
...|...|...
---+---+---
...|.e.|f..
.g.|...|.b.
...|d..|...
---+---+---
..g|...|h..
.h.|...|..a
...|...|...


But after applying AMcK's "mutual exclusion", he deduces that a and g, and b and h are the same, so this equates to
Code:
...|...|.ab
...|cd.|...
...|...|...
---+---+---
...|.e.|f..
.a.|...|.b.
...|d..|...
---+---+---
..a|...|b..
.b.|...|..a
...|...|...


It's the logic behind this mutual exclusion I can't understand.
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Fri Jul 01, 2005 12:09 pm    Post subject: Reply with quote

From block 9 (of your first diagram): a and h are the only cells in block 9 containing the possibility under consideration. Thus h must have the same truth value as b. Thus a=g and b=h. I think that does it. (It's a block conjugacy, assuming your diagram represents the only cells marked by the possibility under consideratin.)

Edit: This recoloring would occur during the block stage of the coloring.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Jul 01, 2005 12:19 pm    Post subject: Reply with quote

The colouring digit is 4, and the candidate matrix is
Code:
8 12 9 6 3 12 7 45 45
37 1267 1236 45 45 129 8 36 29
4 5 36 279 789 2789 36 1 29
56 28 28 1 469 69 456 7 3
37 467 346 8 2 5 9 46 1
1 9 456 347 467 367 456 2 8
25 3 14 257 578 278 14 9 6
259 14 7 2359 569 2369 134 8 45
569 68 568 359 1 4 2 35 7


In block 9, r7c7, r8c7 and r8c9 all have 4 as candidates - doesn't this break the exclusion between a and h?
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Fri Jul 01, 2005 12:34 pm    Post subject: Reply with quote

Sure does! And row 5 (with b and g) doesn't help either; there's a third 4 in that row. Now I'm puzzled too. I didn't look at this example when I tried to work out how his algorithm worked. (I looked at a couple of others though.) Wish he had actually posted the algorithm instead of just some output.

Anyway, what I posted still gives an algorithm equivalent to the fishy cycles algorithm. I don't know what he was doing here.

Edit: Maybe after I sleep I'll work through the coloring algorithm with your permissions matrix and see what I get. Need some sleep now, though.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Jul 01, 2005 12:59 pm    Post subject: Reply with quote

I looked at all his examples I can find, and still can't figure out this step. Perhaps I'm missing something obvious, or perhaps it's not obvious at all.
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Fri Jul 01, 2005 1:39 pm    Post subject: Reply with quote

Ok. Here is the logic.

In block 9. a=T -> h=F -> g=T=a.

Otherwise, in block 9, a=F -> b=T (in row 5) -> g=F (in row 5). So again a=g and b=h.

Hope that helps. Also, checked this with puzzle MadOverlord's susser, and it solves it using Fishy Cycles at exactly this point using 4s.

Ok, really gonna sleeep now.

Cheers!

Edit: I'll try to translate this logic into the coloring algorithm tomorrow.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage


Last edited by Doug on Fri Jul 01, 2005 2:13 pm; edited 2 times in total
Back to top
View user's profile Send private message Send e-mail
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Fri Jul 01, 2005 1:42 pm    Post subject: Reply with quote

Simes wrote:
I looked at all his examples I can find, and still can't figure out this step.

His coloring of the 4s makes sense but this ...
Quote:
Hence eliminations in rows 5,8 for conjugate colours a/b
Row 5 reduction: digit 4 colours a/b cell {5,3} before 346 after 36
Row 8 reduction: digit 4 colours b/a cell {8,7} before 134 after 13

doesn't make sense to me. I have no idea what he means here.
Anyhow, I don't believe you can safely eliminate candidates based on coloring 4s in this example. {Edit: figured it out - I'd excluded these two candidates by other means before I had started coloring. Anhow, having an A & B (true & false) in the same row - where one must be the 'big number' implicitly excludes other candidate 4s in the same row.}

The logic as I see it is this: given a specific candidate (4s in the above example) and you have only two possible locations for this candidate in any one group (row, column, or box) then one must be the 'big number' and the other must not. Because we don't know which is which, we give each of these 'conjugate' candidates a label (A or B, blue or green etc) to represent their conjugate (or opposite true/false) states. Some conjugate candidates chain together - ie wherever cells have conjugate relationships with more than one other cell. This is what Andrew is describing in the post you've pointed to. Sometimes, by following the true/false logic around these chains, it becomes evident that candidates can be safely excluded. In the case above, having a true and false (A & B) in the same row implicitly excludes other candidates in the same row. Also, occasionally two cell in a chain will have the same label (or color) and also share a group. When this happens these two cells must represent 'false' candidates (you can have two or more falses in a group but not two 'trues'), so another candidate must be the 'true' (assuming it is a valid puzzle).

That's a bit long winded so perhaps my admittedly suboptimal explantion here might be marginally clearer.
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 Jul 02, 2005 1:14 am    Post subject: The additional recolouring rule: mutual exclusions Reply with quote

The descriptions given of the colouring algorithm by everyone are amazing and I thank them. There is however one rule missing form the explanation.

Yes, there is an additional recolouring rule that Simes has deduced correctly. I found empirically quite late on that I needed to add this rule to find all the potential reductions in the most difficult puzzles.

Consider the problem that Simes refers to from my original post http://www.setbb.com/phpbb/viewtopic.php?p=25&highlight=&mforum=sudoku#25

Try to consider what the colour map below is telling us:

...|...|.ab
...|cd.|...
...|...|...
---+---+---
...|.e.|f..
.g.|...|.b.
...|d..|...
---+---+---
..g|...|h..
.h.|...|..a
...|...|...

In row 1, a/b are conjugate colours for 4 which means that either a=4 or b=4
But in row 5, g and b are what I term exclusive - which means that either g=4 or b=4 or a third possibilty - (h=4 and a=4 and both g and b are different from 4)
That's what the line "Non-conjugates: row 5 colours g b" means
This alone is not sufficient to deduce that the colour pairs a/b and g/h are identical

But if we look at row 8 we find also that the conjugate colours a and h are exclusive so that either h=4 or a=4 or (g=4 and b=4)

If we put these two together then the (h=4 and a=4) and (g=4 and b=4) possibilities are impossible and so we are left with the only two possibilities
(g=4 or b=4) and (h=4 or a=4)

But we already know that either h=4 or g=4 and also that a=4 or b=4.
So that a=h and b=g must be true and the recolouring is authorised.

So the additional late rule is:
If two non-conjugate colours b, g sit in the same row/column/box and their conjugates a, h sit in some other row/column/box then it is valid to equate the colour pairs a/b and g,h

Hope this fills the missing link for everyone.
AMcK
Back to top
View user's profile Send private message Send e-mail
AMcK

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

Items
PostPosted: Sun Jul 03, 2005 1:17 am    Post subject: Reply with quote

If anyone wants the 500 lines of (VB6) code for colouring just drop me an email to andrew@mckernan.info.
I just discovered uselessly that the colouring algorithm also implements some of Rule 1: "Scan each row/column/box, and if a certain possible only exists in coincidence with another row/column/box, remove it from the other cells in that other row/column/box." It colours pairs of cells in a box and then reduces matching candidates in intersecting rows/columns.
I actually prefer the directed graph formulation and suspect it's easier for humans to use. But colouring is fast and exhaustive for a computer.
It's such a pity that the few puzzles it's applicable to are mostly insoluble by logic - even after colouring reductions.
Surely there must be some more logical rules just waiting to be discovered!
AMcK
Back to top
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Sun Jul 03, 2005 12:09 pm    Post subject: Reply with quote

AMcK wrote:
But colouring is fast and exhaustive for a computer.
It's such a pity that the few puzzles it's applicable to are mostly insoluble by logic - even after colouring reductions.


I've generated about 700 problems that can be solved with simple coloring, and about 2000 that can be solved with advanced coloring.

I haven't implemented triples and above yet, so some of them might be solvable that way. I haven't implemented swordfish either, since it's just a very special case of coloring (naked/hidden pairs and x-wing would be as well, but they are easier to see).

There are actually three techniques that can be used after coloring:
1) immediate contradiction. Two options in the same unit have the same color. Since they cannot be both true at the same time, they must be both false.
2) double exclusion. An option of color A escludes an option of color C, while an option of color A excludes an option of color D. Since C or D must be true, A must be false.
3) excluding pair. An unit contains both an option of color A and an option of color B. Since one of them must be true, all other options in the unit can be removed.

1) and 2) immediately allow to place one or more numbers on the grid. 3) only removes candidates.

The following are four of the ones requiring simple coloring, and techniques 1) or 2). You might have some fun with them.

Code:

..4.8.9.5    ..4.9.8.6    ..5.3.6.4    ..5.7.9.6
.316.....    .316.....    .316.....    .316.....
2........    2........    2........    2........
.....5...    .....5...    .....5...    .....5...
..9.1.8..    ..6.1.9..    ..6.1.3..    ..9.1.3..
...4.....    ...4.....    ...4.....    ...4.....
........7    ........7    ........7    ........7
.....742.    .....742.    .....792.    .....742.
8.6.9.3..    8.9.6.3..    8.3.6.1..    8.3.5.6..
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sun Jul 03, 2005 1:03 pm    Post subject: Reply with quote

Nick70 wrote:
I've generated about 700 problems that can be solved with simple coloring, and about 2000 that can be solved with advanced coloring.

It'd be really terrific if you wanted to make them publicly available (the simple coloring ones at least).

Nick70 wrote:

The following are four of the ones requiring simple coloring, and techniques 1) or 2). You might have some fun with them.

I could solve all but the first one with simple coloring, are you sure it doesn't require what you call advanced coloring?? I particularly liked the third one. Thanks for sharing them.

Edit:
I could do the first puzzle using 2 color pairs (4 colors), the other three only required one color pair. Of the 3 techniques you list above, the first & third require using only one color pair (or A & B), while the second technique requires 2 color pairs (or A & B, C & D).
Back to top
View user's profile Send private message Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Sun Jul 03, 2005 2:19 pm    Post subject: Reply with quote

angusj wrote:
Nick70 wrote:
I've generated about 700 problems that can be solved with simple coloring, and about 2000 that can be solved with advanced coloring.

It'd be really terrific if you wanted to make them publicly available (the simple coloring ones at least).


Eventually I will, but for now I'm still continuing the search (as you have seen I'm looking for all problems on a specific hints pattern - the problem is that until now I have explored only about 1/40000th of the space Sad )

I need to improve my solving program, I want to implement some more techniques and then work on a good rating algorithm, capable of evaluating not only the difficulty but also the "entertainment value" of a problem (you'll hear more from me on these issues). Then I'll publish the best problems.

In the meantime I can give you two "advanced coloring" problems to sink your teeth in. The first one is easier.

Code:

..1.8.3.9
.356.....
9........
.....5...
..8.1.6..
...4.....
........7
.....752.
8.4.6.1..


..1.4.8.6
.356.....
9........
.....5...
..9.1.6..
...4.....
........3
.....712.
8.6.9.7..


angusj wrote:
I could do the first puzzle using 2 color pairs (4 colors), the other three only required one color pair. Of the 3 techniques you list above, the first & third require using only one color pair (or A & B), while the second technique requires 2 color pairs (or A & B, C & D).


That's correct. 1) is the easiest to apply, because you need only one color pair and it immediately allows you to put in one or more numbers.
2) requires two color pairs, and it's not easy to see, but I like it more than 3) because it also allows you to insert numbers straight away. Though you are right that 3) is probably easier to apply than 2).
Back to top
View user's profile Send private message
coconut

Joined: 13 May 2005
Posts: 12
:
Location: Oxford

Items
PostPosted: Mon Jul 04, 2005 7:20 am    Post subject: Reply with quote

The 4 simple colouring problems can be solved using standard techniques (x-wings, swordfish,, nishio etc). My program (which does not have the standard tricks in the most general form) cannot solve the 2 advanced problems without trial and error. In particular, the second advanced problem is one of the most difficult I have seen.

Is it correct to say that (a) simple colouring is equivalent to standard techniques (b) advanced colouring can solve problems which cannot be solved using standard techniques?

coconut
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 1, 2, 3  Next
Page 1 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