The New Sudoku Players' Forum

[benjam]

I was playing around with the Simple Sudoku program and was just F11 jumping through a puzzle to see how the program runs it and found a spot in the puzzle where it removed about 8 of the 6's from the candidates by way of coloring.

When I saw this, I looked and looked, but I could not figure out how the program came to the conclusion that it did.

Could somebody please explain how the program ended up removing so many of the candidates in one move?

Here is the puzzle one move before the coloring move:

Code: Select all

 *-----------*
 |9.5|.87|431|
 |314|.95|87.|
 |.7.|143|.59|
 |---+---+---|
 |791|826|543|
 |.53|471|92.|
 |4.2|539|1.7|
 |---+---+---|
 |5..|314|79.|
 |.49|76.|315|
 |137|95.|..4|
 *-----------*


After this puzzle is opened in Simple Sudoku, press F11 once to remove a candidate by a different means, then press F11 again and around 7 or 8 of the 6's will be removed by coloring.

Thanks for any clarification.

[r.e.s.]

I was playing around with the Simple Sudoku program and was just F11 jumping through a puzzle to see how the program runs it and found a spot in the puzzle where it removed about 8 of the 6's from the candidates by way of coloring.

When I saw this, I looked and looked, but I could not figure out how the program came to the conclusion that it did.

Could somebody please explain how the program ended up removing so many of the candidates in one move?
[...]Thanks for any clarification.

The section on coloring at http://www.angusj.com/sudoku/hints.php should answer your questions.

[angusj]

Could somebody please explain how the program ended up removing so many of the candidates in one move?

The basic principles of colors is described here - http://angusj.com/sudoku/hints.php#colors

In this case:
1. filter on 6s.
2. apply conjugate colorings as per image above.
3. you'll notice two cells of the same color in box 1.

Since there can't be two 6s in a box (or a row or a column) this must be the false color. Therefore 6 can be excluded from all blue cells and all green cells can be assigned 6 too.

[r.e.s.]

angus,
I'm curious how you manage to get your images down to only 17KB or so. I notice others posting similar images >50KB (a recent thread had four images like this, totalling >260KB). Any tips?

[angusj]

angus,
I'm curious how you manage to get your images down to only 17KB or so.

1. From Simple Sudoku I Edit | Copy Image to the clipboard.
2. Paste the image into Paint Shop Pro.
3. Decrease colour resolution to 256 colors (8 bit) using optimised palette.
4. Save image as gif.

(Step 3 may seem unnecessary as all gifs must be 8 bit or less. However, this extra step definitely helps with both file size and preserving exact colors when I decrease colors using an optimised palette rather than the (presumed default) 'web-safe' palette.)

Edit: Simple Sudoku now creates image files directly (in *.png file format).

[r.e.s.]

Angus,
Thanks for the tip. Also, since quite a number of such images are appearing on this bb, maybe it's worth mentioning something I just now stumbled upon (for anyone using Excel) ... One can paste the image into a worksheet and Save As a Web Page, with Tools/Compress Pictures set to Web/Screen, and the image is saved as a .png file of as little as 5KB (!) or so, and of good quality for posting. In fact, that process converted a screenshot of your picture above to a 5KB .png, and I can't tell any difference in on-screen quality. (I'm sure there is a more-direct way if one has the proper software.)

[udosuk]

The .png format does save a lot more space than .jpg. The only down side is that those images are not subjectable to resizing... So if you plan to view the images in full size all the time than .png is definitely the best format to use... BTW you don't need Excel to convert it to that format. Paint would simply do it!

[r.e.s.]

BTW you don't need Excel to convert it to that format. Paint would simply do it!

Excel's compression option can make a huge difference. For example, I just did an Edit/Copy-as-Image in Sudoku Solver, then pasted into Paint and saved as a 21KB .png -- but Excel with compression saves it as a 7KB .png (compressed by a factor of three, with *no* apparent degradation that I can see!) For comparison, I've put these two pictures, plus the 20KB .gif I got using the colors-reduction method angusj described, at
http://r.s.home.mindspring.com/Misc/test-excel.png
http://r.s.home.mindspring.com/Misc/test-paint.PNG
http://r.s.home.mindspring.com/Misc/test-PSP.gif
(Also, I notice the .png's do resize automatically with the browser window.)

[angusj]

Excel's compression option can make a huge difference.

It's not Excel, it's the png file format itself which uses a more efficient compression algorithm than that used in gif files.

Edit: The following url compares gif and png files (you'll need to scroll down to about half way):
http://www.libpng.org/pub/png/book/chapter09.html

[r.e.s.]

Excel's compression option can make a huge difference.

It's not Excel, it's the png file format itself which uses a much more efficient compression algorithm than that used in gif files.

Then Excel seems to be using a more efficient form of png than does Paint. How else to explain the dramatic difference in size between the png produced by simply saving it from Paint (21KB), and the *more*-compressed png generated by Excel (7KB)? They both start with the exact same image from the clipboard.

[angusj]

Then Excel seems to be using a more efficient form of png than does Paint.

I'm sure you're right there. However, I guess that's no surprise since Paint is a very primitive utility.

[benjam]

interesting information about the images...

now back to topic (sorry)

ok I think I got it now. I was having some issues figuring out why the 7th box (bottom leftmost) was not being colored but then I realized that blocks with ONLY two candidates can be colored, and because there is three candidates in column 2, the coloring never makes it into the 7th box. I was getting a little confused on this point but this extreme case and the explanation of it has helped me out a lot.

Thanks for the help, and great program.

[angusj]

Back off topic ...
The next version of SS (not yet released as I'm waiting on translators) supports copying images directly to *.png files.

[benjam]

... continuing off topic ...

SS ? (Super Sudoku)

edit: nm, i'm a little slow

[Lummox JR]

To get a full understanding of coloring, benjam, it's important to know that there are several ways it can eliminate candidates. Also, it's not so much that you can't color a cell if there are more than 2 candidates in the box; the rule is only that it must have a conjugate. In this case you were able to follow a chain of conjugates right along, but coloring won't always work that way.

The method you saw here showed that you can start off with one square and follow conjugates until one color eliminates itself. In this case you ended up with two blue cells in the same box.

You can also find cells where two conjugate colors intersect. If that cell "touches" both blue and green, it must be false.

However far more commonly you'll find multiple colors, which can still be useful. To represent colors I usually go with letters, such as aA for the first pair of conjugates, bB for the second pair, etc. With multiple colors you may be able to connect them, if for example you find that a and b are in the same house, and A and B are in the same house, in which case a=B and b=A. You may also find that a particular color is impossible because it connects to two conjugates, such as if a and b connect, and A and b connect; there b must be false.

When working with multiple colors I now know the best method is not to try to prove several colors are equivalent, but rather to prove that one excludes another. Nick70 did some good work in this regard, proving you can say that if a excludes b, and B (b's conjugate) excludes c, a excludes c. If you know that two colors exclude each other, at least one if not both of their conjugates must be true. Therefore you can eliminate any cells that intersect those colors. (E.g., if a excludes b, then any intersection of A and B is false.) I don't think most people take coloring that far, but it's very worth it because it will show eliminations that otherwise will not appear.