Sudoku solver program, do it like a human!

[audioinstinct]

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:

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?

[SilverWarior]

In order to reduce the number of loops you are doing I recomend you start using sets for storing the posible candidates instead of arrays. Why? Becouse this way you alow yourself to the use of set operators. In your case you are interested in intersection of two sets as this returns you another set that conatins only those elements that are present in all sets. Yes you can find duplicate elements in multiple sets with a single command.

Check this quick code to see an example of how to do this:

type
  TCandidates = set of 1..9;

...

procedure TForm2.Button1Click(Sender: TObject);
var Candidates1, Candidates2, Candidates3: TCandidates;
    Duplicates: TCandidates;
    Candidate: Integer;
begin
  Candidates1 := [3,4,6,7];
  Candidates2 := [3,4,5,6,8];
  Candidates3 := [4,6];
  Memo1.Lines.Add('Intersection between Candidate1 and Candidates2');
  Duplicates := Candidates1 * Candidates2;
  for Candidate in Duplicates do
  begin
    Memo1.Lines.Add(IntToStr(Candidate));
  end;
  Memo1.Lines.Add('Intersection between Candidate1, Candidates2 and Candidates3');
  Duplicates := Candidates1 * Candidates2 * Candidates3;
  for Candidate in Duplicates do
  begin
    Memo1.Lines.Add(IntToStr(Candidate));
  end;
end;

I belive that using of sets would come quite usefull even in other approaches.

EDIT: In order to be able to use for in loops you need to use Delphi 2005 or newer or FPC 2.4.2 or newer.

EDIT2: And for all those of you who still might be using older Delphi version or other pascal compilers which doesn't support for in loops you first need to declare colection of all posible items in your set and then declare set of that colection like so:

type
  TCandidate = 1..9;
  TSetOfCandidates = set of TCandidate;

And then you need to loop through your colection of posible items and test for each on if it is present in your set like so:

procedure TForm3.Button1Click(Sender: TObject);
var Candidates: TSetOfCandidates;
    Candidate: TCandidate;
begin
  Candidates := [1,5,7];
  for Candidate := Low(Candidate) to High(Candidate) do
  begin
    if Candidate in Candidates then Memo1.Lines.Add(IntToStr(Candidate));
  end;
end;

Yes this is quite messy and performance ineficient especially if you are working with sets that can have large number of posible elements.
Just imagine you have to loop through a set that can conatin all 16 bit unsigned integer values (all 65536 of them) and you have to test for each to see if it is present in your desired set. Doing something like this could take ages.

[audioinstinct]

In order to reduce the number of loops you are doing I recomend you start using sets for storing the posible candidates instead of arrays. Why? Becouse this way you alow yourself to the use of set operators. In your case you are interested in intersection of two sets as this returns you another set that conatins only those elements that are present in all sets. Yes you can find duplicate elements in multiple sets with a single command.

Check this quick code to see an example of how to do this:

type
  TCandidates = set of 1..9;

...

procedure TForm2.Button1Click(Sender: TObject);
var Candidates1, Candidates2, Candidates3: TCandidates;
    Duplicates: TCandidates;
    Candidate: Integer;
begin
  Candidates1 := [3,4,6,7];
  Candidates2 := [3,4,5,6,8];
  Candidates3 := [4,6];
  Memo1.Lines.Add('Intersection between Candidate1 and Candidates2');
  Duplicates := Candidates1 * Candidates2;
  for Candidate in Duplicates do
  begin
    Memo1.Lines.Add(IntToStr(Candidate));
  end;
  Memo1.Lines.Add('Intersection between Candidate1, Candidates2 and Candidates3');
  Duplicates := Candidates1 * Candidates2 * Candidates3;
  for Candidate in Duplicates do
  begin
    Memo1.Lines.Add(IntToStr(Candidate));
  end;
end;

I belive that using of sets would come quite usefull even in other approaches.

EDIT: In order to be able to use for in loops you need to use Delphi 2005 or newer or FPC 2.4.2 or newer.

EDIT2: And for all those of you who still might be using older Delphi version or other pascal compilers which doesn't support for in loops you first need to declare colection of all posible items in your set and then declare set of that colection like so:

type
  TCandidate = 1..9;
  TSetOfCandidates = set of TCandidate;

And then you need to loop through your colection of posible items and test for each on if it is present in your set like so:

procedure TForm3.Button1Click(Sender: TObject);
var Candidates: TSetOfCandidates;
    Candidate: TCandidate;
begin
  Candidates := [1,5,7];
  for Candidate := Low(Candidate) to High(Candidate) do
  begin
    if Candidate in Candidates then Memo1.Lines.Add(IntToStr(Candidate));
  end;
end;

Yes this is quite messy and performance ineficient especially if you are working with sets that can have large number of posible elements.
Just imagine you have to loop through a set that can conatin all 16 bit unsigned integer values (all 65536 of them) and you have to test for each to see if it is present in your desired set. Doing something like this could take ages.

Thanks!! That's a very helpful idea. Indeed, when I'm going to rewrite the XY-wing procedure for example, this will be great. I had a seperate function just so I could calculate the common candidates of two cells, instead with sets this will become really simple, so yeah it definitely will come in handy later on too.

[SilverWarior]

@Phibermon @AirPas

Please keep the conversation about the Phibermons engine in seperate thread as that is off-topci for this one which is about making sudoku solver. Let us keep PGD forums organized shall we.
I can move all posts about your Phibermons engine to another thread. Just say where OK.

[phibermon]

Removed, it's not important I'll post about it when I'm ready to. AirPas please feel free to get in touch if you want some more details

[pitfiend]

Wandering the internet today, I found this http://www.sadmansoftware.com/sudoku...techniques.htm maybe you can found here some other approach to what you want to do.

[User137]

I also have made a sudoku solver, that you can possibly learn from
Lazarus source: https://www.dropbox.com/s/u27owmiqrb...u_src.zip?dl=0
Windows binary: https://www.dropbox.com/s/e95blmhhti...udoku.zip?dl=0

Actual solver is recursive, nothing human related. Quick and deep scan of all possible choices, it will also display all of them (normal "proper" sudokus are built with only 1 solution though). So if any sudoku has a solution, this will find it.

But there is a bit more that human-like when building a new sudoku from scratch. First it fills the table, with algorithm i don't remember in detail, but then it starts clearing it. Each cell can have calculated a value, of how many possible numbers it can have based on the numbers already set on board. If for example the row 1 already has number 4, then none of the other 8 cells on that row can have 4, the normal gamerule check. The generator keeps track of that for each cell, and also of what those numbers are. It goes through the whole grid and then finds which ones have lowest value, then randomly picks 1 of the winners and makes it blank. Repeat until number density (filled:empty ratio) reaches the wanted difficulty level, where closest to empty is hardest. When you think about it, a cell that has low value is easy for human to figure out, so it's quite balanced on the difficulty.

edit: Lowest value, not highest... i think