FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Nishio vs Supercolouring Goto page Previous  1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Aug 01, 2005 9:03 am    Post subject: angusj wrote: I'm probably in over my head here but ... aren't you assuming here that implies(y,z) is the same as excludes(-y,z) which of course may not be true? No. implies(y,z)=excludes(y,-z) There was a typo in the line you quote. It is still correct, but to be equivalent to the other one it should have been if excludes(x,-y) and excludes(y,-z) then excludes(x,-z). Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Mon Aug 01, 2005 9:21 am    Post subject: Nick70 wrote: There was a typo in the line you quote. OK. (I was editing my previous post while you were posting so I'm a bit out of sync.) Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Aug 01, 2005 10:19 am    Post subject: angusj wrote: (I was editing my previous post while you were posting so I'm a bit out of sync.) I see. No problem. angusj wrote: Anyhow, this is much harder to understand Is it? "If 2 is in r1c1, then it cannot be in r1c4. But r1c4 can only contain 2 and 6, so it must be 6. So 6 cannot be in r6c4". P.S. of course in the algorithm instead of if excludes(x,-y) and excludes(y,-z) then excludes(x,-z). one would do if excludes(x,y) and excludes(-y,z) then excludes(x,z). But note one thing: while the first excludex(x,y) is guaranteed to also have a implies(x,-y) equivalent (because there are some -y pencilmarks in the grid, as proven by the second excludes)), the last one isn't: there might not be any -z pencilmark on the grid. So we can prove something more than with implies() alone. So it isn't only more efficient, it's also more powerful. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Mon Aug 01, 2005 10:40 am    Post subject: Nick70 wrote: So it isn't only more efficient, it's also more powerful. I'll have to take your word for that, I'm still having trouble getting my head around it. Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Tue Aug 02, 2005 8:42 am    Post subject: Thanks AMcK for an excellent and clear description of the algorithm. I incorporated it into my logic-only solver in a couple of hours this morning and, after ironing out a couple of bugs (mosty associated with the "redundant conjugate colour" removal code) it now solves almost anything in sub-20ms. Nice one The "gotchas" I encountered were as follows: - don't forget to "fix" the excludes/conjugates/implies matrices if you remove a colour and replace it with an existing one (e.g if you replace v with u then make sure implies(u,w) is set to 'true' iff implies(v,w), and implies(w,u) is set to 'true' iff implies(w,v) - adding excludes(u,v) and excludes(v,u) once u and v have been identified as conjugates is an obvious point and seems to "help" step 7) significantly. - there are lots of opportunities for inserting iteration/pass loops. I ended up with the following (it might not be ideal but the whole algorithm takes about 1/100th of a second on my machine so I don't have much motivation to fix it right now ) int countReduced; assignColours(); do { createExclusions(); createConjugates(); determineImplications(); countReduced = reduceContradictions(); countRecoloured =determineCircular(); } while ((countReduced > 0) || (countRecoloured > 0)); (NB: "determineCircular" implements step 7) in the algorithm description") Ian. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 02, 2005 1:03 pm    Post subject: Nick70 wrote: You do the closure of implies[]: if implies(x,y) and implies(y,z) then implies(x,z). I just do the closure of excludes[]: if excludes(x,-y) and excludes(y,-z) then excludes(x,-z). [edited to fix a typo] I'm assuming that by "-x" you mean the conjugate colour of colour x. I can't do this in the new algorithm because I now colour non-conjugates which are involved in exclusions but don't have conjugates. So your excludes(x,-y) has to be generalised to excludes(x, p) and conjugated(y, p) This can't be closed if y doesn't have a conjugate. Of course, I need to check whether this adds any worthwhile power to the algorithm or gets used at all, but that's why I went for implies[] and the asymmetry it enables. Regards Andrew Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 02, 2005 1:13 pm    Post subject: Thanks Ian for the confirmation. droid42 wrote: The "gotchas" I encountered were as follows: Yes, I'm looking carefully at all of those just to check I haven't missed anything. I'm finding that after closure the implies[] matrix has indentical rows and columns for colours which are proved identical and I don't need to do any of that error-prone copying, which I always seem to program badly. I just mark the orphaned colour as unused so that it gets ignored. Although it eats up all the Nishio examples using logic alone. there are still a few very difficult puzzles that my version can't solve so I'm not finished yet. Regards Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Aug 02, 2005 1:50 pm    Post subject: AMcK wrote: I'm assuming that by "-x" you mean the conjugate colour of colour x. I can't do this in the new algorithm because I now colour non-conjugates which are involved in exclusions but don't have conjugates. It doesn't matter. You just do if excludes(x,y) and excludes(-y,z) then excludes(x,z) I'll write an article about it all when I'm finished. Currently it all works but I'm not satisfied with the performance, which is worse than forcing chains. To solve 16,000 hard problems, it takes more than 7 minutes to the coloring algorithm, while forcing chains just takes 5'30". Of course this is a moot point since the stubborn backtrack-only solver takes just 7 seconds. But I'm wondering if I can't improve the coloring algorithm. Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Tue Aug 02, 2005 5:27 pm    Post subject: AMcK wrote: Thanks Ian for the confirmation. droid42 wrote: The "gotchas" I encountered were as follows: Yes, I'm looking carefully at all of those just to check I haven't missed anything. I'm finding that after closure the implies[] matrix has indentical rows and columns for colours which are proved identical and I don't need to do any of that error-prone copying, which I always seem to program badly. I just mark the orphaned colour as unused so that it gets ignored. Although it eats up all the Nishio examples using logic alone. there are still a few very difficult puzzles that my version can't solve so I'm not finished yet. Regards Andrew Marking colours unused is exactly what I do too. Here's my "recolour" method... Code:         private void recolour(int u, int v, int value) {             // replace colour v with colour u                         for (int i_row = 0; i_row < size; i_row++) {                 for (int i_col = 0; i_col < size; i_col++) {                     if (grid[i_row][i_col].colour[value] == v) {                         grid[i_row][i_col].colour[value] = u;                     }                 }             }             // Update matrices to reflect replaced colour...             for (int w = 0; w < numColours; w++) {                 if ((u != v) && (v != w) && (u != w) && colourInUse[w]) {                     if (implies[v][w]) { implies[u][w] = true; }                     if (implies[w][v]) { implies[w][u] = true; }                     if (excludes[v][w]) { excludes[u][w] = true; }                     if (excludes[w][v]) { excludes[w][u] = true; }                     if (conjugate[v][w]) { conjugate[u][w] = true; }                     if (conjugate[w][v]) { conjugate[w][u] = true; }                 }             }             colourInUse[v] = false;         } (This is currently inefficient. I originally had a colourCell[c] array that basically associated cell objects containing colour 'c' with 'c' to avoid cycling through all the cells but, suspicion that this wasn't working correctly led me to remove it. I think it was a bug somewhere else so I might re-instate this) I've done some tweaks and timings and come up with the following results (specific to the example puzzle that you first posted): Using ONLY the super-colouring algorithm from the very start (i.e. switching off pointing pairs, box/line reduction, solitary/hidden pairs, X-Wing/Swordfish/etc.) With all the steps... - takes on average 62ms to run the whole algorithm - solves in 3 passes (11, 7 and 32 possibles reduced, 16, 17 and 4 recolours ) Omitting step 7)... - it still manages to solve the puzzle - takes around 62ms to run - solves in 3 passes (11, 7 and 32 possibles reduced respectively) Including step 7) but omitting the matrix updates... - still solves ok - solves in 3 passes (11, 7 and 32 reductions and 16,17,4 recolours ... again!) - takes around 62ms to run (With conventional reduction switched on, the super-colouring algorithm only needs 2 passes, 6/32reductions and around 10-15ms on top of 30ms to finish off the puzzle). What this tells me is... - solving this puzzle doesn't require step 7) but using it adds little/no time - updating the excludes/conjugate/implies appears to be redundant and doesn't particularly help to speed up or correct anything Of course, this is not to say that performing step 7) isn't essential for some puzzles but, as an experiment, I'm going to disable it for the time being until such time that I find a puzzle that needs it. I'll continue to optimise (in particular, reducing the number of full grid-scans as above). Amazing that this algorithm alone seems to solve most puzzles without the need to use any other traditional reductions (however, as already mentioned, used on its own from the very beginning is a little bit slower in total). Ian. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 02, 2005 6:36 pm    Post subject: droid42 wrote: Using ONLY the super-colouring algorithm from the very start I assume you allow the ocasional elimination of certainties in interlocking rows/columns/boxes. The algorithm struggles without that. I think Nick70 does it every time there's a change. Every time a possible goes certain a colour switches off and the 3-level matrix loops speed up. droid42 wrote: Amazing that this algorithm alone seems to solve most puzzles without the need to use any other traditional reductions Quite scary. I accidentally visualised the simplification that could eliminate yards of complex code, programmed it in one evening and was amazed at what it achieved. Andrew Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Wed Aug 03, 2005 8:00 am    Post subject: Some simple logging reveals that the vast majority of processing occurs in the u,v,w loop that builds and updates the "implies" matrix. I generated the following puzzle today... 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 . According to my solver, the least efficient route through this is as follows (abbreviated to save space): 1. Simple logic to solve 5 cells 2. Swordfish-5 (squirmbag?) for value 5 in rows 3,4,5,7,9 3. Super-colouring (2 passes removing 7 possibles 2{4,6} 2{4,9} 5{4,9} 9{4,9} 2{5,9} 5{5,9} 8{5,9}) 4. Simple logic to solve 2 cells 5. Swordfish-4 (jellyfish?) for value 5 in rows 2,3,4,6 6. Super-colouring (4 passes removing 39 possibles, too many to list here) 7. Simple logic to mop up the remaining 48 cells I've picked the slowest route as an extreme example of how many "tests" occur within the (for u (for v (for w)))) loop for the algorithm that builds the implies matrix. For the above puzzle and the slow route through it, step 3 results in slightly over 40 million tests and step 6 results in around 32 million. These steps take around 780ms in total. Ouch ... an extreme example indeed. As a comparison, the fastest (according to my still-under-development solver) route is something resembling simple->pointing pairs-> box/line -> solitary quad -> solitary 6-tuple (!!!) -> solitary 5-tuple -> simple -> hidden quad -> Swordfish -> Jellyfish(4) -> Super-colouring. In this route, super-colouring "only" needs to process a total of around 8.6 million tests to complete the puzzle. Being somewhat scared by the sheer volume of transactions I implented the obvious optimisation of maintaining 3 additional matrics to sit alongside "excludes", "conjugate" and "implies". These are simply inExcludes[numColours] such that (inExludes[c] == true) if the colour c appears anywhere in "excludes". The same for inConjugate and inImplies. We can then simply maintain these every time we set anything in the 3 main matrices to true. Once we get to the horrible (for u {for v {for w}}} loop when building the implies matrix, we change it to... Code:     for u {     if inExcludes[u] {         for v {             if inExcludes[v] {                 for w {                     if inConjugate[w] {                        if excludes[u][v] && conjugate[v][w] {                            set implies[u][w] to true } } } } } (yawn) } } } } } } ... etc. A similar concept can be applied to the subsequent tests that look for additional implications based on (u=v and v=>w) => (u=>w). Doing this reduces the number of tests performed for the first (slow) example to a total of 15.5 million tests for the first pass (compared to 40M) and 14 million for the second pass (compared to 32M) and a time reduction of around 50-60%. The fast route through this solution takes about 1/10th of the time of the above but still benefits from the above reduction by around 40% both in terms of time and steps. Not sure if this is already in other peoples' implementations but I was bored and my fingers needed some exercise Ian. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Aug 03, 2005 9:22 am    Post subject: droid42 wrote: Some simple logging reveals that the vast majority of processing occurs in the u,v,w loop that builds and updates the "implies" matrix. I generated the following puzzle today... ... super-colouring "only" needs to process a total of around 8.6 million tests to complete the puzzle. Nice puzzle ... rather a lot of spare 9's ... first time I've seen my colours go upper case. Starting from colour map Code: 5        2    4        ¦ 1a8a9a 1b3a6a 3b6b8b9b ¦ 1c3c   7        8c9c    7        8d9d 6        ¦ 5      1c3c   8e9e     ¦ 1e3e   4        2      1f8e9f   3    1g9g     ¦ 4      7      2        ¦ 5a8g9h 5b8h9i   6      -----------------------+------------------------+------------------------ 2a9j     1    3        ¦ 6      8      4a7a     ¦ 2b5b9k 5a9l     4b7b    2c8d     5e8e 2d5f7c   ¦ 3      9      1h4b7d   ¦ 2a6c   1i6d     4a7a    6        4    7f9m     ¦ 2      5      1i7c     ¦ 8k9n   1h8l9o   3      -----------------------+------------------------+------------------------ 1g2d3f9p 5f9e 1m2g5h9r ¦ 1n8m9s 4      6d8n9t   ¦ 7      3g6c8o9u 5i8p9v 3g9w     6    8        ¦ 7      2      5        ¦ 4      3f9x     1      4        7    1o5i9y   ¦ 1p8q9z 1q3b6b 3k6h8r9A ¦ 6d8s9B 2        5k8t9C the following 14 conflicts and reductions are made Code: Conflict: 3a implies 1f and 3a implies 1g but 1f excludes 1g Reduction: 3a=false in {1,5} before=36 after=6 Conflict: 3f implies 1f and 3f implies 1g but 1f excludes 1g Reduction: 3f=false in {8,8} before=39 after=9 Conflict: 4b implies 1f and 4b implies 1g but 1f excludes 1g Forcing: 4a=true {5,9} before=47 after=4 Conflict: 6b implies 1f and 6b implies 1g but 1f excludes 1g Reduction: 6b=false in {9,5} before=136 after=13 Conflict: 6c implies 1f and 6c implies 1g but 1f excludes 1g Forcing: 6d=true {9,7} before=689 after=6 Conflict: 6h implies 1f and 6h implies 1g but 1f excludes 1g Reduction: 6h=false in {9,6} before=3689 after=389 Conflict: 8g implies 1f and 8g implies 1g but 1f excludes 1g Reduction: 8g=false in {3,7} before=589 after=59 Conflict: 8l implies 1f and 8l implies 1g but 1f excludes 1g Forcing: 8k=true {6,7} before=89 after=8 Conflict: 9i implies 1f and 9i implies 1g but 1f excludes 1g Reduction: 9i=false in {3,8} before=589 after=58 Conflict: 9l implies 1f and 9l implies 1g but 1f excludes 1g Reduction: 9l=false in {4,8} before=59 after=5 Conflict: 9p implies 1f and 9p implies 1g but 1f excludes 1g Reduction: 9p=false in {7,1} before=129 after=12 Conflict: 9r implies 1f and 9r implies 1g but 1f excludes 1g Reduction: 9r=false in {7,3} before=1259 after=125 Conflict: 9v implies 1f and 9v implies 1g but 1f excludes 1g Reduction: 9v=false in {7,9} before=589 after=58 Conflict: 9C implies 1f and 9C implies 1g but 1f excludes 1g Reduction: 9C=false in {9,9} before=589 after=58 I put some countng in inner u,v,w loop of the transitive closure of implies[,] Code: If (u <> w) And (v <> w) And Implies(v, w) And (Not Implies(u, w)) Then Implies(u, w) = True This boolean seems to be tested 269,848 times but I spotted several no-brainers which would be bring this down a little. Total colouring time is 1.06 secs in VB6. Regards Andrew Back to top Gennadog Joined: 03 Jun 2005 Posts: 5 : Items Posted: Sat Aug 06, 2005 12:33 am    Post subject: Re: Nishio vs Supercolouring OK, its me plodding along about 10 steps behind everyone else but..... AMcK wrote: Supercolouring assigns the following colour map: Code: 1a4a8a   1b4b   *   4c5a   2a9a   2b9b   5b8b   *   * 4d8c   *   *   *   5c6a   4e6b   5d8d   *   * *   *   *   *   *   *   *   *   * *   2c6c   *   6d8e   1c2d6e8f   1d2e6f   *   *   * 4f6g   4g6h7a   *   *   6i7b   *   *   *   * *   2f7c   *   3a4h   2g7d   3b4i   *   *   * 1e6j   *   *   *   *   *   1f6k   *   * *   *   *   3c6l   1g6m9c   1h3d6n9d   1i6o   *   * *   1j6p   *   5e8g   5f8h   1k6q   *   *   * The fiendish reasoning leading to the first conflict is shown in detail and appears to be sound. 1b excludes 4b in {1,2} 2b excludes 9b in {1,6} 3b excludes 6l in {8,4} I can follow (and regenerate) the supercolour map. However how do you get the last quoted exclusion above. Why is it not 3c excluding 6l? Is this part of the 'colour renaming' you mention in step 3? (I note that my "simple colouring" display shows this cell as 3b, the same as {6,6}) Does this make a (substantive) difference? Thanks Don Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Sun Aug 07, 2005 8:50 am    Post subject: Re: Nishio vs Supercolouring Gennadog wrote: OK, its me plodding along about 10 steps behind everyone else but..... ... I can follow (and regenerate) the supercolour map. However how do you get the last quoted exclusion above. .... Does this make a (substantive) difference? Don, I've edited the original post to bring it up to date with the latest supercolourer transcript showing an identity and a conflict. I still don't guarantee it's bug free but it's the general principles that matter. I may update it again to make it more usable. I'm also 10 steps behind everybody else ... I've only now accepted n-swordfish as a necessary companion to supercolouring. Regards Andrew Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Sun Aug 07, 2005 9:07 am    Post subject: Re: Nishio vs Supercolouring AMcK wrote: I'm also 10 steps behind everybody else ... Who's out in front then if we're all behind? I guess that leaves Nick70 there on his lonesome. On a related note - I do like advanced/super colourings from a theoretical perspective. However, I really can't see how it helps the average Joe Bloggs who wants to solve a puzzle visually (ie without the aid of a computer). 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, 3  Next Page 2 of 3   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