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   

The multi-colouring method

 
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: Sun Jul 10, 2005 8:46 pm    Post subject: The multi-colouring method Reply with quote

Most people on this forum are familiar with the "simple" colouring method, an extension of x-wings which analyses a single possibility at a time by finding conjugate pairs of cells within rows/columns/boxes.

Several of us have struggled to find a multi-possible extension that was strictly logical by avoiding the temptation to do "what if" look-ahead.

Here's how far I've got with my multi-colouring method, using Nick70's "48-Unwind" as an example.

The puzzle is
Code:

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

and the starting point is
Code:

12458   28   1245   24789   1248   3   579   6   24579
234568   2368   245   246789   248   46789   579   1   24579
1246   9   7   5   124   146   3   8   24
14567   67   145   348   9   1458   2   357   135678
12569   26   8   23   7   15   4   35   13569
124579   27   3   248   6   1458   1579   57   15789
37   1   6   347   345   2   8   9   3457
23789   4   29   36789   358   56789   1567   2357   123567
23789   5   29   1   348   46789   67   2347   23467


I then produce a colour map for each of the possibles 1-9 and put them together into a combined map that looks like:
Code:

-   -   1e   9c   1a   -   -   -   -
6b   -   -   6h9d   -   7g   -   -   -
1a6a   -   -   -   1b   6b   -   -   -
-   6c7a   1f   3a   -   -   -   3b7b   6d8c
9a   2a6d   -   2b3b   -   -   -   3a   6c9b
9b   2b7b   -   2a   -   -   1d   7a   8d
-   -   -   4a   4b5a   -   -   -   5b
8b   -   -   6g   5b   6h7h   1c   -   1d
7e8a   -   -   -   8b   -   -   -   7f

The interpretation of the {5,4}=2b3b entry is that {5,4} has colour b in the colour map for possible 2 and (different) colour b in the colour map for possible 3. We can deduse that 2b and 3b are mutually exclusive - if 2b=true then 3b=false and vice-versa. The definition of conjugate colours means that if 3b-false then 3a=true. Thus we can say that 2b=true implies that 3a=true or in shorthand 2b -> 3a.

There are 38 colours in play at this point - 3 pairs 1a-1f for possible 1 up to 2 pairs 9a-9d for possible 9.

I construct a 38x38 "implication matrix" where, as shown above, entry (p,q) is true if colour p=true implies that colour q must also be true.

Here is the NW 10x10 corner of the matrix:

Code:

   1a   1b   1c   1d   1e   1f   2a   2b   3a   3b
1a   -   -   -   -   -   -   -   -   -   -
1b   -   -   -   -   -   -   -   -   -   -
1c   -   -   -   -   -   -   -   -   -   -
1d   -   -   -   -   -   -   -   -   -   -
1e   -   -   -   -   -   -   -   -   -   -
1f   -   -   -   -   -   -   -   -   -   -
2a   -   -   -   -   -   -   -   -   -   -
2b   -   -   -   -   -   -   -   -   X   -
3a   -   -   -   -   -   -   -   -   -   -
3b   -   -   -   -   -   -   X   -   -   -

The only entries in this part of the matrix are 2b -> 3a and 3b -> 2a, but there are many more entries in the full 38x38 matrix.
We can take this one step further by computing the "closure" of the matrix as follows. If p -> q and q -> r then we can deduce that also p -> r. This is a simple calculation for the whole matrix.
Some of the 35 closures are as follows:
2a -> 7a -> 2a
2a -> 7a -> 3a
2b -> 6b -> 2b
3b -> 2b -> 3a
3b -> 6b -> 2b

Having completed all the closures, the NW 10x10 looks like
Code:

   1a   1b   1c   1d   1e   1f   2a   2b   3a   3b
1a   -   -   -   -   -   -   -   -   -   -
1b   -   -   -   -   -   -   -   -   -   -
1c   -   -   -   -   -   -   -   -   -   -
1d   -   -   -   -   -   -   -   -   -   -
1e   -   -   -   -   -   -   -   -   -   -
1f   -   -   -   -   -   -   -   -   -   -
2a   -   -   -   -   -   -   X   -   X   -
2b   -   -   -   -   -   -   -   X   X   -
3a   -   -   -   -   -   -   -   -   -   -
3b   -   -   -   -   -   -   X   X   X   -

Note that the {3b,2a} and (3b,2b} entries are both true. This is telling us that 3b implies both 2a and 2b. But 2a excludes 2b and therefore the original assumption 3b must be false and 3a must be true.
We can therefore assign certainty 3 to all the 3a cells {4,4}, {5,8} and remove the possibility 3 from all 3b cells {5,4}, {4,8}. This enables the puzzle to be solved with ease.

I have one further trick that I'm looking at but let me know if you think the approach so far is valid and useful. It doesn't yet fully solve all of Nick70's puzzles but I will keep trying.

AMcK
Back to top
View user's profile Send private message Send e-mail
Gennadog

Joined: 03 Jun 2005
Posts: 5
:

Items
PostPosted: Sun Jul 17, 2005 8:28 am    Post subject: Re: The multi-colouring method Reply with quote

AMcK wrote:

Code:

-   -   1e   9c   1a   -   -   -   -
6b   -   -   6h9d   -   7g   -   -   -
1a6a   -   -   -   1b   6b   -   -   -
-   6c7a   1f   3a   -   -   -   3b7b   6d8c
9a   2a6d   -   2b3b   -   -   -   3a   6c9b
9b   2b7b   -   2a   -   -   1d   7a   8d
-   -   -   4a   4b5a   -   -   -   5b
8b   -   -   6g   5b   6h7h   1c   -   1d
7e8a   -   -   -   8b   -   -   -   7f

The interpretation of the {5,4}=2b3b entry is that {5,4} has colour b in the colour map for possible 2 and (different) colour b in the colour map for possible 3. We can deduse that 2b and 3b are mutually exclusive - if 2b=true then 3b=false and vice-versa. The definition of conjugate colours means that if 3b-false then 3a=true. Thus we can say that 2b=true implies that 3a=true or in shorthand 2b -> 3a.


I get this far and (except for a trivial difference in that I have the last 6-pair as E/F and not G/H - my numbering scheme assigns the letters after all the pairs have been found) I can follow the '2b3b' example that you give.

However...

Quote:
Some of the 35 closures are as follows:
2a -> 7a -> 2a
2a -> 7a -> 3a
2b -> 6b -> 2b
3b -> 2b -> 3a
3b -> 6b -> 2b


Can you please explain the '2a->7a' step. I can see the cell {6,2} which has the colour values 2b7b. I make the logical consequenses 2a->7b and 2b->7a using the same logic, but not where the 2a->7a comes from.

Can you please expand on this as I think that I'm missing something in the logic behind this.

Thanks

Don
Back to top
View user's profile Send private message
AMcK

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

Items
PostPosted: Sat Jul 23, 2005 10:18 pm    Post subject: Reply with quote

Don,
Sorry for the delay - I wasn't watching the list.
Quote:
Quote:
Some of the 35 closures are as follows:
2a -> 7a -> 2a
2a -> 7a -> 3a
2b -> 6b -> 2b
3b -> 2b -> 3a
3b -> 6b -> 2b

Can you please explain the '2a->7a' step. I can see the cell {6,2} which has the colour values 2b7b. I make the logical consequenses 2a->7b and 2b->7a using the same logic, but not where the 2a->7a comes from.

Sorry, there was a bug in the transcript code and the middle elements of all the closures were scrambled. 2a->7b and 2b->7a are correct. The correct set of full closures for this puzzle are:
Code:

2a[07]   6c[17]   7b[24]
2a[07]   6c[17]   9a[35]
2a[07]   7b[24]   2a[07]
2a[07]   7b[24]   3a[09]
2b[08]   7a[23]   6d[18]
3b[10]   2a[07]   3a[09]
3b[10]   2a[07]   6c[17]
3b[10]   2a[07]   7b[24]
3b[10]   2a[07]   9a[35]
3b[10]   7a[23]   6d[18]
6c[17]   7b[24]   2a[07]
6c[17]   7b[24]   3a[09]
6d[18]   2b[08]   3a[09]
6d[18]   2b[08]   6d[18]
6d[18]   2b[08]   7a[23]
7a[23]   6d[18]   2b[08]
7a[23]   6d[18]   3a[09]
7a[23]   6d[18]   7a[23]
7a[23]   6d[18]   8d[34]
7b[24]   2a[07]   6c[17]
7b[24]   2a[07]   7b[24]
7b[24]   2a[07]   9a[35]
8c[33]   6c[17]   2a[07]
8c[33]   6c[17]   3a[09]
8c[33]   6c[17]   7b[24]
8c[33]   6c[17]   9a[35]
9b[36]   6d[18]   2b[08]
9b[36]   6d[18]   3a[09]
9b[36]   6d[18]   7a[23]
9b[36]   6d[18]   8d[34]
2b[08]   6d[18]   2b[08]
2b[08]   6d[18]   8d[34]
3b[10]   6d[18]   2b[08]
3b[10]   6d[18]   8d[34]
6c[17]   2a[07]   6c[17]

(The [nn] are the row/column numbers in the multicolour implication matrix). Sorry for the error - but I'm most impressed that you found it!

I'm working now on the next step - looking for contradictions and other rules. e.g. 3b->3a so we prove 3b=False, 3a=True and solve the puzzle.

Code:
Conflict:   3b[10]   implies   2a[07]   2b[08]
reduction:   3a=True   {4,4}    before=348    after=3
reduction:   3b=False   {4,8}    before=357    after=57
reduction:   3b=False   {5,4}    before=23    after=2
reduction:   3a=True   {5,8}    before=35    after=3


AMcK
Back to top
View user's profile Send private message Send e-mail
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