Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Logic techniques to solve sudokus larger than 9*9!

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
mcmanuf

Joined: 17 Jun 2009
Posts: 3
:

Items
PostPosted: Wed Jun 17, 2009 2:41 pm    Post subject: Logic techniques to solve sudokus larger than 9*9! Reply with quote

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
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Wed Jun 17, 2009 5:55 pm    Post subject: Re: Logic techniques to solve sudokus larger than 9*9! Reply with quote

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
View user's profile Send private message
mcmanuf

Joined: 17 Jun 2009
Posts: 3
:

Items
PostPosted: Wed Jun 17, 2009 10:14 pm    Post subject: Reply with quote

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
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Jun 18, 2009 5:03 am    Post subject: Reply with quote

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
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Jun 18, 2009 6:41 am    Post subject: Reply with quote

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
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Thu Jun 18, 2009 7:01 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Fri Jun 19, 2009 6:12 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron