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   

Confused over Colouring
Goto page Previous  1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Mon Jul 04, 2005 8:40 am    Post subject: Reply with quote

Both the advanced puzzles fall to "forcing chains". This seems to catch many of the puzzles that could otherwise be solved with colouring.
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Mon Jul 04, 2005 8:56 am    Post subject: Reply with quote

Many thanks to Nick70 for discovering the two new post-colouring reductions and for increasing the library of colouring examples. Since Nishio is censured by purists as a 1-step "what if" lookahead on the borderline between logic and trial & error, it is pleasing if colouring can achieve the same results by logical analysis alone.

Quote:
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.


Technique (3) was in my original design but (1) and (2) and excellent new discoveries which I will program into my solver.

I was able to solve puzzles 1-3 by colouring: (1) has double exclusion on 3 plus excluding pair on 7; (2) has immediate contradiction on 7; (3) has double exclusion on 7.

I'm still looking at simple puzzle 4 and advanced puzzle 2. What is the difference between simple colouring and advanced colouring?

I've suspected for some time that the simultaneous colouring of several possibles might unlock some of the deeper dependency structure of the puzzle - Nick70's advanced puzzle 1 is the first example I've seen where this is worthwhile.

Code:
.   .   1   .   8   .   3   .   9
.   3   5   6   .   .   .   .   .
9   .   .   .   .   .   .   .   .
.   .   .   .   .   5   .   .   .
.   .   8   .   1   .   6   .   .
.   .   .   4   .   .   .   .   .
.   .   .   .   .   .   .   .   7
.   .   .   .   .   7   5   2   .
8   .   4   .   6   .   1   .   .

which can be reduced to
Code:

26   26   1   7   8   4   3   5   9
4   3   5   6   2   9   7   8   1
9   8   7   3   5   1   2   4   6
136   4   36   8   7   5   9   13   2
5   9   8   2   1   3   6   7   4
7   12   23   4   9   6   8   13   5
12   5   29   19   3   8   4   6   7
136   16   369   19   4   7   5   2   8
8   7   4   5   6   2   1   9   3

Its colour map for possible 1 is
Code:

-   -   *   -   -   -   -   -   -
-   -   -   -   -   -   -   -   *
-   -   -   -   -   *   -   -   -
a   -   -   -   -   -   -   b   -
-   -   -   -   *   -   -   -   -
-   b   -   -   -   -   -   a   -
e   -   -   f   -   -   -   -   -
*   a   -   e   -   -   -   -   -
-   -   -   -   -   -   *   -   -

and for possible 6 is
Code:

a   b   -   -   -   -   -   -   -
-   -   -   *   -   -   -   -   -
-   -   -   -   -   -   -   -   *
c   -   d   -   -   -   -   -   -
-   -   -   -   -   -   *   -   -
-   -   -   -   -   *   -   -   -
-   -   -   -   -   -   -   *   -
*   a   c   -   -   -   -   -   -
-   -   -   -   *   -   -   -   -

Look at the contradiction in cells (3,1) and (8,2): the colour map for 6 says that one of them must be 6 but the colour map for 1 says that if one of them is 1 then they must both be 1. We can deduce that neither of them can be 1 and therefore colour map 1 has the solution b=1.
Colouring can't say any more at this stage but this is sufficient to solve the remainder of the puzzle by simple reductions

My thanks again to Nick70 for producing such excellent toys to play with.
AMcK
Back to top
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Mon Jul 04, 2005 9:24 am    Post subject: Reply with quote

coconut wrote:
The 4 simple colouring problems can be solved using standard techniques (x-wings, swordfish,, nishio etc).


x-wings - no, I don't consider that simple coloring (even if it's a special case)
swordfish and nishio - could be, I didn't look for those.

I previously stated that swordfish is a special case of coloring, but that isn't true in general. A swordfish on rows where all three columns have more than two possibilities will not be identified by the coloring algorithm I'm currently using.

Swordfish is instead a more general case of naked triples, just like x-wing is a more general case of naked pairs. I haven't implemented triples yet in my program so it won't catch all swordfishes.

coconut wrote:
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.


It is very difficult indeed. This might help:

Code:

.      .      1       | 3      4      9       | 8      5      6     
4      3      5       | 6      .      1-8     | 2      .      .     
9      6      8       |[2-7]   5     [1-2]    | 3      1-7    4     
----------------------+-----------------------+----------------------
6      .      .       | 9      .      5       | 4      .      .     
5      4      9       |[2-7-8] 1     [2-8]    | 6      3     [2-7]   
.      .      .       | 4      .      6       | 5      .      .     
----------------------+-----------------------+----------------------
.      5      .       | 1-2-8  .      4       | 9      6      3     
3      9      4       | 5      6      7       | 1      2      8     
8      12     6       | 1-2    9      3       | 7      4      5     


Look at the cells I put in square brackets.

coconut wrote:
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?


Simple coloring is not equivalent to standard techniques - swordfish and nishio can solve problems that simple coloring can't. I'm not sure if there are problems that simple coloring can solve and nishio cannot, but I find coloring a better technique than nishio because nishio needs to focus on a specific cell while coloring works on the whole board and leads to the solution automatically.

Advanced coloring can definitely solve problems that the other techniques fail with.
Back to top
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Mon Jul 04, 2005 9:26 am    Post subject: Reply with quote

Simes wrote:
Both the advanced puzzles fall to "forcing chains". This seems to catch many of the puzzles that could otherwise be solved with colouring.


Advanced coloring is indeed a way to bring out all forcing chaing present on the board, all at the same time.
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Mon Jul 04, 2005 9:44 am    Post subject: Reply with quote

AMcK wrote:
Look at the contradiction in cells (3,1) and (8,2): the colour map for 6 says that one of them must be 6

I'm afraid I don't see that.

Firstly, I'll presume you mean cells (4,1) and (8,2). Anyhow, there's no way to derive a conjugate relationship between those 2 cells for 6s so I disagree that one must be a 6.
Back to top
View user's profile Send private message Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Mon Jul 04, 2005 9:48 am    Post subject: Reply with quote

AMcK wrote:
What is the difference between simple colouring and advanced colouring?


Simple coloring focuses on one number at a time. Advanced coloring looks at all possible pairs (cell, number), therefore identifying not only all units where a number can be in two cells, but all cells which can contain two numbers. This links together the simple colorings for all 9 numbers, identifying all existing forcing chains.

AMcK wrote:
Look at the contradiction in cells (3,1) and (8,2): the colour map for 6 says that one of them must be 6 but the colour map for 1 says that if one of them is 1 then they must both be 1.


I assume you mean (4,1) instead of (3,1), but I'm afraid that doesn't work. The map for 6 says that the 6 can be in both cells, but it could also be in neither, because the colors A and C are not conjugate.

The forcing chain you are looking for actually requires three numbers.

Code:

[2-6]  [2-6]   1       | 7      8      4       | 3      5      9     
 4      3      5       | 6      2      9       | 7      8      1     
 9      8      7       | 3      5      1       | 2      4      6     
 ----------------------+-----------------------+----------------------
 1-3-6  4      .       | 8      7      5       | 9      .      2     
 5      9      8       | 2      1      3       | 6      7      4     
 7      1-2    .       | 4      9      6       | 8      .      5     
 ----------------------+-----------------------+----------------------
[1-2]   5      .       | .      3      8       | 4      6      7     
 1-3-6 [1-6]   .       | .      4      7       | 5      2      8     
 8      7      4       | 5      6      2       | 1      9      3     
Back to top
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Mon Jul 04, 2005 2:39 pm    Post subject: Reply with quote

Quote:

I assume you mean (4,1) instead of (3,1), but I'm afraid that doesn't work. The map for 6 says that the 6 can be in both cells, but it could also be in neither, because the colors A and C are not conjugate.

I agree - apologies for the error imagining that the two colours were conjugates.

Using the same example
Code:

[2-6]  [2-6]   1       | 7      8      4       | 3      5      9     
 4      3      5       | 6      2      9       | 7      8      1     
 9      8      7       | 3      5      1       | 2      4      6     
 ----------------------+-----------------------+----------------------
 1-3-6  4      .       | 8      7      5       | 9      .      2     
 5      9      8       | 2      1      3       | 6      7      4     
 7      1-2    .       | 4      9      6       | 8      .      5     
 ----------------------+-----------------------+----------------------
[1-2]   5      .       | .      3      8       | 4      6      7     
 1-3-6 [1-6]   .       | .      4      7       | 5      2      8     
 8      7      4       | 5      6      2       | 1      9      3     

The colour map for 2 is
Code:

a   b   -   -   -   -   -   -   -
-   -   -   -   *   -   -   -   -
-   -   -   -   -   -   *   -   -
-   -   -   -   -   -   -   -   *
-   -   -   *   -   -   -   -   -
-   a   b   -   -   -   -   -   -
b   -   a   -   -   -   -   -   -
-   -   -   -   -   -   -   *   -
-   -   -   -   -   *   -   -   -

and for 6 is
Code:

a   b   -   -   -   -   -   -   -
-   -   -   *   -   -   -   -   -
-   -   -   -   -   -   -   -   *
c   -   d   -   -   -   -   -   -
-   -   -   -   -   -   *   -   -
-   -   -   -   -   *   -   -   -
-   -   -   -   -   -   -   *   -
*   a   c   -   -   -   -   -   -
-   -   -   -   *   -   -   -   -

Thus {1,1} and {1,2} are shown to be conjugates in two overlaid colour maps - 2 and 6.
Using both colour maps, you can therefore assert only two cases:
A: {1,1}=2; {1,2}=6; {7,1}<>2; {8,2}<>6
B: {1,1}=6; {1,2}=2; {7,1}=2; {8,2}=6
Since the possibles grid shows {7,1}=12 and {8,2}=16, case B would clearly imply that {7,1}={8,2}=1, which is forbidden.
Therefore case A is the only viable candidate.
Clearly, the search for such overlapping colour maps is computationally trivial.

I leave it to others to classify this approach as trial & error or whether it makes ir closer to Limited Implication Trees.
Back to top
View user's profile Send private message Send e-mail
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Tue Jul 05, 2005 8:37 am    Post subject: Colouring algorithm definition Reply with quote

Several people have complained that I did not define the colouring algorithm but merely supplied examples of its operation.

Here is an attempt to define "simple" colouring as I have implemented it so far. May thanks to others on this list who have helped with the concept and whose ideas and words I have borrowed from. The mistakes are my own and all comments are welcome.

The algorithm solves all 4 of Nick70's "simple" puzzles, typically in 0.03 seconds, and supplies the information necessary to manually solve his 2 "advanced" puzzles.

Definition: A conjugate pair is a pair of cells in a row/column/box which are the only possible locations in the partial solution grid for the possible under consideration.
We know therefore that the possible must lie in one or other of the cells in the solution.
The "simple" colouring algorithm is applied to each possible 1-9 in turn and finds all conjugate pairs in the partial solution grid.
It determines the minimum number of colour pairs by analysing the logical dependencies between conjugate pairs across the entire grid.
The term "colouring" is used because the technique is analagous to marking up the grid using coloured pens.
Further "advanced" colouring techniques are being developed.

1) Scan rows, columns, blocks for conjugate pairs and assign colours
Each conjugate pair assigned a pair of conjugate colours as follows:
a. If both cells already have colours which are already conjugate then no further action is necessary.
b. If neither cell in the pair already has a colour assigned, they are assigned an unused conjugate pair.
c. If one of the cells is already coloured, but the other is not, then the uncoloured cell is assigned the conjugate colour to the coloured one.
d. If both cells already have colours which are not conjugate, say (P,Q), then we merge the two colour pairs into one pair.
Assign colour P to all cells coloured with Q's conjugate
and assign P's conjugate to all cells coloured Q.
Q and its conjugate can be discarded for re-use.

2) Scan colour matrix for mutually exclusive colours pairs
Scan all the coloured cells in each row/column/box
If there are exactly two coloured cells in a row/column/box which are not already conjugates and their conjugates are the onlt two coloured cells in some other row/column/box then it is valid to merge the two colour pairs into one, again recolouring any cells from the discarded colour pair.

3) Scan coloured grid for possible reductions
Scan each row/colum/box in turn and consider those which now contain cells coloured with conjugate colours.
a. Excluding Pair.
If a row/colum/box contains a pair of cells with conjugate colours, one or the other must be true and so all other instances of the possible in the unit can be removed.
b. Immediate Contradiction.
If two cells in the same row/colum/box have the same color, they cannot be both true at the same time, they must be both false.
The possible can therefore be removed from all instances of that colour in the entire grid.
All instances of the conjugate colour in the entire grid can be set to a certainty for the possible.
c. Double Exclusion.
If a colour A occurs in a row/column/block conjunction with a non-conjugate colour C then A and C cannot be simultaneously true.
If its conjugate B occurs in another row/column/block conjunction with the same non-conjugate colour C, then B and C cannot be simultaneously true.
Since A and B are conjugates then one of A or B must be true and therefore C must be false.
The possible can therefore be removed from all instances of C in the entire grid.
All instances of the C's conjugate colour in the entire grid can be set to a certainty for the possible.
Back to top
View user's profile Send private message Send e-mail
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Jul 05, 2005 9:23 am    Post subject: Re: Colouring algorithm definition Reply with quote

AMcK wrote:
Here is an attempt to define "simple" colouring as I have implemented it so far.

Thank you Andrew for your very detailed explanation.
Back to top
View user's profile Send private message Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Tue Jul 05, 2005 10:29 am    Post subject: Re: Colouring algorithm definition Reply with quote

AMcK wrote:
1) Scan rows, columns, blocks for conjugate pairs and assign colours
Each conjugate pair assigned a pair of conjugate colours as follows:
a. If both cells already have colours which are already conjugate then no further action is necessary.
b. If neither cell in the pair already has a colour assigned, they are assigned an unused conjugate pair.
c. If one of the cells is already coloured, but the other is not, then the uncoloured cell is assigned the conjugate colour to the coloured one.
d. If both cells already have colours which are not conjugate, say (P,Q), then we merge the two colour pairs into one pair.
Assign colour P to all cells coloured with Q's conjugate
and assign P's conjugate to all cells coloured Q.
Q and its conjugate can be discarded for re-use.


When I assign a color to a pair, I recursively scan the board for all other pairs containing one of the cells, so I can immediately assign the correct color and avoid any recoloring (step d is not needed).
This is also more similar to how a human would work.

AMcK wrote:
2) Scan colour matrix for mutually exclusive colours pairs

...

3) Scan coloured grid for possible reductions


I actually do 3) first, then 2), then 3) again. The idea is to first spot the immediate consequences of the coloring, and only if that fails attempt to further reduce the number of colors. This way the program attempts to report the most intuitive option available.
Back to top
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Tue Jul 05, 2005 11:45 am    Post subject: Reply with quote

Quote:
When I assign a color to a pair, I recursively scan the board for all other pairs containing one of the cells, so I can immediately assign the correct color and avoid any recoloring (step d is not needed).
This is also more similar to how a human would work.

Yes, that's a good heuristic, but it would have to look at all the connectable cells and invoke itself iteratively again at the end of colouring each of them, taking care that algorithm couldn't cycle. It could be similar in structure (but using different semantics) to the vertex/edge algorithm of phishy cycles.
Quote:
I actually do 3) first, then 2), then 3) again. The idea is to first spot the immediate consequences of the coloring, and only if that fails attempt to further reduce the number of colors. This way the program attempts to report the most intuitive option available.

I also make the same mistake of scanning all the houses systematically when I solve puzzles by hand - which is why I'm so slow.
I need to put some heuristics in to optimise the sequencing of the all the algorithms.
Regards
AMcK
Back to top
View user's profile Send private message Send e-mail
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Tue Jul 05, 2005 12:30 pm    Post subject: advanced colouring example 2 Reply with quote

Nick 70's "advanced colouring" example 2
Code:
..1.4.8.6
.356.....
9........
.....5...
..9.1.6..
...4.....
........3
.....712.
8.6.9.7..

Code:

Colouring for digit: 7                        
a   b   -   -   -   -   -   -   -
-   -   -   -   d   -   -   *   *
-   -   -   c   -   -   -   d   -
-   *   *   -   *   -   -   *   *
-   -   -   d   -   -   -   -   c
*   *   *   -   *   -   -   *   *
g   -   h   -   -   -   -   -   -
-   -   -   -   -   *   -   -   -
-   -   -   -   -   -   *   -   -
Colouring for digit: 8                        
-   -   -   -   -   -   *   -   -
-   -   -   -   a   b   -   -   -
-   -   *   -   -   -   -   -   -
-   c   -   -   -   -   -   d   -
-   -   -   b   -   a   -   -   -
-   d   -   -   -   -   -   c   -
-   -   -   a   b   -   -   -   -
-   -   -   -   -   -   -   -   *
*   -   -   -   -   -   -   -   -

Look at {2,5} and {5,4}.
The colour map for possible 8 has them as conjugates so they must be different.
But they can't both be colour d for possible 7 so you prove d=False and c=True and discover 4 certainties and 1 reduction. Sweet!
I'm still struggling to find the simplest set of purely logical multi-colour rules.
AMcK
Back to top
View user's profile Send private message Send e-mail
coconut

Joined: 13 May 2005
Posts: 12
:
Location: Oxford

Items
PostPosted: Wed Jul 06, 2005 6:51 am    Post subject: Reply with quote

I understand that some of us like to consider nishio as a stepmother but iin my view it is the only rule one has to use to derive new rules. The importance of this concept has been emphasised many times by Rubylips.

Going back to Nick70's advanced-colouring example 2, if we assume that (2,5) in the seventh plane is correct, nishio does not give a contradiction in that plane. Thus, "simple" nishio fails to give any new information. However, if we analyse the eigth plane, there is a failure as a consequence of this assumption on the seventh plane. Thus, the "complex" nishio shows that (2,5) is not a 7.

Most standard techniques (x-wings, swordfish) will not solve this problem since they essentially work on the same plane. However, "complex" nishio can be used across planes to solve many more problems and more importantly to justify new techniques such as colouring.

coconut
Back to top
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Wed Jul 06, 2005 9:11 am    Post subject: Reply with quote

coconut wrote:
Most standard techniques (x-wings, swordfish) will not solve this problem since they essentially work on the same plane. However, "complex" nishio can be used across planes to solve many more problems and more importantly to justify new techniques such as colouring.


Any don't think coloring needs any "justification" from nishio Smile

The problem with nishio is that you have to focus on a specific value in a specific cell, and draw consequences from that.

Coloring, instead, works on the whole board at the same time. Even in its advanced form, what it does is simplify the problem by reducing pencilmarks to colors, and then drawing conclusions from the colors. When you start a nishio, you need to know which cell to look at and what value to put in it. When you start coloring, you don't have to know where it will lead you.
Back to top
View user's profile Send private message
coconut

Joined: 13 May 2005
Posts: 12
:
Location: Oxford

Items
PostPosted: Wed Jul 06, 2005 10:11 am    Post subject: Reply with quote

Perhaps, I shouldnt have mentioned nishio since it is not always consider as a "logical step".

However, AMcK's solution is based on reductio absurdum (some of the old guys might remember this from school lessons in Euclidean geometry) in the context of colouring. I have extracted the following from the internet dictionary of philosophy:

Reductio ad absurdum is a mode of argumentation that seeks to establish a contention by deriving an absurdity from its denial, thus arguing that a thesis must be accepted because its rejection would be untenable. It is a style of reasoning that has been employed throughout the history of mathematics and philosophy from classical antiquity onwards.

I do not think that the use of this argument wouldl hinder sudoku solvers and colouring techniques. In my view, most of the valid techniques are mathematically/philosophically equivalent. The differences are in implementation.

coconut
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
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