View previous topic :: View next topic |
Author |
Message |
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Fri Jul 01, 2005 8:04 am Post subject: Confused over Colouring |
|
|
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 |
|
|
| Doug
| Joined: 28 May 2005 | Posts: 42 | : | | Items |
|
|
Back to top |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Fri Jul 01, 2005 11:54 am Post subject: |
|
|
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 |
|
|
| Doug
| Joined: 28 May 2005 | Posts: 42 | : | | Items |
|
Posted: Fri Jul 01, 2005 12:09 pm Post subject: |
|
|
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 |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Fri Jul 01, 2005 12:19 pm Post subject: |
|
|
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 |
|
|
| Doug
| Joined: 28 May 2005 | Posts: 42 | : | | Items |
|
Posted: Fri Jul 01, 2005 12:34 pm Post subject: |
|
|
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 |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Fri Jul 01, 2005 12:59 pm Post subject: |
|
|
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 |
|
|
| Doug
| Joined: 28 May 2005 | Posts: 42 | : | | Items |
|
Posted: Fri Jul 01, 2005 1:39 pm Post subject: |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Fri Jul 01, 2005 1:42 pm Post subject: |
|
|
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 |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sat Jul 02, 2005 1:14 am Post subject: The additional recolouring rule: mutual exclusions |
|
|
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 |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sun Jul 03, 2005 1:17 am Post subject: |
|
|
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 |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Sun Jul 03, 2005 12:09 pm Post subject: |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Sun Jul 03, 2005 1:03 pm Post subject: |
|
|
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 |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Sun Jul 03, 2005 2:19 pm Post subject: |
|
|
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 )
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 |
|
|
| coconut
| Joined: 13 May 2005 | Posts: 12 | : | Location: Oxford | Items |
|
Posted: Mon Jul 04, 2005 7:20 am Post subject: |
|
|
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 |
|
|
|