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   

Colouring stress testing

 
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: Sun Oct 16, 2005 1:07 am    Post subject: Colouring stress testing Reply with quote

Hi,

Further to my colouring implementation, I'd like to stress test it. If you have any puzzles that require colouring to solve, please could you post them here. I think others may find them useful as well...

Many thanks,

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
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Sun Oct 16, 2005 2:06 am    Post subject: Reply with quote

Well, there's this fun one my generator spit out, although after coloring it requires supercoloring. What's fun about it is that after supercoloring the puzzle proceeds with some other interesting tests, including remote pairs. You don't see that too often.
Code:
7 . .|. . 9|4 . .
. 5 .|. . 1|3 . .
. . .|4 5 .|. . 1
-----------------
. . 6|. . .|8 . .
5 . 4|. . .|. . .
. 9 .|. . 2|. . .
-----------------
6 . .|1 9 .|. 8 .
. . .|6 . .|9 4 5
. . .|. . 4|. . 2

If your solver uses standard techniques and then tries complete simple coloring, it will be able to find two eliminations for the digit 2. Then it will get stuck unless you've implemented something more powerful.

There's also this nice one where you can do coloring several times before getting to more advanced techniques:
Code:
. . .|. . .|. 5 .
. . 2|. 9 5|. . .
. . 4|1 . .|8 . .
-----------------
. . .|6 7 2|. . 8
6 . 1|9 . .|. . .
2 . .|. . 1|. 9 4
-----------------
. . .|. 3 .|2 . .
7 . 8|. . .|. . 9
. . 6|. . .|3 4 .

And I absolutely adore this next puzzle, where coloring is most successful only if you apply the uniqueness test 2B first. It's rare to find a puzzle where the uniqueness B test can make a difference, but it does here because it happens to eliminate a crucial placement for the digit you'll be coloring in. If you don't use uniqueness B here, you can still find one more elimination by coloring in another digit, but that's not enough to help you.
Code:
. . .|. . .|. 6 7
. . .|3 1 .|. . .
. . .|. . 2|. . 1
-----------------
4 . .|. . 8|. . .
. 3 8|. . 7|2 . .
. . .|. 5 .|3 . 9
-----------------
. . 7|8 . .|. 4 .
3 . .|. 7 .|. . .
8 . .|. . 6|. 9 .

This one has some coloring which will eliminate two candidates, and an XY-wing:
Code:
. . .|5 . .|4 . .
2 1 .|. . .|. 5 7
7 . .|. 3 .|6 . .
-----------------
3 . .|. . .|. . .
. . .|9 7 .|8 3 .
4 . 9|. 2 8|. . .
-----------------
. . 4|. . .|. . .
. 6 .|1 . .|. . .
. 9 .|. 4 .|. 2 5

Here's some pretty basic coloring with just one conjugate set:
Code:
. 7 .|. 8 .|. . .
3 . .|2 . .|. . 5
. . .|. . 5|8 3 7
-----------------
. 1 .|. . .|9 . .
8 . .|. . .|6 . 4
4 . .|7 9 .|3 . .
-----------------
. . .|4 . 7|. . .
. 3 2|5 1 .|. . .
. 5 .|. . 2|. . .

Another cool one relies on the uniqueness test (form 1) to make a crucial elimination before coloring can help you much. You can also do an XYZ-wing but it's unnecessary. After coloring an XY-wing unlocks the puzzle.
Code:
2 . .|. . 7|. 5 .
. . .|5 . .|. 3 .
3 . .|. 6 .|. . 9
-----------------
5 6 3|. . .|. . 2
. . .|. 7 .|5 4 .
. 1 .|. . .|. . .
-----------------
. 9 .|. . .|. . .
6 . 2|4 1 .|. . .
1 4 .|3 . .|. 2 .

This one uses just one pair of conjugates, but one of them eliminates itself:
Code:
. . .|. 5 3|. . 4
. 6 .|. . .|. 5 .
. . .|7 . .|. . .
-----------------
9 7 .|. 6 2|. 8 3
. . .|5 . .|9 . .
2 . .|. 3 7|. . .
-----------------
1 2 6|4 . .|. . .
. . 7|. . .|. . 8
. 3 .|. 9 .|. 7 .

Here one color appears alongside two others that are conjugates, so it can be eliminated:
Code:
6 . 1|. . 4|. . .
. . .|. . .|. 5 .
. . .|1 . .|3 . .
-----------------
. 8 .|. . 7|6 2 .
4 . .|. . 5|. . .
. . .|. 3 .|. . 8
-----------------
. 7 .|. 2 .|1 . .
9 . 5|. . 8|7 . .
. 4 8|. . .|. 3 .

Here's another nice one:
Code:
1 . .|. . .|. . .
. 7 .|. 3 .|. 1 4
5 . 4|. 7 .|6 2 .
-----------------
6 . .|. . .|. . .
. . 7|8 . .|5 6 1
. . .|. . .|. . 7
-----------------
. . 6|. . 2|. . .
3 . .|. 6 5|. . .
. 1 .|4 . 8|7 . .

This next one uses some transitivity. The rule is if x!y and Y!z, then x!z. (x!y means x excludes y; they both appear in a common house, so they can't both be true.) You'll find a set of colors that behaves that way for the digit 9.
Code:
. 2 .|. . .|. . .
9 . 1|. . .|. . .
. 3 .|. 2 .|. 4 8
-----------------
. . .|. . 8|. . 7
4 . 6|9 . .|. . .
. 9 .|. 1 .|. . .
-----------------
5 . 2|. . .|4 . 6
. . .|7 . 4|. 2 .
. . .|2 5 .|. 1 3

I found a few others of minor interest, but this should pretty well run the gamut of complete simple coloring.
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sun Oct 16, 2005 3:10 am    Post subject: Re: Colouring stress testing Reply with quote

gaby wrote:
If you have any puzzles that require colouring to solve, please could you post them here.


http://angusj.com/sudoku/multicolor_puzzles_1.zip
http://angusj.com/sudoku/multicolor_puzzles_2.zip

nb: the second collection is considerably tougher than the first.
Back to top
View user's profile Send private message Visit poster's website
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