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   

Easiest Concequences of Fishy Cycles Algorithm: 2-cycles

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

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Tue May 31, 2005 12:58 am    Post subject: Easiest Concequences of Fishy Cycles Algorithm: 2-cycles Reply with quote

I thought it might be usefull to list the special cases of the Fishy Cycles rule that I gave in a different post. I will follow the notation from that post:

http://www.setbb.com/phpbb/viewtopic.php?t=35&mforum=sudoku

A 2-cycle (or digon) is a pair of vertices connected by parallel edges. There are four situations in which digons can arise when one constructs the graph defined in my other post. Two of these situations give rise to well-known candidate removal rules, and two seem to give rise to new rules. I only give details for the "new" rules. My source for rules is the following web-page:

http://www.simes.clara.co.uk/programs/sudokutechniques.htm

In describing instances of the the digon rule the words row and column may always be interchanged. I use house to refer to a row, column or block. Here are the four special case rules:

1. The "X-wing". This arisies from vertices being rows and the parallel edges being columns. In this situation, the other candidates may be removed from the columns.

2. Rule "RC 2". (See my link to the list of rules.) This arises when the vertices are two blocks and the edges are two rows..

3. Rule "Row Vertices connected by block edges". This rule states that if there are two rows each containing exactly two candidate positions for n, and there are two blocks containing exactly one of the candidates from each row, then all other candidates may be cleared from the blocks.

Example:

Below I have drawn three horizontal blocks from a Sudoku array. a and A are the only candidates for n in the top row. b and B are the only candidates for n in the second row. In this situation all other candidates for n may be cleared from the first and third block.

a**|***|A**
*b*|***|*B*
***|***|***

4. Rule: "Row and block vertices connected by column edges". This rule states that if there is a row containing exactly two candidate positions for n and also a block containing exactly two candidate positions for n and there are two columns containing one candidate position from the row in one and the other candidate postions in the other column, then both columns may have all other candidate positions cleared for n.

Example:

Two vertical blocks from a Sudoku array:

***
*aA
***
----
*b*
***
**B

Here a and A are the only candidates for n in the second row. b and B are the only candidates for n in the lower block. Then all other candidates for n may be cleared from the second and third columns.

All four of these rules are special cases of the digon rule:

Digon Rule
Suppose there are two houses containing exactly two candidates for n. Suppose that there are two other houses each of which contains one of the candidates from each of the first two houses. (These new houses may contain other candidate positions as well.) Then all the other candidate positions for n may be cleared from the second pair of houses.

One can go on and classify all possible 3-cycle rules as well. (One will be the "swordfish" rule.) But one might as well implement the Fishy Cycles algorithm at that point. The reduction rules I have given above can be implemented more easily and I thought people might find them interesting.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
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