FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Advanced coloring - very hard Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Fri Jul 08, 2005 12:58 am    Post subject: There are actually short forcing chains that can be used in second problem; not really simple, but doable. 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      (2,5)=8 => (9,5)=3 => (9,3)=9 => (9,1)=1 (2,5)=7 => (6,5)<>7 => (6,1)=7 => (9,1)=1 The important thing to note is the use of an inequality in the second chain. That's not the only chain, here is another one: (8,2)=3 => (4,2)=8 => (4,5)=3 => (5,6)=8 (8,2)=1 => (8,6)<>1 => (2,6)=1 => (5,6)=8 and finally: (4,5)=3 => (5,6)=8 => (2,6)=1 (4,2)=3 => (8,2)=1 => (8,6)<>1 => (2,6)=1 Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Fri Jul 08, 2005 11:38 pm    Post subject: Different results using advanced colouring I seem to be using a very similar technique to Nick70 with slightly different terminology but I'm not getting such good results. I call my multicolours e.g. 1a = possible 1, colour a whereas Nick 70 just gives them unique capital letters. I say 1a implies conjugate(3c) whereas Nick70 says A excludes B. But these differences are cosmetic - wse both try to build contradiction chains. If we take Nick70's starting point 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      He finds several contradictions and proves some colours true/false. I get Code: -   -   -   -   -   4b   2a   2b5a   4c5b -   -   -   3a8d   -   3b4a   4b   -   - -   -   -   -   -   -   -   -   - 7d8e   -   1a3c   -   2g3d   -   -   2a7a   1b 2c8f   -   -   -   -   3a   2d3b4c   -   4d -   2e3d   1b7a   -   2h8a   -   3a8b   5b7b   1a5a -   -   -   -   -   -   -   -   - 2e7c   2f3c   3d7d   -   -   -   -   -   - -   -   -   3b8c   3a8d   -   -   -   - Which doesn't seem to correspond - and I can't find any contradiction chains in my colour map but Nick70 can. I do hope I'm doing something wrong - because I'd like the technique to work AMcK Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Sat Jul 09, 2005 7:00 am    Post subject: Re: Different results using advanced colouring AMcK wrote: Which doesn't seem to correspond - and I can't find any contradiction chains in my colour map but Nick70 can. I do hope I'm doing something wrong - because I'd like the technique to work The "2a7a" you have in (4,8) cannot be right - it would mean 2 and 7 have to be in the cell at the same time, and since they are the only possibilities it would mean the problem is contradictory. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sun Jul 10, 2005 7:49 am    Post subject: Quote: The "2a7a" you have in (4,8) cannot be right - it would mean 2 and 7 have to be in the cell at the same time, and since they are the only possibilities it would mean the problem is contradictory. No, that's not what 2a7a means in the multi-colouring algorithm. Looking at your first "Very Hard" puzzle: Code: 3   1   .   6   .   .   .   .   . .   .   2   .   .   .   .   .   . .   8   .   .   9   .   7   6   . .   .   .   .   .   5   .   .   . .   6   .   .   1   .   .   9   . .   .   .   4   .   .   .   .   . .   9   8   .   6   .   .   3   . .   .   .   .   .   .   5   .   . .   .   .   .   .   7   .   4   2 Colour 2a means (1,7)=(4,8)=2. Colour 2b means (1,8)=2. 2a and 2b are mutually exclusive in the simple "single" colour analysis. Multicolours 2a7a in (4,8) means EITHER 2a OR 7a Because 2a and 7a sit in the same cell they are mutually exclusive in multi-colour analysis. In fact, we know that the solution is (4,8)=2 so we want to discover logically without guessing at least one of 2a=false, 2b=true, 7a=false, 7b=true. The implication chains (e.g. if 2a then because of {1,7} also 8b) are: 2a{1,7}8b{4,8}7b{1,9}5a{6,9}1b [OK] 2b{1,8}5b{1,9}8a{6,8}7a{4,9}1a{4,3}3d{4,5}2h{6,2}2f{8,3}7c{6,5}8f {6,7}3b{2,6}8c{5,7}2c{5,1}8i [OK] 7a{4,8}2b{6,3}1a{1,8}5b{4,3}3d{1,9}8a{4,5}2h{6,2}2f{8,3}7c{6,5}8f{6,7}3b{2,6}8c{5,7}2c{5,1}8i [OK] 7b{6,8}5a{1,8}2a{6,9}1b{1,7}8b [OK] I can't see any contradictions in the 2b and 7a chains - but I suspect that there's more information to be extracted. I'm building the full implication matrix and computing its transitive closure and inverse. One property I want to explore is where there are pairs of colours P, Q (in different possibles) such that P implies Q and Q implies P so that P must be identical with Q. There may be more contradictions but there may also be some more single colour reductions. AMcK Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Mon Aug 01, 2005 10:45 pm    Post subject: OK I've moved on a bit and I now understand your notation if not your reasoning. I'm looking at the puzzle Code: 3 1 . ¦ 6 . . ¦ . . . . . 2 ¦ . . . ¦ . . . . 8 . ¦ . 9 . ¦ 7 6 . ------+-------+------- . . . ¦ . . 5 ¦ . . . . 6 . ¦ . 1 . ¦ . 9 . . . . ¦ 4 . . ¦ . . . ------+-------+------- . 9 8 ¦ . 6 . ¦ . 3 . . . . ¦ . . . ¦ 5 . . . . . ¦ . . 7 ¦ . 4 2 starting from colour map Code: 3        1        9        ¦ 6        7        4a8a     ¦ 2a4b8b   2b5a     4c5b8c    6        7        2        ¦ 3a8d     5        3b4d8e   ¦ 4a8f     1        9        5        8        4        ¦ 2        9        1        ¦ 7        6        3        ---------------------------+----------------------------+---------------------------- 2c7a8g   4        1a3c7b   ¦ 9        2d3d8h   5        ¦ 6        2a7c     1b8i      2f8j     6        3e5c     ¦ 7        1        3a8k     ¦ 2g3g4c8l 9        4g5d8m    9        2h3h     1b5d7c   ¦ 4        2i3i8n   6        ¦ 2j3j8o   5b7e     1a5g      ---------------------------+----------------------------+---------------------------- 4        9        8        ¦ 5        6        2        ¦ 1        3        7        2h7f     2l3k     3h7a     ¦ 1        4        9        ¦ 5        8        6        1        5        6        ¦ 3b8p     3a8d     7        ¦ 9        4        2        I find more than enough contradictions and identities to solve the puzzle but don't seem to be able to prove as many colour identities as you do. I end up with Code: 3    1    9    ¦ 6    7    4    ¦ 2    2b5a 5b8c 6    7    2    ¦ 8    5    3    ¦ 4    1    9    5    8    4    ¦ 2    9    1    ¦ 7    6    3    ---------------+----------------+---------------- 8    4    1a7b ¦ 9    3    5    ¦ 6    2a7c 1    2    6    5    ¦ 7    1    8    ¦ 3    9    4    9    3    1b7c ¦ 4    2    6    ¦ 8    5b7e 1a5g ---------------+----------------+---------------- 4    9    8    ¦ 5    6    2    ¦ 1    3    7    7    2    3    ¦ 1    4    9    ¦ 5    8    6    1    5    6    ¦ 3    8    7    ¦ 9    4    2    which of course is trival to solve by elimination but that's not the point. So how did you reason the missing colour identities 1a, 1b, 5b, 5g, 7b, 7c in your model? Regards Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Aug 01, 2005 10:53 pm    Post subject: AMcK wrote: So how did you reason the missing colour identities 1a, 1b, 5b, 5g, 7b, 7c in your model? Are you sure you started from the same point as me? I only had 17 in r6c3, you have 157. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 02, 2005 9:23 am    Post subject: Well spotted - that brings 1a and 1b into play. But I'm not sure how you lose the 5 from r6c3 using conventional rules. It was there in your original Wed Jul 06, 2005 9:28 pm post and it's still in play in r5, r6, b3, b4 and b6. 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 No matter - there are more important lines to follow - a small number of very hard reference puzzles that I need to figure out how solve ... like "Supertough 1" Code: . 8 . ¦ 1 . . ¦ . . 2 . . . ¦ . . . ¦ 4 . . . 7 . ¦ 4 9 . ¦ . . . ------+-------+------- 4 . 9 ¦ . . . ¦ . . . . . . ¦ 3 . 5 ¦ . . . . . . ¦ . . . ¦ 2 . 6 ------+-------+------- . . . ¦ . 8 2 ¦ . 5 . . . 3 ¦ . . . ¦ . . . 1 . . ¦ . . 6 ¦ . 7 . Have you yet found a good use for the colour identities across different possibles. I suppose that they allow you to set them all true/false when you prove one of them but that's just an neat optimisation. Regards Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Aug 02, 2005 11:36 am    Post subject: AMcK wrote: Well spotted - that brings 1a and 1b into play. But I'm not sure how you lose the 5 from r6c3 using conventional rules. I had placed a 5 in r5c3 using a xy-wing. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 02, 2005 12:46 pm    Post subject: Nick70 wrote: I had placed a 5 in r5c3 using a xy-wing. Yes, that works, but you know that I'm trying to minimise and simplify the rules so anything beyond the first three commandments would be inadmissable. How do you get on with Supertough 1? Code: . 8 . ¦ 1 . . ¦ . . 2 . . . ¦ . . . ¦ 4 . . . 7 . ¦ 4 9 . ¦ . . . ------+-------+------- 4 . 9 ¦ . . . ¦ . . . . . . ¦ 3 . 5 ¦ . . . . . . ¦ . . . ¦ 2 . 6 ------+-------+------- . . . ¦ . 8 2 ¦ . 5 . . . 3 ¦ . . . ¦ . . . 1 . . ¦ . . 6 ¦ . 7 . I start with Code: 3a5a6a9a 8          4          ¦ 1      5b6b     3b7a   ¦ 3c5c7b9b 3d6c9c     2            3e5d6d9d 1a3f5e6e9e 1b5f6f     ¦ 2a6g   2b5g6h   3g7b8a ¦ 4        1c3h6i8b9f 1d3i5h7a8c9g 2c3j5i6j 7          1e2d5j6k   ¦ 4      9        3k8d   ¦ 1f3l5k8e 1g3m6l8f   1h3n5l8g      -------------------------------+------------------------+---------------------------------- 4        2e3o6m     9          ¦ 2b6n   2g6o7e   1      ¦ 3p5m7f8h 3q8i       3r5n7g8j      2d6p7h8k 1i2i6q     1j2j6r7i8l ¦ 3      2k4a6s7j 5      ¦ 1k7k9h   1l4b9i     1m7l9j        3s5o7m   1n3t5p     1o5q7n     ¦ 8      4b7o     9      ¦ 2        1p3u4a     6            -------------------------------+------------------------+---------------------------------- 6t7p9k   4          6u7q       ¦ 7r9l   8        2      ¦ 1q3v     5          1r3w          5r7r8l9m 5s9n       3          ¦ 5t7t9o 1        4      ¦ 6        2          8k9p          1        2l5u9q     2m5v8k     ¦ 5w9r   3        6      ¦ 8l9s     7          4            but can't get beyond Code: 3569   8      4      ¦ 1      56     37     ¦ 3579   369    2      3569   13569  156    ¦ 26     256    378    ¦ 4      13689  135789 2356   7      1256   ¦ 4      9      38     ¦ 1358   1368   1358    ---------------------+----------------------+---------------------- 4      236    9      ¦ 26     267    1      ¦ 3578   38     3578    2678   126    12678  ¦ 3      2467   5      ¦ 179    149    179    357    135    157    ¦ 8      47     9      ¦ 2      134    6      ---------------------+----------------------+---------------------- 679    4      67     ¦ 79     8      2      ¦ 13     5      13      5789   59     3      ¦ 79     1      4      ¦ 6      2      89      1      29     28     ¦ 5      3      6      ¦ 89     7      4      All I can find are Conflict: 5u implies 2l and 5u implies 2m but 2l excludes 2m Reduction: 5u=false in {9,2} before=259 after=29 Conflict: 5v implies 5t and 5v implies 5w but 5t excludes 5w Reduction: 5v=false in {9,3} before=258 after=28 Conflict: 9r implies 5t and 9r implies 5w but 5t excludes 5w Reduction: 9r=false in {9,4} before=59 after=5 Multi-identity: 1q=3w Multi-identity: 1r=3v Multi-identity: 2a=6n Multi-identity: 2b=6g Multi-identity: 8k=9s Multi-identity: 8l=9p All x-wing generalisations need lots of linkable conjugates to be inherited from standard rules but this puzzle just doesn't have enough. I'm still finding bugs and omissions but can either of you improve on this? Regards Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Aug 02, 2005 1:42 pm    Post subject: AMcK wrote: Yes, that works, but you know that I'm trying to minimise and simplify the rules so anything beyond the first three commandments would be inadmissable. It doesn't matter then--xy-wing is a special case of coloring anyway. But you'll have to use colors twice probably. AMcK wrote: How do you get on with Supertough 1? It cannot be solved with coloring or simple forcing chains. Back to top Nick67 Joined: 08 Sep 2005 Posts: 5 : Location: Sacramento, CA Items Posted: Fri Sep 09, 2005 8:18 pm    Post subject: Nick70, I tried to apply your coloring approach to this puzzle: Code:  *-----------*  |...|.7.|94.|  |.7.|.9.|..5|  |3..|..5|.7.|  |---+---+---|  |.87|4..|1..|  |463|...|...|  |...|..7|.8.|  |---+---+---|  |8..|7..|...|  |7..|...|.28|  |.5.|268|...|  *-----------* ...and with candidates: Code: {1256}  {12}    {1258}  {1368}  {7}     {1236}  {9}     {4}     {1236}  {126}   {7}     {1248}  {1368}  {9}     {12346} {2368}  {136}   {5}      {3}     {1249}  {12489} {168}   {1248}  {5}     {268}   {7}     {126}    {259}   {8}     {7}     {4}     {235}   {2369}  {1}     {3569}  {2369}  {4}     {6}     {3}     {1589}  {1258}  {129}   {257}   {59}    {279}    {1259}  {129}   {1259}  {3569}  {235}   {7}     {23456} {8}     {23469} {8}     {12349} {12469} {7}     {1345}  {1349}  {456}   {1569}  {1469}  {7}     {1349}  {1469}  {1359}  {1345}  {1349}  {456}   {2}     {8}      {19}    {5}     {149}   {2}     {6}     {8}     {347}   {139}   {13479} ... but I failed. Was it a bad idea to use the approach in this situation? Or did I just not do it right? Thanks for your help. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Fri Sep 09, 2005 9:11 pm    Post subject: Nick67 wrote: ... but I failed. Was it a bad idea to use the approach in this situation? Colouring cannot solve that problem, it's too hard. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sat Sep 10, 2005 10:29 am    Post subject: Nick70 wrote: Nick67 wrote: ... but I failed. Was it a bad idea to use the approach in this situation? Colouring cannot solve that problem, it's too hard. It seems to be a well-formed (although asymmetrical) puzzle with a unique solution Code: 2 1 5 ¦ 8 7 6 ¦ 9 4 3 6 7 8 ¦ 3 9 4 ¦ 2 1 5 3 4 9 ¦ 1 2 5 ¦ 8 7 6 ------+-------+------- 5 8 7 ¦ 4 3 2 ¦ 1 6 9 4 6 3 ¦ 9 8 1 ¦ 7 5 2 1 9 2 ¦ 6 5 7 ¦ 3 8 4 ------+-------+------- 8 2 6 ¦ 7 4 3 ¦ 5 9 1 7 3 4 ¦ 5 1 9 ¦ 6 2 8 9 5 1 ¦ 2 6 8 ¦ 4 3 7 It can be solved recursively with just 3 guesses out of 80 candidate sets - if you use standard rules to prune dead ends out of the search tree e.g. Code: AlphaBeta success: level = 0   {1,1}    possibles=1256    guess=2 AlphaBeta success: level = 1   {1,6}    possibles=1236    guess=6 AlphaBeta success: level = 2   {2,3}    possibles=12468    guess=8 MadOverlord's SuDoku Susser can solve it logically using Trebor's Tables and veracities and (theoretically at least) there's no reason why any other system like colouring based on implications and veracities can't do the same ... eventually. Colouring is of course merely a representation supporting a number of solution methods but none of those so far published seem to be able to solve this one logically. Ultracolouring (colouring using implication matrices and ver(ac)ities) can already solve it logically given just the first guess {1,1}=2 but I remain in the hunt to find its blind spot. Regards Andrew Back to top Interval Joined: 10 Sep 2005 Posts: 1 : Items Posted: Sat Sep 10, 2005 7:16 pm    Post subject: Solution I printed out the question and successfully did it by hand. I know that there is only one unique solution. I'm poking my own program to get it to solve this one completely. Before, it resolved only 93% of all elements; with the patch it should resolve all of them. It is not a brute force program. It's probably a painting program, but since I haven't actually read painting theory, I couldn't say for sure. Cheers! - Greg 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 Previous  1, 2 Page 2 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