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   

Pairwise methods

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Thu Sep 22, 2005 9:10 pm    Post subject: Pairwise methods Reply with quote

I've noticed several of the more obscure techniques available for solving sudoku seem to revolve around cells with only 2 candidates. The last 3 tests I've written for my solver all follow the same basic pattern for setup.

Recently I implemented tests for remote pairs, XY-wing, and uniqueness. (Technically the uniqueness test could be done in a triple format, but it'd be complicated.) I have not yet implemented XYZ-wing but plan to do it in a similar way. In each case I start out with an array C as big as the grid, and fill it with bit flags for the candidates. I do not fill the array for cells with less than or more than 2 candidates. For some techniques, I'll make the array twice as large and fill a second part of the array with the complete bit flag for dealing with 3+ candidates. I have 4 helper functions: countbits(), firstbit() (returns 0 for b=1, 1 for b=2, etc.; internally digit 0 is really a 1), CommonHouse(), and Intersection(). CommonHouse() returns -1 for nothing in common, 0 to size-1 for a common box, size to size*2-1 for column, and so on for row; it will find the first house in common, but can be sent another argument which tells it the last one found in case you want to look for more commonalities. The Intersection(p1,p2,cells) function takes two cell positions and fills the cells array with up to (size-2)*2 values which are indexes of cells sharing a common house with p1 and p2; it will return the number of intersecting cells found.

From there, the rest is fairly easy to figure out:

Remote pairs: Start with a double-size C array, and fill the 2nd half with 0's; this will mark cells that are already part of the chain. Search each index until you find a cell with only 2 candidates AB; this is easy because all the others in the array will be marked as 0. Add this cell index to a stack, and mark the point used. Then, look for another cell with the exact same 2 candidates AB which a house with this one. If none is found, pop the last one from the stack and continue searching from that point. If a cell is found, add it to the stack. If your stack reaches a length of 4 or more, and has an even number of cells, take the two endpoints and use Intersection() to find the cells. For each of those intersecting cells, remove the candidates AB.

XY-wing: Search the C array for the first pair XY, index i. Find a second pair j such that C[i]!=C[j] and C[i]&C[j]!=0, and i and j have a common house. Then find another pair k such that C[k]=C[i]^C[j], and k and j have a common house. If all these pairs have been found, find the digit d=firstbit(C[i]&C[k]), and use Intersection(i,k,cells) to find cells where eliminations may be done. Remove d from all such cells.

Uniqueness: I don't think this test has been described on these forums before, but it can be found here where it was first suggested by flagitious. In a nutshell this test looks for a locked pair with candidates AB within the same box, and the same col/row, and then finds 2 other cells AB and ABC in another box which form a rectangle with the first two. (C can be more than one digit.) All four cells must have AB as candidates. The uniqueness test says that with a valid sudoku grid, if the 4th cell was AB then you'd have multiple solutions. Since the assumption with a valid sudoku puzzle is that it has a unique solution, you can eliminate AB in the 4th cell. For the algorithm you need a double-sized C array, with half storing the pair bitflags and the other half storing all bitflags. Once you've found the first two cells i and j, and have found a matching cell k which all have the same values C[i]==C[j], C[i]==C[k], then you need to find the opposite corner c. If (C2[c]&C[i])==C[i], then you have a valid case for the uniqueness test, and you can eliminate both digits from i that are found in c.

(As I mentioned uniqueness can be done with triples too, but it's got to be so rare as to be the sudoku equivalent of finding bigfoot. You'd need 3 cells in a box and on the same col/row with all 3 candidates ABC, and then 3 more in another box laid out the same way, and likewise in a 3rd box. One and only one of those 9 cells would contain extra candidates, and that's where you'd do the elimination.)

XYZ-wing should be easy to implement in a manner similar to both XY-wing and the uniqueness test. With these four rare pairwise techniques, I'm wondering if there are others waiting to be discovered. Given how recent some techniques like fishy cycles, Bowman bingo, and even XY-wing itself are, there must be more--especially in this simple pairwise domain.
Back to top
View user's profile Send private message
duvidl

Joined: 26 Sep 2005
Posts: 1
:

Items
PostPosted: Mon Sep 26, 2005 3:14 am    Post subject: Pairwise methods Reply with quote

I'm brand new to this forum and also quite new to sudoku. Some of the terms and strategies as well are unfamiliar to me, so please bear with me if this idea is already known. However, I've been working on a C solver, which is pair-based. What I've found is that any matched tuple of any length (involving any number of cells), can ultimately be reduced to a matched pair of "pseudocells," each of which can point to other pseudocells, the lowest level of which point to two cells from a row, column or box. For example, if looking for a matched triple, suppose in a given row one cell can contain a 1|2, another a 1|2|3. Assume that the 1|2 is not part of a matched pair. The algorithm will search for cells having no more than three possible values (and never less than two). For each cell in the row, it looks for any other cell whose possible values, when and-ed with its own, produce a set of possibles numbering no greater than three. Since the above two cells satisfy that condition, a "pseudocell" is created, containing the two original cells from the row as members. The possible values for the pseudocell are the result of the and-ing, 1|2|3. Suppose there is another cell in the same row whose possibilities are 2|3, also not part of a matched pair. When and-ed with the 1|2, the result is also 1|2|3. A second pseudocell is created, with these two grid cells as members. Its possible values are also 1|2|3. Now, in the next iteration of the matching algorithm, it is the pseudocells that will be compared. I believe that if the possible values of any two of these pseudocells match exactly, that their member cells taken together, eliminating repeat references, will form a matched triple. The algorithm works, I believe, for tuples of any practical length. The algorithm will iterate until it ultimately can ascertain a matched n-size tuple based on a matched pair of derived pseudocells.

This method does not, in itself, solve all sudokus. I am currently looking at other strategies to combine with this to handle difficult cases. Thanks for your interest if you've read this far.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Sep 28, 2005 7:07 am    Post subject: Reply with quote

I'm not entirely sure I follow the pseudocell logic there, but it sounds an awful lot like basic subset solving for pairs, triples, etc. Subsets are of course highly useful, and their logic extends to X-wing and swordfish as well by applying the same principle in a different way.

The methods I'm referring to above are basically the sort you'd use when solving for subsets breaks down. Some, like remote pairs or uniqueness, are actually quite easy to test. XY-wing is a bit harder.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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