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   

Advantages and disadvantages of some techniques

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

Joined: 14 Sep 2009
Posts: 11
:

Items
PostPosted: Tue Nov 03, 2009 1:16 pm    Post subject: Advantages and disadvantages of some techniques Reply with quote

I intend to solve a sudoku nxn and i am looking for advantages and disadvantages of some techniques such as:

Naked Single / Singleton / Sole Candidate
Hidden Single / Unique Candidate
Block and Column / Row Interactions
Block / Block Interactions
Naked Pair, Triplet, Quad / Naked Subset / Disjoint Subset
Hidden Pair, Triplet, Quad / Hidden Subset / Unique Subset
X-Wing
Swordfish
XY-Wing
XYZ-Wing
Colouring
Remote Pairs
XY-Chain
Forcing Chains
Trial and Error

Someone can me indicate the advantages and / or disadvantages?
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Tue Nov 03, 2009 6:10 pm    Post subject: Re: Advantages and disadvantages of some techniques Reply with quote

pirussas wrote:
I intend to solve a sudoku nxn and i am looking for advantages and disadvantages of some techniques such as:

Naked Single / Singleton / Sole Candidate
Hidden Single / Unique Candidate
Block and Column / Row Interactions
Block / Block Interactions
Naked Pair, Triplet, Quad / Naked Subset / Disjoint Subset
Hidden Pair, Triplet, Quad / Hidden Subset / Unique Subset
X-Wing
Swordfish
XY-Wing
XYZ-Wing
Colouring
Remote Pairs
XY-Chain
Forcing Chains
Trial and Error

Someone can me indicate the advantages and / or disadvantages?

Simple Sudoku is a solver for 9x9 puzzles. It uses the most common techniques to solve puzzles.

Code:
===== ===== ===== ===== Simple Sudoku Hierarchy

- Naked  Single
- Hidden Single
- Naked  Pair
- Locked Candidate 1
- Locked Candidate 2
- Naked  Triple
- Naked  Quad
- Hidden Pair
- X-Wing
- Swordfish
- Colors
- Multi-Colors
- Hidden Triple
- XY-Wing
- Hidden Quad

You will need to include a backtracking (Trial & Error) feature to your solver for any puzzles that can't be solved using these techniques. Good Luck!

Simple Sudoku is presented in the Software section of this forum ... along with many other solvers.
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Nov 03, 2009 9:50 pm    Post subject: Reply with quote

The problem with coding a sudoku solver is that some techniques are subsumed by others, so unless you just gotta have an exhaustive list or have lots of time on your hands, you probably want to code fewer but more powerful methods.

For example, a really complete fishing algorithm is incredibly difficult to program because of the sheer number of fish varients. But a templating algorithm is faster, the most powerful single digit analysis technique known, much easier to code, and is usually used within fishing algorithms just to determine whether or not there's anything available to catch. Of course, with templating, you can't notate what type of fish you caught, you can only say that you used templates a, b, c, d... and those produced this set of eliminations and this set of assignments.

Some other examples... You have indicated 5 different singles techniques whereas I have a single method that detects and assigns all naked or hidden singles in one pass. All my block/line interactions are again contained in a single method. All subsets size 2-4 naked/hidden plus all simple fish (x-wing, swordfish, jellyfish ...) are contained in a single method. X-coloring, 3d-medusa and GEM are all contained in a single coloring method. All URs are contained in a single method.

Of course, I'm on about my 5th or 6th generation solver with the accumulated knowledge of all the prior implementations and the insight gained from looking at overlap and how to combine things into simpler algorithms, so it's easy for me to tell you to do this or that to make things easier.

One thing I can pass on is that you really need to design some structures correctly in order to make everything easier to code. The main influential structure is your grid object - the one that contains givens and candidates remaining to be solved. This structure really needs to contain all 4 space views (rc, rn, cn, bn). You should not start until you fully understand the relationship of 729 nrc candidates and the 324 constraints of Sudoku, and how that relates to the 4 different grid space views. Plus I'd really recommend using STL bitsets and maps if you're going to code in C++.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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