View previous topic :: View next topic |
Author |
Message |
| SarC
| Joined: 19 Oct 2005 | Posts: 14 | : | | Items |
|
Posted: Mon Dec 05, 2005 7:04 pm Post subject: Simple coloring |
|
|
I have tried to implement simple coloring into my solver. It seems to work fine but I was wondering if there was any rules that I haven't coded ('cause I don't know 'em).
So here is a run-down of what I have made so far:
1) Color the board.
2) Check if there is two of the same letter in a house, for instance two A's. If that is true I remove the candidate from all cells that occupy that letter.
3) See if there are a conjugate pair in a house, for instance a 'b' and a 'B'. If true, remove the candidate from all non-colored cells in that house.
4) Then I check all non-colored cells and see if one share a house with a conjugate pair. If true, I remove the candidate from that non-colored cell.
5) Lastly I loop through all letter-cells and see what other letters they have in common, in regard to row, column and box. For instance, 'A' can be in the same house as 'b' and 'B'. I store all these pairs in an array 'Ab', 'AB' etc. I then reverse-case the array, so 'A' becomes 'a', 'B' becomes 'b' etc. Then I loop through all letter-cells again, this time looking for a cell that shares one of the pairs, previously collected. If this is true, I remove the candidate from this cell.
I am unsure if I need 3), since I also implement locked candidates, and that rule is used before coloring. I haven't found a test case, where the rule can be applied, after testing for locked candidates.
In 5), is it possible to exclude candidates from non-colored cells? In all my test, I have only come across exclusions in letter-cells.
Any help will be appriciated |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Dec 05, 2005 9:44 pm Post subject: |
|
|
SarC wrote: | I have tried to implement simple coloring into my solver. |
Many would consider this to be "multi-coloring".
Your check 4) would subsume check 3), if I read them both correctly.
Test 5) is the most interesting one, and can be further extended:
When a pair of colors exclude each other, we write it like this: a!b
You can also combine these exclusions, like this: a!b and A!c implies b!c.
It is also possible to have a color exclude itself: a!b and a!B implies a!a.
Check the SOLVING TECHNIQUE INDEX. It contains a links to good coloring topics.
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| SarC
| Joined: 19 Oct 2005 | Posts: 14 | : | | Items |
|
Posted: Mon Dec 05, 2005 11:16 pm Post subject: |
|
|
Thanks for your reply, Ruud. The rule of combining exclusions seems very interesting so I went investigation for an example where I could apply it.
Code: |
-------------
|...|...|...|
|..A|.a.|...|
|D4.|E.4|...|
-------------
|...|.Aa|...|
|.44|...|.F.|
|d4.|...|.f.|
-------------
|..c|e.4|...|
|...|...|...|
|.C.|..c|...|
-------------
Possible exclusions:
A!c A!D a!E D!E a!c d!f c!e
So, if I got this right, A!c and a!E so c!E. After the reverse-case this becomes C!e and then combining it with the C!E (reverse) already found, I can then conclude that all "C"'s are false? I'm pretty sure this isn't correct, but I'm insecure when to apply these combinations - before or after the reverse-case?
|
SarC |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Dec 05, 2005 11:46 pm Post subject: |
|
|
Never reverse before combining the rules. When you reverse, do not use the ! symbol. This symbol means "excludes" and that is no longer true when you reversed the case.
Your example analyzed:
Quote: | Possible exclusions:
A!c A!D a!E D!E a!c d!f c!e |
Concusions that you can draw:
A!c + a!c = c!c (eliminate c)
Because c is an invalid choice, you should not use c to draw any other conclusions.
So, the new situation becomes:
Code: | -------------
|...|...|...|
|..A|.a.|...|
|a..|b.4|...|
-------------
|...|.Aa|...|
|..a|...|.A.|
|A..|...|.a.|
-------------
|...|B.b|...|
|...|...|...|
|.4.|...|...|
------------- |
This situation only has a!b, so this is the end stage for coloring.
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| SarC
| Joined: 19 Oct 2005 | Posts: 14 | : | | Items |
|
Posted: Tue Dec 06, 2005 10:12 pm Post subject: |
|
|
I've added the A!c + a!c = c!c (eliminate c) rule to my solver, so it produces output like this:
Code: |
Coloring combine: C!B and c!B = B!B
-------------
|...|...|...|
|11.|...|..1|
|.1C|...|B.1|
|---+---+---|
|...|...|...|
|Aa.|...|...|
|...|...|...|
|---+---+---|
|...|...|...|
|.B.|...|b..|
|1.c|...|..B|
-------------
Removing candidate 1 from all B's in cells [7, 3][2, 8][9, 9]
|
After this I wanted to code the other combine rule, so I went searching for a test puzzle, so I had something to test it on, but I couldn't find any! I've tried all 20 multicolor puzzles from Simple Sudoku and tried some from the top95, but no luck. So I was wondering if you could supply me with one ...
And just to be sure I have understood everything correctly I will present an example:
Code: |
-------------
|.7.|7.B|.C.|
|777|7..|...|
|777|7..|.c.|
|---+---+---|
|..A|a..|...|
|7.7|7.b|...|
|...|...|...|
|---+---+---|
|...|...|...|
|777|...|...|
|...|...|...|
-------------
excludes: B!C a!b
So if B!C and b!a then C!a. And I should be looking for cells that shares a house with a "c" and an "A" (ie the reverse of the new-found exclusion). And if I find any cell that match that criteria, I can exclude the candidate from that cell?
|
Thanks again for your time and knowledge
SarC |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Tue Dec 06, 2005 10:54 pm Post subject: |
|
|
View this topic for a good testset by Lummox JR: http://www.setbb.com/phpbb/viewtopic.php?t=320&mforum=sudoku
This sample (from the same topic) uses the transitivity you want to test:
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 think it's one of the best samples. It requires nothing but naked-hidden subsets + this single transitive coloring test.
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| SarC
| Joined: 19 Oct 2005 | Posts: 14 | : | | Items |
|
Posted: Thu Dec 08, 2005 12:32 am Post subject: |
|
|
Now I got the transitive test coded as well. Thanks for the link to the excellent post by Lummox JR and for all your help in my coloring quest.
Code: |
Coloring: Found excludes with complete simple coloring
-------------
|...|.99|99D|
|...|...|...|
|...|..A|a..|
|---+---+---|
|...|...|Bb.|
|...|...|...|
|...|...|...|
|---+---+---|
|...|.99|.9.|
|..C|.9.|9.d|
|..c|..9|9..|
-------------
Coloring transitive: D!a and d!C = a!C
Exclude c!A at [6, 9]
|
Works like a charm! . Now its onto the next technique heh |
|
Back to top |
|
|
|