FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Logic techniques to solve sudokus larger than 9*9!          Sudoku Programmers Forum Index -> Exotic sudoku View previous topic :: View next topic   Author Message mcmanuf Joined: 17 Jun 2009 Posts: 3 : Items Posted: Wed Jun 17, 2009 2:41 pm    Post subject: Logic techniques to solve sudokus larger than 9*9! Hello. I have read multiple places that solving every sudoku can be done only by logic(hidden pairs,xy-wing etc.....). So we dont actually have to backtrack or guessing at any point. Can this rule be transferred for sudokus larger than 9*9? I am very curious as weather it can be done for a 16*16 for example or larger? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Wed Jun 17, 2009 5:55 pm    Post subject: Re: Logic techniques to solve sudokus larger than 9*9! mcmanuf wrote: I have read multiple places that solving every sudoku can be done only by logic(hidden pairs,xy-wing etc.....). So we dont actually have to backtrack or guessing at any point. Can this rule be transferred for sudokus larger than 9*9? I am very curious as whether it can be done for a 16*16 for example or larger? At least for the basic techiques the answer is yes. Just try using them yourself to solve a 16x16 and you'll see that they are equally applicable. Massive sudokus are not intrinsically harder, they're more difficult because of their sheer size. Regards, Mike Metcalf Back to top mcmanuf Joined: 17 Jun 2009 Posts: 3 : Items Posted: Wed Jun 17, 2009 10:14 pm    Post subject: I was actually trying to solve a 225*225 sudoku in hardware, so its a bit more intensive than the ordinary 9*9. Im doubting how much many of the ordinary logic algorithms i should implement and how much time I should use on developing a dedicated search algorithm. Will the logic deduction methods work on such large sudokus? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Thu Jun 18, 2009 5:03 am    Post subject: mcmanuf wrote: I was actually trying to solve a 225*225 sudoku in hardware, so its a bit more intensive than the ordinary 9*9. Im doubting how much many of the ordinary logic algorithms i should implement and how much time I should use on developing a dedicated search algorithm. Will the logic deduction methods work on such large sudokus? The problem is not to solve these massive puzzles, but to generate them in the first place. There has been extensive discussion of all this, for instance here and here. I suggest you look at this. Your 15^2x15^2 is simply an extension. Using software they could take a long time to solve because of their size. On the other hand, I've no idea how you're going to be able to generate a solution grid and then a reasonable puzzle with a unique solution in the first place: gasp. Regards, Mike Metcalf Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Thu Jun 18, 2009 6:41 am    Post subject: m_b_metcalf wrote: I've no idea how you're going to be able to generate a solution grid If it helps, for testing purposes, I can provide you with an isomorph of a canonical 225x225 solution grid. Regards, Mike Metcalf Back to top Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Thu Jun 18, 2009 7:01 am    Post subject: mcmanuf wrote: I have read that solving every sudoku can be done by logic (hidden pairs, xy-wing, etc.....). So we dont actually have to backtrack or guessing at any point. yes, as long as your definition of "logic" includes a lot of "etc" -- "chains" and "nets". mcmanuf wrote: Can this rule be transferred for sudokus larger than 9*9? I am very curious as weather it can be done for a 16*16 for example or larger? I was actually trying to solve a 225*225 sudoku. Will the logic deduction methods work on such large sudokus? yes, definitely. Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Fri Jun 19, 2009 6:12 pm    Post subject: Sudoku is a NP-complete problem, therefore, no matter what techniques you will be using, or if these techniques are considered as logical, when the sudoku board is large, the solution will require exponential time in the size of the board Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT Page 1 of 1   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