Colouring Troubleshooting

gaby · Posted: Sun Oct 16, 2005 1:32 am Post subject: Colouring Troubleshooting

Grrrrrr

Right, here are two images:

http://vanhegan.net/pictures/state1.png
http://vanhegan.net/pictures/state1.cols.png

The first is the current state of the puzzle that I have, and the second is how my colouring engine decides to colour the threes. Now, I think that the three colouring combination causes a contradiction in col 6, therefore the 'b' coloured cells can't be right, so the 'a' coloured cells have to be right. So I set the a cells to 3, and a few steps later the puzzle is broken. The puzzle is soluable, and has one solution as I've solved it before. It's just that my colouring is broken.

How would you colour this puzzle? Where have I gone wrong? What rule have I missed out of my colouring algorithgm? Where is this colouring pattern broken?

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Lummox JR · Posted: Sun Oct 16, 2005 2:22 am Post subject:

Well, there are two problems. The first is, there's no apparent contradiction in column 6. The light red, yellow, and light green cells can all exist there just fine.

The second problem is, you only found some conjugates, but not all. There is another conjugate in column 8, box 6, between cell (8,4) which is 2b and cell (8,5) which should be 2a.

This leaves you with these exclusions: 4b!2a, 4a!3b, 1b!2a, 1b!3b, g!2a

Unfortunately none of those exclusions lead you anywhere. Transitivity will tell you nothing new, and there are no intersections to be found:

4b and 2a cannot both be true, so at least 4a or 2b must be true. There is no intersection between these colors.
4a and 3b cannot both be true, so at least 4b or 3a must be true. There is no intersection between these colors.
1b and 2a cannot both be true, so at least 1a or 2b must be true. There is no intersection between these colors.
1b and 3b cannot both be true, so at least 1a or 3a must be true. There is no intersection between these colors.
Light green and 2a cannot both be true, so at least green or 2b must be true. There is no intersection between these colors.

There are also no intersections between conjugate colors, since no color pair is spread out far enough to allow the possibility. So there's no coloring you can do on the 3's.

gaby · Posted: Sun Oct 16, 2005 2:18 pm Post subject:

The colouring scheme is either the light colours must be true or the dark colours must be true, so the contradiction in column 6 for the light colours means that the light colours can't be true.

Also, I suspect that it found that other conjugate, but it hasn't included it in the colouring map for reasons known only to itself. I think that it's because one part of the conjugate is already used in the yellow set, so I need to make it add that to the yellow set, as it's half yellow already. I think my criteria for including colours is a bit too restrictive. I'll post updated pictures when I've had a chance to work on this today. For the moment, I've got some gardening to do!
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

gaby · Posted: Sun Oct 16, 2005 8:28 pm Post subject:

So I made it detect the other conjugate, and label it accordingly, but it still suggests that there is a contradiction in the middle row. If the three conjugates share a common column, then surely only one of them can be true?

http://vanhegan.net/pictures/state2.png

Looking at col 6, the red cells do directly influence the green and yellow colours? Should I only check for contradictions in one state, or both? I can see that if I only check for a state contradictions rather than b state, it'll work. But I can't rely on that. What am I missing here?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

gaby · Posted: Sun Oct 16, 2005 8:48 pm Post subject:

Well, I seem to have made some progress. If I only let it look for contradictions in the a state (all the darker colours numbers) then it seems to work, not generating any false recommendations, and not breaking any puzzles. Also, it looks like it's solving most of those stress testing colouring puzzles that were kindly posted here, bit it's using tabling to do the majority of them, not actually making any progress with colouring.

What on earth is going on here? If I disbable checking for contradictions on the lighter coloured numbers, it works. Surely that shouldn't be the case, as the contradiction in the lighter numbers means that the darkers number should be true?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Lummox JR · Posted: Sun Oct 16, 2005 9:43 pm Post subject:

Ruud · Site Admin

Don't give up, Gaby!

I had a few errors in my code, and the nature of this complicated stuff sometimes causes weird results. I temporarily rewrote the code to take it one step at the time and show some debugging output after each step. Then I could identify the errors (bad linking of colors, eliminating for the dark in stead of the light colors, etc)

There are still more unrevealed possibilities with colouring.

I've been testing my colouring against some of the puzzles in the multicolor pack posted by Angus, and everything seems to work perfectly now, but still the single-digit-template-checker catches situations faster than colouring.

Here's an example (multi009 from Angus' second pack)
At this point not all clues are placed yet, but the template checker already made a fast elimination.

gaby · Posted: Sun Oct 16, 2005 10:53 pm Post subject:

Lummox, the way I have the colouring setup is that the chain of conjugates are coloured appropriately, so either all the light cases should be true (in a forcing chains-style way), or all the dark cases should be true. However, you can only follow the chains that are within the same colour to draw any conclusions. This makes more sense, so I should instruct the solver to test for contradictions one colour at a time, rather than by all the light and dark shades.

As an aside, my solver, using colouring, now ranks this puzzle 2.5.3.2 (the highest numeric value I've seen in my collection, but not the hardest puzzle):

gaby · Posted: Sun Oct 16, 2005 10:56 pm Post subject:

Oh, and it produces a really pretty colour map for the 9's at one point:

http://vanhegan.net/pictures/state3.png

Quite pleasing to the eye, that one Smile

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Ruud · Site Admin

Nice, but not quite there yet.

You do not seem to linkup the conjugate pairs in boxes. Only in rows and columns.

gaby · Posted: Sun Oct 16, 2005 11:14 pm Post subject:

How odd, I though they did. I've seen it in other numbers, just not in the 9's on that particular puzzle. Is there not an example of this in block 6? Light yellow in r4,c7 causes causes dark green (not very dark) in r6,c8? I could provide some sample output from my code, but I think it does. Which one has it missed?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Ruud · Site Admin

Your colouring still looks a bit like this

Your code is missing the conjugate pairs in boxes. e.g. box 3 has a conjugate pair, but it was not colored.

Lummox JR · Posted: Sun Oct 16, 2005 11:46 pm Post subject:

Ruud · Site Admin

gaby · Posted: Mon Oct 17, 2005 9:48 pm Post subject:

OK, I think I licked the problem with that set, in that it was assigning colours to the wrong end. When it was extending a colour with a 2a, it was assigning the conjugate to 2a, when it should have been a 1a...

Alas, I think I have fixed the problem. Now running through the stress test, I found 5 puzzles that don't get solved, and instead come out broken. Disabling colouring cures the problem, so I can only assume it's a problem in there:

This puzzle: