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   

Back to basics: a look at the intersections

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Oct 15, 2005 11:50 am    Post subject: Back to basics: a look at the intersections Reply with quote

With all the rocket science going on in this forum, I've taken a step back and looked at what's called Basic Techniques.

There are a lot of easy deductions that can be made from the intersections between rows and boxes, or columns and boxes. Only a little bookkeeping is required for this.

There are 27 intersections between rows and boxes. Each contains 3 cells in a horizontal line. There are also 27 intersections between columns and boxes, each with 3 cells in a vertical arrangement. Each cell belongs to exactly 1 horizontal segment and 1 vertical segment.

For a horizontal segment, there are 2 competing segments in the same row. Any digit placed in one of them excludes that digit in the other 2. There are also 2 competing segments in the box.

All box/row and box/column interactions can now be summed up in these few simple rules:

1. When a segment contains a digit, all 4 competing segments are disabled for that digit.
2. When all 3 cells in a segment are eliminated for a certain digit, the segment is disabled for that digit.
3. When 2 segments in a house are disabled for a digit, the 3rd segment requires that digit.
4. When a segment in a house requires a digit, the other segments in that house are disabled for that digit.

One more rule also takes care of hidden pairs and triples that lie within an intersection:

5. When the number of required digits equals the number of vacant cells in a segment, all other digit are disabled in that segment.

For bookkeeping, you only need the following data:

a. Pointers to the competing segments (static)
b. A matrix segment/digit with the status: enabled/disabled/required/contains
c. A count of the number of vacant cells in a segment
d. A count of the number of disabled competing segments per digit, separately for row/column and box.
e. Per cell, the horizontal and vertical segment that it belongs to. (static)
f. A count of the number of cells within each segment which are available for each digit.

The following basic techniques are all covered by segments:

a. Naked singles
b. Hidden singles
c. Box-row/column interactions (pointing pairs)
d. Box-box interactions
e. Naked pairs & triples within a section
f. Hidden pairs & triples within a section

I've been using this technique for quite some time in my solver, and it works perfectly. It also allows my solver to give very comprehensive feedback based on the deductions.

Another advantage is that it can give a different rating to naked/hidden pairs and triples within an intersection, which are much easier to spot than those scattered around a house.

And now: back to ultracoloring!

Ruud
(who wonders whether there are enough recognizable colors to implement ultracoloring)
Back to top
View user's profile Send private message Visit poster's website
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