Page 2 of 3 FirstFirst 123 LastLast
Results 11 to 20 of 28

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

  1. #11
    Quote Originally Posted by SilverWarior View Post
    Hmm that is strange. I will however forward this information to site administrator.
    Thanks for that.

    Anyway, right now I'm thinking about a recursive approach to build the chain itself, a function would call itself for each candidate from 1-9 and build a chain of strong links which would return an array at the end which I could then easily check for possibilities. Well, it definitely sounds more simple than it is , but I think this will be most efficient way because with recursion I can ignore factors such as how many instances of the candidate exists and what's the relation of every single one of them to all the others which would just further complicate and add completely unnecessary loops into the procedure. Aaaand I need to step up my recursion capabilities anyway because I've never really written anything recursive harder than a factorial, lol.

  2. #12
    Ugh, this is a mess. I'm seriously considering that I'm rewriting the entire code in Object Pascal right now. I think I'm going to get used to that faster than I get around all the BS I encounter without it and I'm going to need it anyway when I want to create an interface for it. It will be million times easier to do the interface if I have to draw the properties of already existing objects, than to create new ones based on the tremendous amount of data, it would take eons to debug that.

  3. #13
    Quote Originally Posted by audioinstinct View Post
    It will be million times easier to do the interface if I have to draw the properties of already existing objects, than to create new ones based on the tremendous amount of data, it would take eons to debug that.
    I think that it will be easier to debug that is unless you don't create to big a mess with objects in the first place (yes you can do that).

    Anywhay if you will need any help with classes (class inheritence, method inheritance, property inheritance, getter and setter methods of properties, some data reusability with external classes and data forwarding) do let me know and I'll help as best as I can.

  4. #14
    Quote Originally Posted by SilverWarior View Post
    I think that it will be easier to debug that is unless you don't create to big a mess with objects in the first place (yes you can do that).

    Anywhay if you will need any help with classes (class inheritence, method inheritance, property inheritance, getter and setter methods of properties, some data reusability with external classes and data forwarding) do let me know and I'll help as best as I can.
    Well I've started to rewrite it, and now it fails at line 2. Weirdest error I've ever seen. Error code is 216 it says "program received signal sigsegv segmentation fault". I researched this and it seems to mean that my program is trying to refer to a memory address that it is not allowed to, but I have absolutely 0 idea why that is. Here's the code:

    Code:
    {$mode objfpc}
    
    {$m+}
    
    Program SudokuSolverObject;
    
    uses crt;
    
    
    type
    
     Cell=Class
    
      private
    
       Procedure Eliminate(cand:smallint);
    
       Procedure ReaarangeCandidates;
    
       Function BoxCalc(x,y:smallint):smallint;
    
    
    
      public
    
       x,y,box:smallint;
    
       boxnullx,boxnully:smallint;
    
       candidates: array[1..9] of smallint;
    
       num_of_candidates: smallint;
    
       solved:boolean;
    
       constructor create(a,b:smallint);
    
       procedure ClearRow(cand:smallint);
    
       procedure ClearColumn(cand:smallint);
    
       procedure ClearBox(cand:smallint);
    
       procedure Solve(cand:smallint);
    
     End;
    
    
    
    VAR
    
    Grid:array[1..9,1..9] of Cell;
    
    Completed:boolean;
    
    
    Constructor Cell.create(a,b:smallint);
    
    var
    
    i:smallint;
    
    Begin
    
     x:=a;
     y:=b;
    
     for i:=1 to 9 do
    
     begin
    
      candidates[i]:=i;
    
     end;
    
     box:=BoxCalc(a,b); //This function is defined before this in the code, I didn't include it because it's not related to the error at all
    
     num_of_candidates:=9;
    
     solved:=false;
    
    
     if box=1 then
    
     begin
    
      boxnullx:=1;
      boxnully:=1;
    
     end
     else
    
     if box=2 then
    
     begin
    
      boxnullx:=1;
      boxnully:=4;
    
     end
     else
    
     if box=3 then
    
     begin
    
      boxnullx:=1;
      boxnully:=7;
    
     end
     else
    
     if box=4 then
    
     begin
    
      boxnullx:=4;
      boxnully:=1;
    
     end
     else
    
     if box=5 then
    
     begin
    
      boxnullx:=4;
      boxnully:=4;
    
     end
     else
    
     if box=6 then
    
     begin
    
      boxnullx:=4;
      boxnully:=7;
    
     end
     else
    
     if box=7 then
    
     begin
    
      boxnullx:=7;
      boxnully:=1;
    
     end
     else
    
     if box=8 then
    
     begin
    
      boxnullx:=7;
      boxnully:=4;
    
     end
     else
    
     begin
    
      boxnullx:=7;
      boxnully:=7;
    
     end;
    
    End;
    
    Procedure Cell.Solve(cand:smallint);
    
    var
    
    i:smallint;
    
    Begin
    
     for i:=1 to 9 do
    
     begin
    
      candidates[i]:=0; 
    
    {This is the line that gives me the error, but all the other changes do it too, I've tried to switch the orders, any change
    
    to any variable of the classes after they were created throws me this stupid error. I've tried adding "self." before the assignments too, it didn't help.}
    
     end;
    
     num_of_candidates:=1;
     solved:=true;  
    
     candidates[1]:=cand;
    
    End;
    
    // I have all the other functions and procedures for the class defined as well, but they're not related to this problem.
    
    Procedure ReadGrid;
    
    var
    
    i,j:smallint;
    
    inp:string;
    
    act:smallint;
    
    err:smallint;
    
    Begin
    
     for i:=1 to 9 do
    
     begin
    
      Writeln('Please give me the clues of row # ',i, ' (0 means no clue)');
    
      Readln(inp);
    
      for j:=1 to 9 do
    
      begin
    
       val(inp[j],act,err);
    
       Grid[i,j].create(i,j); //This works just fine, there is no error yet
    
       if act<>0 then //"act" has a valid value, I double-checked it in debug mode, it works fine.
    
       begin
    
        Grid[i,j].Solve(act); //This is the point where the program enters the procedure which gives the error
    
       end;
    
      end;
    
     end;
    
    End;
    
    BEGIN
    
    Writeln('Welcome to Sudoku solver!');
    
    Readgrid;
    
    Readln;
    
    End.
    Edit: I've just tried to add a watch to certain points of the Grid before I get the error. It seems that the trouble is deeper than I thought. I get to the point where the class is created, and then it's all weird. If I set the watch like this: Grid[i,j].candidates then it says it is not a structure or union type, whatever the hell that means, and if I set the watch like this: Grid[i][j].candidates then, it tells me this "Can not access memory at 0xe". Wtf is going on here? P.S: I'm administrator on this computer, mine is the only user anyway, and it might be relevant, I'm using Windows 7 as OP system.

    Edit2: I've tried running this ridiculously easy program and it failed with the same BS so the problem is even deeper than I thought. Either I screw up the class definitions or it has to do something with the compiler...

    Code:
    {$mode objfpc}
    
    {$m+}
    
    Program wtf;
    
    
    type
    
    testclass=class
    
     private
    
      datx:integer;
    
     public
    
      dat1:integer;
    
      dat2:integer;
    
      constructor create(d1,d2,dx:integer);
    
     end;
    
    
    Constructor testclass.create(d1,d2,dx:integer);
    
    Begin
    
     datx:=dx;
     dat1:=d1;
     dat2:=d2;
    
    End;
    
    Var
    
    what:testclass;
    
    i,j,k:integer;
    
    Procedure Whatthef(a,b,c:integer);
    
    Begin
    
     what.create(a,b,c);
    
    End;
    
    BEGIN
    
    Writeln('Give me the first variable');
    
    Readln(i);
    
    Writeln('Give me the second');
    
    Readln(j);
    
    Writeln('Give me the third');
    
    Readln(k);
    
    Whatthef(i,j,k);
    
    Writeln('The first value was: ', what.dat1);
    
    Writeln('The second value was: ',what.dat2);
    
    Writeln('The third value was private');
    
    Readln;
    
    End.
    Last edited by audioinstinct; 04-01-2015 at 07:23 PM. Reason: addition

  5. #15
    The problem lies in the way you are creating your classes.
    Whenever you are creating classes you use next sytax:

    Code:
    //ClassRefereneVar is variable trhrough which you will be accessing your class
    //MyClass is the name of the class you are creating
    ClassReferenceVar := MyClass.Create;
    So in your case you need to call:

    Code:
    Grid[i,j] := Cell.create(i,j); //Right approach
    instead of:

    Code:
    Grid[i,j].create(i,j //Wrong approach
    EDIT: Pepole usually add T prefix to class names (TCell insted of just Cell) so that they can be quicly distinguished between normal variables in code.
    Last edited by SilverWarior; 04-01-2015 at 10:25 PM.

  6. #16
    Haha omg epic fail. Object Pascal 101, well thanks, I hate stupid mistakes like this, because I never guess the problem is something so simple. It runs fine now. I will continue to rewrite the original code with objects tomorrow, and see how it turns out. It's pretty weird though, pascal is always so strict with the syntax, and it allowed me to start the program like that. Basically this means the class it creates points to nothing, so it's no wonder it couldn't access the memory address, oh well, I guess I will get used to it, just takes some time.

  7. #17
    Quote Originally Posted by audioinstinct View Post
    Haha omg epic fail. Object Pascal 101, well thanks, I hate stupid mistakes like this, because I never guess the problem is something so simple.
    Never a mistake is stupid... unless you do the same twice. We learn from mistakes, to do improved versions... in more spectacular failures!

    Quote Originally Posted by audioinstinct View Post
    It's pretty weird though, pascal is always so strict with the syntax, and it allowed me to start the program like that.
    That's a compiler problem. Never used FPC and not sure if Delphi is able to catch that kind of errors at compile time, I think it warns about uninitialized variables.

    If you ever play with pointers, you are going to see weirder things for sure.

  8. #18
    Quote Originally Posted by pitfiend View Post
    That's a compiler problem. Never used FPC and not sure if Delphi is able to catch that kind of errors at compile time, I think it warns about uninitialized variables.
    You can make same mistake with Delphi. It also took me quite some time to learn that.

    Nof if I'm not mistake this is left in in Objective Pascal as backward compatibility to the verry first days of Objective Pascal when classes still didn't have capability to automatically initialize its own members (internal fields, variables, etc.).

    I think I once sow a code that actually makes use of this to delay the initialization of some class members in order to speed up the creation process of the class itself.

    But this is pactically not used nowadays becoouse you would usually want for your class to be the decendant of TObject class which provides you with some basic and comonly used functionality like class name property with which you can determine the class type at runtime without the use of extended RTL, then quckly creating of new instances of that particular class etc.

  9. #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.

  10. #20
    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:

    Code:
    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:

    Code:
    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:
    Code:
    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.
    Last edited by SilverWarior; 05-01-2015 at 05:38 PM.

Page 2 of 3 FirstFirst 123 LastLast

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
  •