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   

How to find Empty Rectangles

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

Joined: 08 Aug 2006
Posts: 6
:
Location: http://www.sd9981.com

Items
PostPosted: Tue Nov 21, 2006 12:13 pm    Post subject: How to find Empty Rectangles Reply with quote

How to find Empty Rectangles with computer?
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Nov 21, 2006 12:46 pm    Post subject: Reply with quote

foreach digit
- foreach row (R1) with only 2 candidates
- - foreach of these 2 candidates (C1) (name the other C2)
- - - foreach other box in the tower containing C1
- - - - if all candidates in this box which are not in the same column as C1 are located on a single row (R2)
- - - - - eliminate candidate from R2 in the same column as C2

do the same swapping columns and rows.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
MCondron

Joined: 17 Jul 2006
Posts: 35
:
Location: Houston, TX

Items
PostPosted: Sat Jan 06, 2007 7:19 pm    Post subject: Reply with quote

I do it slightly differently:
Code:

Repeat this for each digit, k:
- For each row with a conjugate pair in k which has its two cells in different boxes
  - For each of the two cells in the pair (call one A and the other B)
    - Scan over all cells in the same col as A looking for cells which are
        (1) in a different box than A and (2) have k eligible
        If one is found satisfying (1) and (2) call it V (a potential victim) and then:
          - Find the box where B's col intersects the V's line
          - For all cells in that box,
              Paint each with flags (one flag if the cell sees V, another for B)
          - For all cells in that box
              Test that every cell with k eligible must have either the V flag or B flag set
          - If all cells in that box meet those criteria, then k can be removed from V's candidate digit list.
And of course, repeat again interchanging rows and cols.

It's not really necessary to use two different flags when painting which cells in the box can see V or B. The important thing is that any cell which has k on its candidate digit list must be visible to either V or B.
Back to top
View user's profile Send private message
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