FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Some nice, very hard, Sudoku's Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Feb 20, 2006 3:11 pm    Post subject: Hi Henk, Ididn't fine a simple elegant solution however your seconfd puzzle has these interesting consecutive steps: Code: *-----------------------------------------------------------------* | 248    38     1     | 2349   35     6     | 2458   489    7     | | 247    5      234   | 8      1      23479 | 2469   49     2469  | | 2478   6      9     | 247    57     247   | 2458   3      1     | |---------------------+---------------------+---------------------| | 6      9      24    | 237    378    1     | 2478   5      2348  | | 128    38     23    | 5      4      279   | 1279   6      29    | | 14     7      5     | 239    6      2389  | 12489  489    23489 | |---------------------+---------------------+---------------------| | 9      1     *67    |*467    78     478   | 3      2      5     | | 3      4      8     | 1      2      5     | 69     7      69    | | 5      2     *67    |*367    9      37    | 48     1      48    | *-----------------------------------------------------------------* Eliminating 7 from r7c4 (Candidates 67 in r7c3,r9c3,r7c4 & r9c4 form a type-4 unique quadrangle) Eliminating 7 from r9c4 (Candidates 67 in r7c3,r9c3,r7c4 & r9c4 form a type-4 unique quadrangle) *-----------------------------------------------------------------* | 248    38     1     | 2349   35     6     | 2458   489    7     | | 247    5      234   | 8      1      23479 |*2469   49    *2469  | | 2478   6      9     | 247    57     247   | 2458   3      1     | |---------------------+---------------------+---------------------| | 6      9      24    | 237    378    1     | 2478   5      2348  | | 128    38     23    | 5      4      279   | 1279   6      29    | | 14     7      5     | 239    6      2389  | 12489  489    23489 | |---------------------+---------------------+---------------------| | 9      1      67    | 46     78     478   | 3      2      5     | | 3      4      8     | 1      2      5     |*69     7     *69    | | 5      2      67    | 36     9      37    | 48     1      48    | *-----------------------------------------------------------------* Eliminating 9 from r2c7 (Candidates 69 in r8c7,r8c9,r2c7 & r2c9 form a type-4 unique quadrangle) Eliminating 9 from r2c9 (Candidates 69 in r8c7,r8c9,r2c7 & r2c9 form a type-4 unique quadrangle) Tarek Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Tue Feb 21, 2006 11:43 am    Post subject: Quote: Ididn't fine a simple elegant solution however your seconfd puzzle has these interesting consecutive steps: My solver uses these steps too... _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Sun Feb 26, 2006 9:45 pm    Post subject: Another one! I added a new technique to my generaters arsenal. I also improved the rating system a bit. This puzzle is rated 25776, which is lower then most of the others I posted, but I think it is very challanging anyway! Code:  . 7 . | . . . | . 1 .  . . . | . . . | . 3 8  3 . . | . 6 8 | 2 . . -------+-------+------  . . . | 6 . . | . . 3  . 1 9 | . 5 . | . . 6  . . . | 7 . . | 4 5 . -------+-------+------  . . 3 | 4 . 5 | 7 . .  1 . . | . 7 . | . . .  . 5 2 | . 9 . | . . .  245689 7      4568   | 2359   234    2349   | 569    1      459     24569  2469   1456   | 1259   124    12479  | 569    3      8       3      49     145    | 159    6      8      | 2      479    4579  ----------------------+----------------------+----------------------  24578  248    4578   | 6      1248   1249   | 189    2789   3       2478   1      9      | 238    5      234    | 8      278    6       268    2368   68     | 7      1238   1239   | 4      5      129    ----------------------+----------------------+----------------------  689    689    3      | 4      128    5      | 7      2689   129     1      4689   468    | 238    7      236    | 35689  24689  2459   4678   5      2      | 138    9      136    | 1368   468    14    _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 8:42 am    Post subject: Re: Another one! I have posted these before on the Players' Forum, but I figured I could add them here, too. I have modestly (*cough*) dubbed these "Vidar's Monster 1, 2 and 3". I believe #3 is the hardest of the bunch. (But I have a few more for the list lined up for testing, which might beat it.) Code: Vidar's Monster #1 +-------+-------+-------+ | . . 5 | 8 3 . | . . . | | . 1 . | . . . | . 9 8 | | . . 8 | 9 . . | . 4 . | +-------+-------+-------+ | . . 9 | . 8 . | 6 . . | | 7 . . | . . 4 | . . . | | . 8 . | 1 . . | . 7 5 | +-------+-------+-------+ | 5 . . | . . . | 2 . . | | . . 3 | . 7 . | . . . | | . . . | 6 2 . | . 5 1 | +-------+-------+-------+ ..583.....1.....98..89...4...9.8.6..7....4....8.1...755.....2....3.7.......62..51 Vidar's Monster #2 +-------+-------+-------+ | 8 . . | 4 . . | 6 . . | | . 3 . | . 6 . | . 7 . | | . . 7 | . . . | . . 2 | +-------+-------+-------+ | 1 . . | 6 . . | 3 . . | | . 7 . | . 4 . | . 8 . | | . . 3 | . . 9 | . . 6 | +-------+-------+-------+ | . . . | 8 . . | 4 . . | | . 9 . | . 5 . | . 2 . | | . . 1 | . . . | . . 5 | +-------+-------+-------+ 8..4..6...3..6..7...7.....21..6..3...7..4..8...3..9..6...8..4...9..5..2...1.....5 Vidar's Monster #3 +-------+-------+-------+ | 5 . . | 8 . . | 4 . . | | . 8 . | . 9 . | . 5 . | | . . 7 | . . 6 | . . 2 | +-------+-------+-------+ | . . 4 | . . 3 | . . 6 | | . 3 . | . . . | . . . | | 9 . . | 1 . . | . . . | +-------+-------+-------+ | . . . | 7 . . | 8 . . | | . 4 . | . 5 . | . 1 . | | . . 2 | . . 1 | . . 4 | +-------+-------+-------+ 5..8..4...8..9..5...7..6..2..4..3..6.3.......9..1........7..8...4..5..1...2..1..4 Henk: I'm curious what your rating system says about these. Is it possible to have it rate arbitrary puzzles online? Or is it possible to submit them to your database? (Feel free to do so.) Vidar Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 8:56 am    Post subject: vidarino: My solver could not give a trustable rating for these, because it needs guessing to solve them. Did you generate these yourself? What techniques are needed to solve these? My solver only supports these techniques: SingleInBox SingleInRow SingleInCol Naked Single PointingPair BoxLineReduction NakedPair NakedTriple NakedQuad HiddenPair HiddenTriple HiddenQuad RemotePair X-Wing SwordFish Color MultiColor XY-Wing XYZ-Wing Bug removal Unique Rectangle 1 Unique Rectangle 2 Unique Rectangle 3 Unique Rectangle 4 Comprehensive Chain Double implication Chain Triple implication Chain Trial & Error BTW: I can generate puzzles that needs T&E with my generater, they probably would be harder but thats no sport, is it? _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 9:06 am    Post subject: Henk wrote: BTW: I can generate puzzles that needs T&E with my generater, they probably would be harder but thats no sport, is it? Ah, but therein lies the challenge for me! I'm a firm believer in that *no* puzzle requires T&E, and that there is a logical way to solve them, even though that way can be extremely convoluted. And if I do find one that seems to require blind guessing, I will work on improving my solver. All of my "monsters" can be solved by my solver, but they all require the use of Forcing Chains and -Nets (which include Error Chains), so my current task is to improve the more logical (as in pattern-based) techniques. (I regard Forcing Chains and Nets as a limited form of guessing, so I'm not crazy about using them.) If you post a candidate list from where your solver needs to resort to guessing, I can see if my solver can provide a logical next step. Vidar Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 9:14 am    Post subject: vidarino: I realised that my post was a bit insulting, I didn't ment to be. What I was trying to say is that I think its not a sport for me to generate puzzles that I can't solve myself. Quote: I'm a firm believer in that *no* puzzle requires T&E Your right! There are no puzzles that cannot be solved without pure logic, there is always a logic solution (i believe this anyway..). I didn't inlcude forcing nets in my solver, because this is in most cases extremely difficult for humans. I allready crossed the line with triple implication chains I think. Pattern based techniques are better I think, but there are lots of patterns and it takes a lot off work to implement them all. A few days ago I read an article on how to use patterns that do not lead to a deduction to start a chain from. This way you can use chains, but do not have to 'brute force' every possible chain. This is hard for computers, but is a more human approach to chaining. _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 9:24 am    Post subject: Henk wrote: I realised that my post was a bit insulting, I didn't ment to be. What I was trying to say is that I think its not a sport for me to generate puzzles that I can't solve myself. I don't think you were, so no offense taken at all. Quote: I didn't inlcude forcing nets in my solver, because this is in most cases extremely difficult for humans. You got that right! I came across a puzzle that needed a Forcing Net of 39 steps (and a bunch of implications - didn't count them, sorry) to yield one elimination. Not exactly something for your average human. (I have later improved my solver, though, so almost no chain or net needs more than 10 steps any more.) The only reason I added Forcing Chains/Nets is to give the stuck user a feedback that there *is* a way to proceed, even though it's extremely hard to spot. And sometimes it's not too hard for the user to verify the deduction that the chain/net did (the so-called "backtest"), which usually makes one think "huh, good catch!" Vidar Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 9:29 am    Post subject: Quote: which usually makes one think "huh, good catch!" I have a pretty large user group now, and my solver can solve a lot of hard puzzles now, but I still get request to include more advanced techniques. Its just nice to see a computer program solve an extremely hard puzzle sometimes. Allthough most humans cannot do the same (i met a few that can, but most cannot), they learn a lot of it. Can I download your program somewhere? _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 9:50 am    Post subject: Henk wrote: Can I download your program somewhere? Unfortunately it's not ready for public consumption yet (having lots of hard-coded values and signs of generally lazy coding), but the plan is to clean it up and release it. It's just a command-line tool, by the way. Written under Linux, but it doesn't have any esoteric dependencies, so it should compile just about everywhere. I'm also going to stick under a web-based interface at some point, so it can be used to give hints or provide the next step on a user-supplied grid. Those are the plans, though. No deadlines or ETA yet, but I'm working actively on it. Vidar Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 11:45 am    Post subject: This is a good one! You can enter one value, and then your stuck allready.. Code:  . . . | . . . | 2 . .  1 . . | . . . | . 9 7  3 . . | 8 . . | 4 . . -------+-------+------  . . 6 | 7 9 . | . . .  . 9 4 | . . 6 | . . .  . 2 . | 5 4 . | . . . -------+-------+------  2 . . | . . . | 3 5 .  . . . | . 6 . | . . .  . . . | . 7 . | 8 . 1  456789  45678   5789    | 13469   135     134579  | 2       1368    3568     1       4568    258     | 2346    235     2345    | 56      9       7       3       567     2579    | 8       125     12579   | 4       16      56      -------------------------+-------------------------+-------------------------  58      1358    6       | 7       9       1238    | 15      12348   23458   578     9       4       | 123     1238    6       | 157     12378   2358     78      2       1378    | 5       4       138     | 1679    13678   3689    -------------------------+-------------------------+-------------------------  2       14678   1789    | 149     18      1489    | 3       5       469     45789   134578  135789  | 12349   6       1234589 | 79      247     249     4569    3456    359     | 2349    7       23459   | 8       246     1      EDIT: After improving this puzzle not hard at all! it needs one dual chain _________________ Generate and solve Sudoku puzzles with Into Sudoku! Last edited by Henk on Thu Mar 23, 2006 7:49 pm; edited 1 time in total Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 11:50 am    Post subject: Henk wrote: This is a good one! You can enter one value, and then your stuck allready.. Good one! A lot of eliminations, but hardly a single number to solve. Please try Vidar's Monster #2 for a similar treat. Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 11:53 am    Post subject: Quote: Please try Vidar's Monster #2 for a similar treat. I tried to do it manually because my solver doesn't beat it, and I haven't removed a single candidate yet _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Mon Feb 27, 2006 12:13 pm    Post subject: vidarino: After drawing every strong and weak link i removed a 7 from R6C5! Now i'm stuck again, but I will solve this puzzle eventually!.. _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Mon Feb 27, 2006 12:21 pm    Post subject: Henk wrote: vidarino: After drawing every strong and weak link i removed a 7 from R6C5! Now i'm stuck again, but I will solve this puzzle eventually!.. Not bad! To be honest, I couldn't get *anywhere* with it myself, and have more or less given up trying... But who knows, maybe I'll pick it up again one day. 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, 4, 5, 6, 7, 8  Next Page 6 of 8   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