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,xywing 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,xywing 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, xywing, 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 NPcomplete 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 


