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   

Supercolouring: exclusions vs implications

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
AMcK

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

Items
PostPosted: Thu Aug 11, 2005 11:12 am    Post subject: Supercolouring: exclusions vs implications Reply with quote

Sorry for the intensity of this thread. Anyone who hasn't got a clue what we're talking about should just ask and we'll try to explain.
I'm comparing Nick70's variant of my supercolouring solution method. He uses the equation
Code:
if excludes(x,y) and excludes(y',z) then excludes(x,z) where y' denotes the conjugate colour of y
to compute the transitive closure of the excludes matrix, whereas I use the equation
Code:
if implies(u,v) and implies(v,w) then implies(u,w)
to compute the transitive closure of the implies matrix. The transitive closure is at the heart of the method, since it is this which finds all paths through the coloured grid to detect contradictions (and, I would argue, identities).

Anyway, I was comparing the two methods using the following puzzle supplied I think originally by droid42
Code:
5 2 . ¦ . . . ¦ . 7 .
. . . ¦ . . . ¦ . 4 .
. 3 . ¦ 4 7 . ¦ . . 6
------+-------+-------
. 1 3 ¦ 6 8 . ¦ . . .
. . . ¦ 3 9 . ¦ . . .
6 4 . ¦ . . . ¦ . . 3
------+-------+-------
. . . ¦ . 4 . ¦ 7 . .
. 6 8 ¦ . . 5 ¦ . . 1
4 7 . ¦ . . . ¦ . 2 .

Simple reductions get us to the colour map
Code:
*        *    *        ¦ 1a8a9a 1b3a6a 3b6b8b9b ¦ 1c3c   *        8c9c   
*        8d9d *        ¦ *      1d3d   8e9e     ¦ 1e3e   *        *     
1f8f9f   *    1g9g     ¦ *      *      *        ¦ 5a8g9h 5b8h9i   *     
-----------------------+------------------------+------------------------
2a9j     *    *        ¦ *      *      4a7a     ¦ 2b5c9k 5d9l     4b7b   
2c8i     5e8j 2d5f7c   ¦ *      *      1h4c7d   ¦ 2e6c   1i6d     4d7e   
*        *    7f9m     ¦ *      *      1j7g     ¦ 8k9n   1k8l9o   *     
-----------------------+------------------------+------------------------
1l2f3f9p 5g9q 1m2g5h9r ¦ 1n8m9s *      6e8n9t   ¦ *      3g6f8o9u 5i8p9v
3h9w     *    *        ¦ *      *      *        ¦ *      3i9x     *     
*        *    1o5j9y   ¦ 1p8q9z 1q3j6g 3k6h8r9A ¦ 6i8s9B *        5k8t9C

The implication closure method finds lots of contradictions which prove that a colour must be false and its conjugates true. The most important are
Code:
False   True
1b   1h
1i   1h
3a   3g
3f   
4b   4a
6b   
6c   6d
6h   
8g   8k
9i   
9l   
9p   
9r   
9v   
9C   

I'll show the raw logic trace for the 3f=false
Code:
Exclusion in {7,1} 1g excludes 3f
Conjugate in row 3 1f conjugates 1g
3f excludes 1g and 1g conjugates 1f so 3f implies 1f
Exclusion in {8,8} 3f excludes 9x
Conjugate in row 8 9w conjugates 9x
3f excludes 9x and 9x conjugates 9w so 3f implies 9w
Constraint in box 7 9e excludes 9w
Conjugate in row 2 9d conjugates 9e
9w excludes 9e and 9e conjugates 9d so 9w implies 9d
3f implies 9w and 9w implies 9d so 3f implies 9d
Exclusion in {2,2} 8d excludes 9d
Conjugate in row 2 8d conjugates 8e
9d excludes 8d and 8d conjugates 8e so 9d implies 8e
Exclusion in {3,1} 1f excludes 8e
Conjugate in row 3 1f conjugates 1g
8e excludes 1f and 1f conjugates 1g so 8e implies 1g
9d implies 8e and 8e implies 1g so 9d implies 1g
3f implies 9d and 9d implies 1g so 3f implies 1g
Constraint in row 3 1f excludes 1g
Conflict: 3f implies 1f and 3f implies 1g but 1f excludes 1g
Reduction: 3f=false in {8,8} before=39 after=9

The final colour map after processing all the contradictions is
Code:
*      *    *      ¦ 1a8a9a 6a   3b8b9b ¦ 1c3c   *    8c9c
*      8d9d *      ¦ *      1c3c 8e9e   ¦ 1e3e   *    *   
1f8e9f *    1g9g   ¦ *      *    *      ¦ 5a9h   5b8h *   
-------------------+--------------------+------------------
2a9j   *    *      ¦ *      *    4a     ¦ 2b5b9k 5a   7b   
2c8d   5e8e 2d5f7c ¦ *      *    1h     ¦ 2a     6d   4a   
*      *    7f9m   ¦ *      *    7c     ¦ 8k     1h   *   
-------------------+--------------------+------------------
1g2d   5f9e 1m2g5h ¦ 1n8m9s *    6d     ¦ *      3g   5i8p
3g     *    *      ¦ *      *    *      ¦ *      9x   *   
*      *    1o5i9y ¦ 1p8q9z 1q3b 3k8r9A ¦ 6d     *    5k8t
which is easily solved using simple rules.

Sadly, my first implementation of Nick70's exclusion closure variant can only find one of the above contradictions
Code:
Contradiction: 9o excludes 9o
Reduction: 9o=false in {6,8} before=189 after=18
Reduction: 9o=false in {6,8} before=189 after=18


I've checked the exclusion matrix but can't see what's wrong. Can anyone who has implemented Nick70's variant confirm this or convince me that it's a bug in my code.

Regards
Andrew
Back to top
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Thu Aug 11, 2005 8:08 pm    Post subject: Reply with quote

All I can do is post the output of my routine.

Sorry about the ?s - I ran out of alphabetic letters.

Code:
5     2     4      | 189   136   3689   | 13    7     89   
                   | nop   qrm   kMst   | aA          bB   
7     89    6      | 5     13    89     | 13    4     2     
      cC           |       aA    Cc     | Aa               
189   3     19     | 4     7     2      | 589   589   6     
DCu         dD     |                    | gvw   Gxy         
-------------------+--------------------+-------------------
29    1     3      | 6     8     47     | 259   59    47   
eE                 |             fF     | EGz   gG    Ff   
28    58    257    | 3     9     147    | 26    16    47   
Cc    cC    jCe    |             eF?    | eE    Ee    fF   
6     4     79     | 2     5     17     | 89    189   3     
            Ee     |             Ee     | hH    eH?         
-------------------+--------------------+-------------------
1239  59    1259   | 189   4     689    | 7     3689  589   
djI?  Cc    ?J??   | ???         e??    |       iE??  l??   
39    6     8      | 7     2     5      | 4     39    1     
iI                 |                    |       Ii         
4     7     159    | 189   136   3689   | 689   2     589   
            ?l?    | ???   ?kM   K???   | e??         L??   

I excludes c and C excludes l, therefore I excludes l
D excludes C and c excludes I, therefore D excludes I
e excludes C and c excludes I, therefore e excludes I
I excludes d and D excludes I, therefore I excludes I
I excludes itself, therefore it's false (and i is true)
C excludes D and d excludes I, therefore C excludes I
C excludes e and E excludes G, therefore C excludes G
C excludes e and E excludes i, therefore C excludes i
D excludes e and E excludes G, therefore D excludes G
D excludes e and E excludes i, therefore D excludes i
F excludes e and E excludes G, therefore F excludes G
F excludes e and E excludes i, therefore F excludes i
F excludes e and E excludes I, therefore F excludes I
H excludes e and E excludes i, therefore H excludes i
H excludes e and E excludes I, therefore H excludes I
G excludes E and e excludes I, therefore G excludes I
G excludes E and e excludes j, therefore G excludes j
G excludes E and e excludes M, therefore G excludes M
i excludes E and e excludes j, therefore i excludes j
i excludes E and e excludes M, therefore i excludes M
I excludes E and e excludes M, therefore I excludes M
C excludes i and I excludes C, therefore C excludes C
C excludes itself, therefore it's false (and c is true)
C excludes i and I excludes d, therefore C excludes d
C excludes i and I excludes E, therefore C excludes E
C excludes i and I excludes F, therefore C excludes F
C excludes i and I excludes H, therefore C excludes H
C excludes i and I excludes M, therefore C excludes M
D excludes i and I excludes D, therefore D excludes D
D excludes itself, therefore it's false (and d is true)
D excludes i and I excludes E, therefore D excludes E
D excludes i and I excludes F, therefore D excludes F
D excludes i and I excludes H, therefore D excludes H
D excludes i and I excludes j, therefore D excludes j
D excludes i and I excludes l, therefore D excludes l
D excludes i and I excludes M, therefore D excludes M
E excludes i and I excludes E, therefore E excludes E
E excludes itself, therefore it's false (and e is true)
E excludes i and I excludes F, therefore E excludes F
E excludes i and I excludes H, therefore E excludes H
E excludes i and I excludes j, therefore E excludes j
E excludes i and I excludes l, therefore E excludes l
E excludes i and I excludes M, therefore E excludes M
F excludes i and I excludes F, therefore F excludes F
F excludes itself, therefore it's false (and f is true)
F excludes i and I excludes H, therefore F excludes H
F excludes i and I excludes j, therefore F excludes j
F excludes i and I excludes l, therefore F excludes l
F excludes i and I excludes M, therefore F excludes M
G excludes i and I excludes G, therefore G excludes G
G excludes itself, therefore it's false (and g is true)
G excludes i and I excludes l, therefore G excludes l
H excludes i and I excludes H, therefore H excludes H
H excludes itself, therefore it's false (and h is true)
H excludes i and I excludes j, therefore H excludes j
H excludes i and I excludes l, therefore H excludes l
H excludes i and I excludes M, therefore H excludes M
j excludes i and I excludes j, therefore j excludes j
j excludes itself, therefore it's false (and J is true)
j excludes i and I excludes l, therefore j excludes l
j excludes i and I excludes M, therefore j excludes M
M excludes i and I excludes M, therefore M excludes M
M excludes itself, therefore it's false (and m is true)
c excludes I and i excludes D, therefore c excludes D
c excludes I and i excludes E, therefore c excludes E
c excludes I and i excludes F, therefore c excludes F
c excludes I and i excludes G, therefore c excludes G
c excludes I and i excludes H, therefore c excludes H
c excludes I and i excludes j, therefore c excludes j
c excludes I and i excludes M, therefore c excludes M
d excludes I and i excludes E, therefore d excludes E
d excludes I and i excludes F, therefore d excludes F
d excludes I and i excludes G, therefore d excludes G
d excludes I and i excludes H, therefore d excludes H
d excludes I and i excludes M, therefore d excludes M
e excludes I and i excludes G, therefore e excludes G
l excludes I and i excludes M, therefore l excludes M
extended matrix by 68 exclusions

  - Put 6 in r1c5
  - Put 8 in r2c2
  - Put 9 in r2c6
  - Put 1 in r3c3
  - Put 5 in r3c7
  - Put 2 in r4c1
  - Put 4 in r4c6
  - Put 5 in r4c8
  - Put 7 in r4c9
  - Put 8 in r5c1
  - Put 5 in r5c2
  - Put 7 in r5c3
  - Put 1 in r5c6
  - Put 2 in r5c7
  - Put 6 in r5c8
  - Put 4 in r5c9
  - Put 9 in r6c3
  - Put 7 in r6c6
  - Put 8 in r6c7
  - Put 1 in r6c8
  - Put 1 in r7c1
  - Put 9 in r7c2
  - Put 2 in r7c3
  - Put 6 in r7c6
  - Put 3 in r7c8
  - Put 3 in r8c1
  - Put 9 in r8c8
  - Put 6 in r9c7
Back to top
View user's profile Send private message
AMcK

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

Items
PostPosted: Mon Aug 15, 2005 12:17 am    Post subject: Reply with quote

Thanks for the transcript. I've learnt a lot from it and incorporated some new thinking but haven't quite finished.
I note that you have pre-coloured all the identities - for same and different possibles in your map - so you must have a pre-pass that assigns colours based on concepts of conjugacy and identity.
I prefer to do this as a post-transformation on the colour map by transitive closure - but I suppose there's no point in *debating* this.
Perhaps as a result of some bug fixes, Supertough4 [Nick70]
has now joined supertough5 as supercolouring-solvable. Can anyone else confirm this?
Supertough 5
Code:
5 . . ¦ 2 . . ¦ . . .
. . 6 ¦ . . . ¦ 1 . .
. 9 . ¦ 3 . . ¦ . . .
------+-------+-------
. . . ¦ . 1 . ¦ 3 . 9
. . 7 ¦ . . . ¦ 5 . .
8 . 4 ¦ . 6 . ¦ . . .
------+-------+-------
. . . ¦ . . 5 ¦ . 8 .
. . 2 ¦ . . . ¦ 7 . .
. . . ¦ . . 4 ¦ . . 6

Initial map
Code:
5        4a7a8a   1a3a8b 2      4b7b8c9a   1b6a 6b8d 7c9b       4c7d       
2a3b4d7e 2b4e7f8e 6      7g8f9c 4f5a7h8g9d 7i8h 1    2c3c5b7j9a 2d3d4g5c7k
2e4h7l   9        1b8d   3      4i5d7m     1a6b 6a8j 2f5e7n     2g4j5f7o   
2b6e     2i6f     5      7i8h   1          7q8l 3    4          9         
9        1        7      4      3          2    5    6          8         
8        3        4      5      6          9    2    1e7r       1f7s       
1g3d6g7t 6h7u     9      1h6i7v 2j7w       5    4    8          2k3c       
4k6j     4l6k8m   2      6l8n9f 8o9c       3    7    1f5g       1e5h       
1h3g7x   5        3b8p   1g7y8q 2k7z8r     4    9    2j3d       6         

Contradictions
Code:
Forcing: 8j=true {3,7} before=68 after=8
Reduction: 1a=false in {3,6} before=16 after=6
Reduction: 3b=false in {9,3} before=38 after=8
Reduction: 7c=false in {1,8} before=79 after=9
Reduction: 8m=false in {8,2} before=468 after=46
Reduction: 8q=false in {9,4} before=178 after=17
Reduction: 8r=false in {9,5} before=278 after=27
Reduction: 9a=false in {2,8} before=23579 after=2357

Final map
Code:
5        4a7a8a   3 2      4b7b8c     1    6 9        4c7d       
2a4d7e   2b4e7f8e 6 7g8f9c 4f5a7h8g9d 7i8h 1 2c3c5b7j 2d3d4g5c7k
2e4h7l   9        1 3      4i5d7m     6    8 2f5e7n   2g4j5f7o   
2b6e     2i6f     5 7i8h   1          7q8l 3 4        9         
9        1        7 4      3          2    5 6        8         
8        3        4 5      6          9    2 1e7r     1f7s       
1g3d6g7t 6h7u     9 1h6i7v 2j7w       5    4 8        2k3c       
4k6j     4l6k     2 6l8n9f 8o9c       3    7 1f5g     1e5h       
1h3g7x   5        8 1g7y   2k7z       4    9 2j3d     6         

Supertoughs 1-3 are still for the moment out of reach, as is Menneske 900610, although I can see that the "table" methods that Bowman and Mad Overlord have published are feasible.
Regards
Andrew
Back to top
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Mon Aug 15, 2005 7:18 am    Post subject: Reply with quote

AMcK wrote:
I note that you have pre-coloured all the identities - for same and different possibles in your map - so you must have a pre-pass that assigns colours based on concepts of conjugacy and identity.

As I wrote in the other hread:

Nick70 wrote:
1) Assign colors to conjugates
Assign a different colour pair to every chain of conjugate possibles in the partial grid. Use even/odd pairs of colors, so 0/1 are conjugate, 2/3 are conjugate, and so on. Using the dancing links data structures, this is done very easily and efficiently using a recursive algorithm.
At the end of step 1) all possibles that have a conjugate are colored, using the minimal number of colors. We don't need a "conjugate" table, because the conjugation property is embedded in the color.

There is no distinction between candidate numbers when coloring. It vould be arbitrary, two numbers in the same cells or two positions for a number in the same unit are exactly the same thing.

AMcK wrote:
I prefer to do this as a post-transformation on the colour map by transitive closure - but I suppose there's no point in *debating* this.

The way I do it is just much faster.
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
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