Results 1 to 10 of 28

Thread: Sudoku solver program, do it like a human!

Threaded View

Previous Post Previous Post   Next Post Next Post
  1. #19
    So before I write the code for this method I was thinking I'd ask for a bit of advice here. I don't want to rewrite it later, and my approach is pretty brutal, I get this feeling that there just must be a more efficient way...

    First, I will explain the concepts of Hidden Pairs, in Sudoku theory. This is a really simple one.

    It means that in a house(row, column or box) TWO candidates both have an incidence of two in that house, and both candidates reside in the same two cells. Currently, there may be other candidates too in these cells.

    What does this mean? Well, think about it... We know that both candidates must be somewhere inside that house and we know that each candidate can only occur once.

    Let's say we're in row #3, and we have the following situation:

    Candidates for position #4: 3 ,4, 6 ,7. Candidates for position # 7: 3 ,4,5,6,8. There is no other cell in this row that contains 3 or 6 as a candidate.

    Let's assume that the cell at position #4 is not a 3 or a 6. What does this mean? Well it means that both 3 and 6 would have only one possible place in this row, and that is at position #7. Since a cell can only have one value at a time, we can conclude that the cell at position #4 must be either a 3 or a 6. We can say the same about the cell at position #7.

    Now my question is, what do you think would be the most efficient way of finding these? What I have done certainly does work, but I am sure there is an easier or more efficient way. This is how it works right now:

    Code:
    Procedure Find_Hidden_Pairs;
    
    var
    
    i,j:smallint; // i always marks a row and j always marks a column in my code
    
    box:smallint; //boxes are numbered from 1-9 from left to right, up to down.
    
    count1,count2:smallint; //These are the variables for the possible candidates.
    
    candidate:smallint; //This will be used in a short loop to determine which candidates can be eliminated.
    
    TargetCell1,TargetCell2:Cell; //These will be the cells where an elimination will occur
    
    Begin
    
    TargetCell1:=Cell.create(1,1);
    TargetCell2:=Cell.create(1,1); //It doesn't matter that yet they have the same properties, I just want to initialize them.
    
    for count1:=1 to 9 do
    
    begin
    
     //Check for Rows
    
     for i:=1 to 9 do
    
     begin
    
      if ( Candidate_Count(count1,i,'row')=2 ) then 
    
      //Function Candidate_Count(candidate,housenumber:smallint;housetype:string):smallint returns how many candidates exist in a house.
    
      begin
    
       for count2:=1 to 9 do
    
       begin
    
        if (count1<>count2) and (Candidate_Count(count2,i,'row')=2) then //We don't want the program to find a 3 that pairs with 3...
    
        begin
    
         TargetCell1.x:=0;
         TargetCell2.x:=0;
    
          for j:=1 to 9 do
    
          begin
    
           if ( Candidate_Exists(i,j,count1) )and (Candidate_Exists(i,j,count2) ) then  
    
           begin
    
            {Function Candidate_Exists(row,column,candidate:smallint):boolean Checks if a cell has a possible candidate.
    
             This is necessary because it is possible that 2 candidates only have 2 instances but they reside in more than 2 cells. Such as in a row:
    
             position#1: 1,3 position#2: 5,3 position#3: 4,1. And the other cells don't have 3 or 1 as candidates, now obviously
             
             these don't form pairs}
    
            if TargetCell1.x=0 then
       
            begin
    
             TargetCell1.x:=i;
             TargetCell1.y:=j;
    
            end
    
            else
    
            begin
    
             TargetCell2.x:=i;
             TargetCell2.y:=j;
    
            end;
          end;
         end;
    
         if TargetCell2.x<>0 then
     
         begin
    
         for candidate:=1 to 9 do
    
         begin
    
          if (candidate<>count1) and (candidate<>count2) then
    
          begin
    
           Grid[TargetCell1.x,TargetCell1.y].Eliminate(candidate);
    
           Grid[TargetCell2.x,TargetCell2.y].Eliminate(candidate);
    
          end;
         end;
         end;
    
        end;
       end;
      end;
     end;
    
     //End of Row Checks
    
     {Here would come the column checks and box checks, I won't include because it follows the exact same procedure the box is only slightly   
    
     different... sooo....}
    
     //Check for Columns
    
     //Check for Boxes
    
     end;
    
      TargetCell1.done;
      TargetCell2.done;
    
    End;
    As you can see it is a mass amount of loops going on here, and it looks pretty ugly.

    Right now it starts with candidate 1 on each row and if it finds a row where it occurs twice it checks the row for another candidate from 1-9 that occurs twice and if they happen to form a pair then it eliminates the other possibilities, if they don't happen to form a pair, then it will search for another second candidate, and so on, and then it will go to the next row, and if it doesn't find any rows for that candidate then it goes to columns and boxes and then it starts all over again with a starting candidate for 2, and goes on until the pair 9,8 is checked for box 9.

    There should be a recursive way or I don't know, anything that won't cause it to go through 5 or 6 for loops just to check one row for 2 candidates. It seems way overkill. Anyone has an idea how can I make this more simple?
    Last edited by audioinstinct; 05-01-2015 at 01:52 PM.

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •