Need help programming advanced techniques

PTP

I had the idea of creating a solver that works in a more general way. Instead of defining rows, columns, and blocks, I made groups that, in the case of the regular Su Doku, consist of 9 cells which must be unique. My idea was that by designing it this way, it would scale seamlessly to solve multiple Su Doku (such as the Samurai), and puzzles with irregular or extra regions.

I got the infrastructure (which automatically handles only candidates) set up, and I'm working on the other basic solving techniques, but I'm at a loss as to how to code X-wings and other advanced techniques. Any ideas?

Basically, what I need is a way to generalize those strategies without using the words "row", "column", or "block", and only using "group".

Ruud · Site Admin

I advice you to read about constraint subsets. Many techniques can be implemented using these, and you program never needs to know whether the constraints are rows, columns or boxes. Even diagonals and other variant constraints can be implemented this way.

Here is a link to a constraint subset topic: http://www.setbb.com/sudoku/viewtopic.php?t=505&mforum=sudoku

Ruud

maarten · Posted: Wed Aug 02, 2006 11:19 am Post subject:

X-Wing

for a candidate (V)
1) Take a group (A) with two possible cells (p1, p2) for candidate V
2) Find another group (B) which doesn't share cells with A and also has two possible cells (p3, p4) for value V
3) Find another group (C) which shares a cell with group A in cell p1 or p2, and shares a cell with group B in cell p3 or p4
4) Find another group (D) which shared a cell with group A in cell p1 or p2, and shares a cell with group B in cell p3 or p4
5) Remove (if any) candidate V in group C and D, exclusing positions p1, p2, p3 and p4

Do you mean something like this? I think you have to make functions/methods for your groups to do stuff like overlapping, counts, possible candidates, possible cells, and/or, etc.

Ruud · Site Admin

Yes, that's the general idea.

To make it a little more abstract:

Take any N groups (RBC) that do not intersect. Call this set A.
Take another N groups (RBC) that do not intersect. Call this set B.

Call the intersection of both sets AB.

The cells in set A outside AB are the A-surplus (AS).
The cells in set B outside AB are the B-surplus (BS).

For any digit V:

If all candidates in A are a member of AB, the candidates for V in BS can be removed.

If all candidates in B are a member of AB, the candidates for V in AS can be removed.

Now you have to translate this abstract finding to the user in something he/she can understand.

N can be 2, 3 or 4. Larger values only find complements of smaller patterns.
Line-box reductions can also be found using this method.

Ruud
_________________
Meet me at sudocue.net