Advantages and disadvantages of some techniques

pirussas

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?

daj95376

PIsaacson · Posted: Tue Nov 03, 2009 9:50 pm Post subject:

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++.