FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Advanced coloring - very hard Goto page 1, 2  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Jul 05, 2005 8:56 pm    Post subject: Advanced coloring - very hard I have added even more devious logic to my program - now it can solve problems like this one using coloring. Code: 31.6..... ..2...... .8..9.76. .....5... .6..1..9. ...4..... .98.6..3. ......5.. .....7.42 It took me a good 15 minutes to reconstruct how it did it Very neat. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Tue Jul 05, 2005 11:49 pm    Post subject: Re: Advanced coloring - very hard Nick70 wrote: It took me a good 15 minutes to reconstruct how it did it Very neat. Well done, but I think I'll stick to puzzles mere mortals can solve . Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 5:54 am    Post subject: Re: Advanced coloring - very hard angusj wrote: Well done, but I think I'll stick to puzzles mere mortals can solve . It's absolutely something that can be done by humans. It's quite in your face once you've seen it. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 12:06 pm    Post subject: Nobody biting the bait? Need some hints? Back to top Simes Joined: 08 Apr 2005 Posts: 71 : Location: North Yorkshire, UK Items Posted: Wed Jul 06, 2005 12:16 pm    Post subject: Sorry, I didn't recognise it as bait! I'd say there are some cells linked from (5,1) that allow you to enter numbers in (5,3), (5,9) and (6,2). (But that's just a wild guess.) _________________ Simes www.sadmansoftware.com/sudoku Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 12:48 pm    Post subject: Simes wrote: I'd say there are some cells linked from (5,1) that allow you to enter numbers in (5,3), (5,9) and (6,2). Well spotted! It wasn't that hard after all. I will post a harder problem later Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 1:47 pm    Post subject: This one should be difficult, I don't see a short forcing chain leading to the solution. Code: 39.6..... ..5...... .6..2.47. .....5... .2..1..6. ...4..... .78.6..3. ......5.. .....7.42 Back to top Simes Joined: 08 Apr 2005 Posts: 71 : Location: North Yorkshire, UK Items Posted: Wed Jul 06, 2005 4:13 pm    Post subject: (2,5) = 7 : Forced from either candidate of (4,1) _________________ Simes www.sadmansoftware.com/sudoku Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 5:16 pm    Post subject: Simes wrote: (2,5) = 7 : Forced from either candidate of (4,1) Wow. I can't see it. How do you derive that? Back to top Simes Joined: 08 Apr 2005 Posts: 71 : Location: North Yorkshire, UK Items Posted: Wed Jul 06, 2005 7:42 pm    Post subject: I recant maximally! On further reflection, I think my forcing chain algorithm is a little over zealous! Although it correctly finds forced cells, it goes beyond what is humanly possible by looking for more than simply linked cells, i.e. it finds links resulting from eliminated candidates because of previously linked cells. Too much, and not what I wanted to achieve. I've now limited it to simple chains of two-candidate cells - and it no longer finds a solution to the above problems... either of them. Oh well, it was good while it lasted. _________________ Simes www.sadmansoftware.com/sudoku Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 06, 2005 9:28 pm    Post subject: Simes wrote: I've now limited it to simple chains of two-candidate cells - and it no longer finds a solution to the above problems... either of them. Either of them? I don't think that's right. The chain is quite obvious in the first one: Code: 3     1     9      | 6     7     48     | 248   25    458 6     7     2      | 38    5     348    | 48    1     9 5     8     4      | 2     9     1      | 7     6     3 -------------------+--------------------+------------------ 278   4     137    | 9     238   5      | 6     27    18 28    6     35     | 7     1     38     | 2348  9     458 9     23    157    | 4     238   6      | 238   57    15 -------------------+--------------------+------------------ 4     9     8      | 5     6     2      | 1     3     7 27    23    37     | 1     4     9      | 5     8     6 1     5     6      | 38    38    7      | 9     4     2 (5,1)=2 => (6,2)=3 => (5,3)=5 (5,1)=8 => (5,6)=3 => (5,3)=5 The second problem however is a different matter. I'll show how I did it. This is where we get with the usual rules: Code: 3     9     7      | 6     5     4      | 18    2     18 2     4     5      | 178   78    18     | 3     9     6 8     6     1      | 39    2     39     | 4     7     5 -------------------+--------------------+------------------- 79    38    6      | 2     3789  5      | 78    1     4 5     2     4      | 378   1     38     | 789   6     389 179   138   39     | 4     3789  6      | 2     5     38 -------------------+--------------------+------------------- 4     7     8      | 5     6     2      | 19    3     19 6     13    2      | 139   4     139    | 5     8     7 19    5     39     | 138   38    7      | 6     4     2 Let's put some coloring over the pencilmarks: Code: 3     9     7      | 6     5     4      | 18    2     18                    |                    | 2     4     5      | 178   78    18     | 3     9     6                    |  H    GH           | 8     6     1      | 39    2     39     | 4     7     5                    |                    | -------------------+--------------------+------------------- 79    38    6      | 2     3789  5      | 78    1     4 FE                 |                    | GH 5     2     4      | 378   1     38     | 789   6     389                    |  G                 | H 179   138   39     | 4     3789  6      | 2     5     38 BE    A     AB     |                    | -------------------+--------------------+------------------- 4     7     8      | 5     6     2      | 19    3     19                    |                    | 6     13    2      | 139   4     139    | 5     8     7       BA           |                    | 19    5     39     | 138   38    7      | 6     4     2 AB          BA     |   C   CD           | from (9,5) and (2,5) follows that D excludes H from (4,7) and (4,1) follows that G excludes F from (6,1) follows that E excludes B from the three above follows that D escludes B from (9,5) and (9,3) follows that C excludes B therefore B is false and A is true Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Jul 06, 2005 11:50 pm    Post subject: Very hard - pure multi-colouring solution I've checked my new multi-colouring solution and (I think) it looks OK. Here are the colour maps for the possibles involved Code: Colouring for digit: 1                         -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   - -   -   a   -   -   -   -   -   b -   -   -   -   -   -   -   -   - -   -   b   -   -   -   -   -   a -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   -                          Colouring for digit: 2                         -   -   -   -   -   -   a   b   - -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   - -   -   -   -   g   -   -   a   - c   -   -   -   -   -   d   -   - -   e   -   -   h   -   -   -   - -   -   -   -   -   -   -   -   - e   f   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   -                          Colouring for digit: 3                         -   -   -   -   -   -   -   -   - -   -   -   a   -   b   -   -   - -   -   -   -   -   -   -   -   - -   -   c   -   d   -   -   -   - -   -   -   -   -   a   i   -   - -   f   -   -   -   -   j   -   - -   -   -   -   -   -   -   -   - -   e   f   -   -   -   -   -   - -   -   -   b   a   -   -   -   -                          Colouring for digit: 4                         -   -   -   -   -   b   *   -   c -   -   -   -   -   a   b   -   - -   -   *   -   -   -   -   -   - -   *   -   -   -   -   -   -   - -   -   -   -   -   -   c   -   d -   -   -   *   -   -   -   -   - *   -   -   -   -   -   -   -   - -   -   -   -   *   -   -   -   - -   -   -   -   -   -   -   *   -                          Colouring for digit: 5                         -   -   -   -   -   -   -   a   b -   -   -   -   *   -   -   -   - *   -   -   -   -   -   -   -   - -   -   -   -   -   *   -   -   - -   -   c   -   -   -   -   -   d -   -   d   -   -   -   -   b   * -   -   -   *   -   -   -   -   - -   -   -   -   -   -   *   -   - -   *   -   -   -   -   -   -   -                          Colouring for digit: 8                         -   -   -   -   -   -   -   -   - -   -   -   d   -   -   -   -   - -   -   -   -   -   -   -   -   - e   -   -   -   -   -   -   -   - f   -   -   -   -   -   -   -   - -   -   -   -   a   -   b   -   - -   -   -   -   -   -   -   -   - -   -   -   -   -   -   -   -   - -   -   -   c   d   -   -   -   - The chain of implication is as follows: Code: analyse          possible 5    colour d implies:       cell {5,9}    possible 4    colour c implies:       cell {6,3}    possible 1    colour a analyse          possible 4    colour c implies:       cell {5,7}    possible 3    colour j analyse          possible 1    colour a implies:       cell {4,3}    possible 3    colour d analyse          possible 3    colour j implies:       cell {6,7}    possible 8    colour a analyse          possible 3    colour d implies:       cell {4,5}    possible 2    colour h analyse          possible 8    colour a conflict:       cell {6,5}    possible 2    colours: h/g analyse          possible 2    colour h conflict:       cell {6,5}    possible 8    colours: a/b multicolour:       possible 5    colour d    conflicts= 2 The first 2 lines say that the assumption "possible 5 has colour d" implies that cell {5,9} can't have colour d in possible 4 and therefore must have colour c in possible 4. The algorithm then iterates until cycles, exhausts or conflicts. So by reasoning about colours alone (the algorithm doesn't even look at the possibles) we show that the assumption 5d (i.e. possible 5 has colour d) leads to conflicting colour implications in cells {6,5} for possibles 2 and 8. So 5d must be false and 5c true, which enables us to fix {5,3}=5. [Hopefully, final edit] Running the algorithm two more times shows that conflict in {8,2} 4c=false, 4d=true fix {5,9}=4 conflict in {4,3} 4b=false, 4a=true fix {2,6}=4 This is sufficient to solve Nick70's (excellent) puzzle. Please let me know (as if I need to ask) if there are any errors in this new approach. AMcK Last edited by AMcK on Thu Jul 07, 2005 12:33 pm; edited 7 times in total Back to top Simes Joined: 08 Apr 2005 Posts: 71 : Location: North Yorkshire, UK Items Posted: Thu Jul 07, 2005 6:58 am    Post subject: Nick70 wrote: Simes wrote: I've now limited it to simple chains of two-candidate cells - and it no longer finds a solution to the above problems... either of them. Either of them? I don't think that's right. The chain is quite obvious in the first one: Sorry, I was unclear - I didn't say it didn't find the chain, just that it doesn't solve the puzzles. (5, 3) = 5 is found OK. _________________ Simes www.sadmansoftware.com/sudoku Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Thu Jul 07, 2005 8:06 am    Post subject: Simes wrote: Sorry, I was unclear - I didn't say it didn't find the chain, just that it doesn't solve the puzzles. (5, 3) = 5 is found OK. Ah, that's fair enough. So this proves that advanced coloring + aliasing is more poweful than simple forcing chains. Code: 3     1     9      | 6     7     48     | 248   25    458                       |                    | D     CD     C    6     7     2      | 38    5     348    | 48    1     9                         |                    |                    5     8     4      | 2     9     1      | 7     6     3                         |                    |                    -------------------+--------------------+------------------- 278   4     137    | 9     238   5      | 6     27    18     EB         CE     |       EF           |       DC    DC    28    6     5      | 7     1     38     | 2348  9     48    BA                 |                    | A                  9     23    17     | 4     238   6      | 238   57    15          EF    DC     |       F            |       CD    CD    -------------------+--------------------+------------------- 4     9     8      | 5     6     2      | 1     3     7                         |                    |                    27    23    37     | 1     4     9      | 5     8     6      EF    FE    FE     |                    |                    1     5     6      | 38    38    7      | 9     4     2                         |                    |                                A excludes D because of (5,7) and (4,8) B excludes C because of (4,1) and (4,9) therefore CD=AB B excludes E because of (4,1) A=C excludes E because of (4,3) therefore E is false and F is true Back to top Gennadog Joined: 03 Jun 2005 Posts: 5 : Items Posted: Fri Jul 08, 2005 12:36 am    Post subject: Please explain... Nick70 wrote: Let's put some coloring over the pencilmarks: Code: 3     9     7      | 6     5     4      | 18    2     18                    |                    | 2     4     5      | 178   78    18     | 3     9     6                    |  H    GH           | 8     6     1      | 39    2     39     | 4     7     5                    |                    | -------------------+--------------------+------------------- 79    38    6      | 2     3789  5      | 78    1     4 FE                 |                    | GH 5     2     4      | 378   1     38     | 789   6     389                    |  G                 | H 179   138   39     | 4     3789  6      | 2     5     38 BE    A     AB     |                    | -------------------+--------------------+------------------- 4     7     8      | 5     6     2      | 19    3     19                    |                    | 6     13    2      | 139   4     139    | 5     8     7       BA           |                    | 19    5     39     | 138   38    7      | 6     4     2 AB          BA     |   C   CD           | I've managed to follow the 'simple colouring' stuff (even managed to use AMcK's examples to work out what was going on before he posted is explanation). However I can't see how to interpret the above, and therefore I'm not sure how to generate it and use it. For the "interested amateurs" that are following this interesting discussion, could you please explain it to me? Thanks Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron