|
View previous topic :: View next topic |
Author |
Message |
| PTP
| Joined: 31 Jul 2006 | Posts: 1 | : | | Items |
|
Posted: Mon Jul 31, 2006 2:23 pm Post subject: Need help programming advanced techniques |
|
|
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". |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Jul 31, 2006 4:08 pm Post subject: |
|
|
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 |
|
Back to top |
|
|
| maarten
| Joined: 16 Jun 2006 | Posts: 7 | : | Location: The Netherlands | Items |
|
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. |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Aug 02, 2006 11:46 am Post subject: |
|
|
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 |
|
Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|