Page 1 of 3 123 LastLast
Results 1 to 10 of 28

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

  1. #1

    Sudoku solver program, do it like a human!

    Hi everyone. I'm writing a sudoku solving program just for fun currently in free pascal. I don't use any objects, I'm really inexperienced with OOP, and due to the complexity of the problem, I'm skipping on them currently. Later I will get into it, but I'll start with easier programs, because this turns out to be a pretty hard one.

    This program doesn't use a Gauss elimination or brute forces it way through the Sudoku to find a pattern that matches the original clues, that's way too boring. I've decided that I'd rather implement very humanlike strategies in it. As I consider myself a decent Sudoku solver, I'm familiar with the concepts and strategies, and making a program doing them is quite challenging.

    Here's how it works:

    The 9x9 Grid is a Matrix, defined liked this in the program:

    Code:
    Type 
    
    Cell=Record
    
    Number_of_Candidates:smallint;
    Candidates:array[1..9] of smallint;
    Solved: Boolean;
    
    end;
    
    Var
    
    Grid:array[1..9,1..9] of Cell;
    Now here's how it works...

    First, the User inputs the clues line by line, and 0 means there is no clue in that particular cell, these are the cells the program will have to solve.

    I don't yet have any procedure or function which checks the validity of the Sudoku, I'm currently using Sudokus for tests that I know to be valid, and will later care about error checking.

    When the Grid is read, first the program calculates all the possible candidates for each cell, and then the fun begins.

    First, it checks for "Naked Singles". These are cells, that only have one possible candidate remaining, therefore, the solution of these are certain.
    After this, it checks for Hidden Singles. These are candidates that only exist in a house(row, column, or box) only once. Since every house must contain 1 of each, these must be solutions.

    Each time the program finds a solution, it reevaluates the candidates. This is necessary first to avoid errors, and secondly to not make it go through unnecessary processes.

    If no more naked or hidden singles can be found, it gets into the more advanced methods in this order: naked pairs, hidden pairs, pointing pairs, box-line reductions, X-wings, XY-wings.

    When I've made my first post, I was struggling with coding the XY-wing process, but it's already done, altough it's pretty much an overkill of a procedure that loops about 80000 times, but I didn't really find any way around this.

    Here's how an XY-wing works:

    You have a Hinge Cell, and two Wing Cells. Each Cell contain only two possible candidates, and these are related in a way like this: (a,b) (a,c) and (b,c). Which Cell is the Hinge and which the Wings are determined by the position of the Cells, because the Hinge can "see" both Wings, but the Wings can't see each other. This means that if the Hinge is (a,b), one Wing is (a,c) and the other is (b,c) then one of the wings must be a c. If the Hinge is a, then the first one must be a c, if it is a b, then the other must be a c. So then, from all the cells that both wings can see, c can be eliminated as a candidate. Now I don't know if there is a simple way to program that, my way is definitely not simple, but it works, and since the actual comparison and process is short, it still runs like a charm in less than a second despite the huge number of loops. Basically, I read the data of all the cells with two candidates into a two dimensional array and check for every possible combination of three of them whether they are valid or not, and if they do, then I call the elimination for the necessary cells.

    Now all this was pretty unrelated to my question, it was just to demonstrate you how my program works in short and what I'm currently capable of programming.

    Basically, I want to expand my program a bit because it still can't solve the hardest Sudokus. First I will add Triples, Quads, Simple Coluring, and XY-chains. Now I don't really have an issue with triples and quads, they work the same as pairs, it's only going to take longer to write it and that's all. Now with coluring and chains, that's a whole different story though because these are not so easily defined as the former methods, on a grid. There won't really be a "one way to go about it" for the program. It also must ignore possibilities meanwhile that might confuse the procedure and make it unnecessarily long. I have come across solvers that use these methods flawlessly so it's definitely not something impossible to code.

    I'll provide a link of these strategies, and I'm just going to ask the question, is it sensible for me to try and code these strategies without the use of objects? I feel like I can't sidestep them anymore unless I really want my program to loop for even more, and I don't want that. It's ugly already as it is, the reason I haven't pasted the entire code here is because you probably wouldn't understand it. Not because it's so complex but because it's so damn ugly with sometimes 10 or more consecutive "end;"s in some procedures, not to mention the 5 or even more "for loops" and the other things that would make any serious programmer cry themselves to sleep if they looked at my code

    Links:
    http://www.sudokuwiki.org/Singles_Chains
    http://www.sudokuwiki.org/XY_Chains

    Thanks, in advance, peace

  2. #2
    Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

    Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

    So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
    You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
    This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

    I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code

    Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
    As for the need to use objects to make this Sudoku solver I don't think they are required.

  3. #3
    Quote Originally Posted by SilverWarior View Post
    Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

    Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

    So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
    You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
    This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

    I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code

    Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
    As for the need to use objects to make this Sudoku solver I don't think they are required.
    Hey, thanks for the reply, now some of the things I have mentioned were probably not well explained in my post so I will try to elaborate.

    I really want to avoid the decision tree type of solution, that would be pretty much brute forcing through the puzzle. I'm pretty confident in that I could write that, there's no fun in that though, I like challenges to improve my scope as a hobby-programmer. Now with the extremely hard sudokus, even humans are left with very complicated methods. Some of these techniques include the 3D Medusa for example, or the Death Blossom, they're really hard to spot, let alone execute for an inexperienced sudoku solver. I don't plan on implementing those, because for 99.9% of the puzzles they are not needed.

    What I do want to do however is the easier methods. Pairs, X-wings and XY-wings are already completed in my program. You know what? I'm just going to paste the XY-wing method here... I will add some comments to the code so you don't have to go through everything in it, because it really is a big mess...

    Code:
    Type
    
     TCoord=array[1..2] of smallint; //There are lots of way I use this in the program
    
     TBox=array[1..3,1..3] of TCoord; 
    
    
     TCell=array[1..4] of smallint;
    
    {The first element of the array stores the row number of the cell. The second, the column number. 
    The third and the fourth are the two possible candidates in that cell }
    
     TArr=array[1..6] of smallint;
    
     TPointCell=^TCell;
    
     TPossibles=array[1..81] of TCell; 
     Cell=Record
    
      Solved:boolean;
      Candidates:array[1..9] of smallint;
      Num_of_Candidates:smallint;
    
     end;
    
    Var
    
     Grid:array[1..9,1..9] of Cell;
     Finished:integer; 
     {Why is this integer? I was getting unexplainable and weird errors when the function was boolean. 
     It stored weird stuff like "0x4ecwhatever" instead of "true" or "false" and somehow it works with integer... weird }
    
     Have_Result:Boolean;
    
    Function GetBox(x,y:smallint):TBox;  
    
    {What this function does is it returns a 3x3 size Box for every x,y coordinate, or if y is set to 0, then box #x. 
    Boxes are numbered 1-9 from left to right, up to bottom like this:
    
    1 2 3
    4 5 6
    7 8 9 }
    
    var
    
    i,j:smallint;
    
    Begin
    
     if y<>0 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        if x<=3 then GetBox[i,j][1]:=i
        else
        if x>6 then GetBox[i,j][1]:=i+6
        else
        GetBox[i,j][1]:=i+3;
    
    
        if y<=3 then GetBox[i,j][2]:=j
        else
        if y>6 then GetBox[i,j][2]:=j+6
        else
        GetBox[i,j][2]:=j+3;
    
       end;
    
      end;
    
     end
    
     else
    
     begin
    
     if x=1 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i;
        GetBox[i,j][2]:=j;
    
       end;
    
      end;
    
     end
    
     else
     if x=2 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i;
        GetBox[i,j][2]:=j+3;
    
       end;
    
      end;
    
     end
    
     else
     if x=3 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i;
        GetBox[i,j][2]:=j+6;
    
       end;
    
      end;
    
     end
    
     else
     if x=4 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+3;
        GetBox[i,j][2]:=j;
    
       end;
    
      end;
    
     end
    
     else
     if x=5 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+3;
        GetBox[i,j][2]:=j+3;
    
       end;
    
      end;
    
     end
    
     else
     if x=6 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+3;
        GetBox[i,j][2]:=j+6;
    
       end;
    
      end;
    
     end
    
     else
     if x=7 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+6;
        GetBox[i,j][2]:=j;
    
       end;
    
      end;
    
     end
    
     else
     if x=8 then
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+6;
        GetBox[i,j][2]:=j+3;
    
       end;
    
      end;
    
     end
    
     else
    
     begin
    
      for i:=1 to 3 do
    
      begin
    
       for j:=1 to 3 do
    
       begin
    
        GetBox[i,j][1]:=i+6;
        GetBox[i,j][2]:=j+6;
    
       end;
    
      end;
    
     end;
    
    end;
    
    End;
    
    
    Function BoxCalc(x,y:smallint):smallint; 
    
    {This was written early as a quick comparison. I could use the above function too, but I have written this before I realized the above would be necessary later, and I've already had a bunch of procedures using this one, so I've decided to keep it}
    
    Begin
    
     if (x<=3) and (y<=3) then                     BoxCalc:=1;
     if (x>3) and (x<=6) and (y<=3) then           BoxCalc:=2;
     if (x>6) and (y<=3) then                      BoxCalc:=3;
     if (x<=3) and (y>3) and (y<=6) then           BoxCalc:=4;
     if (x>3) and (x<=6) and (y>3) and (y<=6) then BoxCalc:=5;
     if (x>6) and (y>3) and (y<=6) then            BoxCalc:=6;
     if (x<=3) and (y>6) then                      BoxCalc:=7;
     if (x>3) and (x<=6) and (y>6) then            BoxCalc:=8;
     if (x>6) and (y>6) then                       BoxCalc:=9;
    
    end;
    
    
    Function Candidate_Exists(x,y,cand:smallint):boolean;
    
    {This is simple, it checks if a candidate is possible on an unsolved cell. It's very useful and pretty much necessary}
    
    var
    
    i,j:smallint;
    
    check:boolean;
    
    Begin
    
     check:=false;
    
     for i:=1 to Grid[x,y].Num_of_Candidates do
    
     begin
    
      if Grid[x,y].Candidates[i]=cand then check:=true;
    
     end;
    
     Candidate_Exists:=check;
    
    End;
    
    
    Function Cells_Collide(x1,y1,x2,y2:smallint):string;
    
    {A key function for the XY-wing. This checks if two cells can see each other and what house they share.
    This latter is not too important XY-wing wise, but I do use it in other procedures too.}
    
    Begin
    
     if (x1=x2) and (y1=y2) then Cells_Collide:='null'
     else
     if x1=x2 then Cells_Collide:='row'
     else
     if y1=y2 then Cells_Collide:='column'
     else
     if BoxCalc(x1,y1)=BoxCalc(x2,y2) then Cells_Collide:='box'
     else
     Cells_Collide:='null';
    
    
    End;
    
    Procedure Eliminate(x,y,cand:smallint);
    
    {This is just a simple procedure to save me some typing}
    
    var
    
    i,j:smallint;
    
    Begin
    
    
     if Candidate_Exists(x,y,cand) then
    
     begin
    
     for i:=1 to Grid[x,y].Num_of_Candidates do
    
     begin
    
      if Grid[x,y].Candidates[i]=cand then
    
      begin
    
       Grid[x,y].Candidates[i]:=Grid[x,y].Candidates[Grid[x,y].Num_of_Candidates];
       Grid[x,y].Candidates[Grid[x,y].Num_of_Candidates]:=0;
       Grid[x,y].Num_of_Candidates:=Grid[x,y].Num_of_Candidates-1;
    
       Have_Result:=True;
    
      end;
    
     end;
    
     end;
    
    End;
    
    
    
    
    Function Num_of_Cands(arr:TArr;Cand:smallint):smallint;
    
    {This is also very simple and specific. If three cells all have 2 candidates and I read ALL candidates into an array, 
    and each candidate only has an incidence of two, 
    then they can not be other than (a,b) (b,c) and (a,c) since one candidate can not reside twice in any of the cells. 
    An XY-wing works with cells like this, so this is to check that}
    
    var
    
    i:smallint;
    
    base:smallint;
    
    Begin
    
     base:=0;
    
     for i:=1 to 6 do
    
     begin
    
      if arr[i]=Cand then base:=base+1;
    
     end;
    
     Num_of_Cands:=base;
    
    End;
    
    Function ValidCandidates(Square1,Square2,Square3:TCell):Boolean;
    
    {This uses the above method to check for possibly valid XY-wings }
    
    var
    
    i:smallint;
    
    base:boolean;
    
    Candidates:array[1..6] of smallint;
    
    Begin
    
     base:=false;
    
     Candidates[1]:=Square1[3];
     Candidates[2]:=Square1[4];
    
     Candidates[3]:=Square2[3];
     Candidates[4]:=Square2[4];
    
     Candidates[5]:=Square3[3];
     Candidates[6]:=Square3[4];
    
     if ( Num_of_Cands(Candidates,Square1[3])=2 ) and (Num_of_Cands(Candidates,Square1[4])=2 ) then
    
     if ( Num_of_Cands(Candidates,Square2[3])=2 ) and (Num_of_Cands(Candidates,Square2[4])=2 ) then
    
     if ( Num_of_Cands(Candidates,Square3[3])=2 ) and (Num_of_Cands(Candidates,Square3[4])=2 ) then
    
     base:=true;
    
     ValidCandidates:=base;
    
    End;
    
    
    Function ValidPosition(Square1,Square2,Square3:TCell):smallint;
    
    {This function checks if the position of the cells are good to form an XY-wing. 
    If it is valid, it also returns which one will be the Hinge, and which two the Wings. 
    Which wing will be wing 1 or wing 2 is fortunately irrelevant so I don't really have to deal with that. 
    If it is not valid, it returns a 0}
    
    Var
    
    base:smallint;
    
    x1,x2,x3:smallint;
    
    y1,y2,y3:smallint;
    
    
    
    Begin
    
     base:=0;
    
     x1:=Square1[1];
     y1:=Square1[2];
    
     x2:=Square2[1];
     y2:=Square2[2];
    
     x3:=Square3[1];
     y3:=Square3[2];
    
    
    
     if (Cells_Collide(x1,y1,x2,y2)<>'null') and (Cells_Collide(x1,y1,x3,y3)<>'null') and (Cells_Collide(x2,y2,x3,y3)='null')
    
     then base:=1
    
     else
    
     if (Cells_Collide(x1,y1,x2,y2)<>'null') and (Cells_Collide(x1,y1,x3,y3)='null') and (Cells_Collide(x2,y2,x3,y3)<>'null')
    
     then base:=2
    
     else
    
     if (Cells_Collide(x1,y1,x2,y2)='null') and (Cells_Collide(x1,y1,x3,y3)<>'null') and (Cells_Collide(x2,y2,x3,y3)<>'null')
    
     then base:=3
    
     else
    
     base:=0;
    
     ValidPosition:=base;
    
    End;
    
    Function Common_Candidate(Square1,Square2:TCell):smallint;
    
    {This function will be called when a valid XY-wing is found to determine which candidate should be removed from particular cells
    Obviously, it's going to be the one that the two Wings share.}
    
    var
    
    i:smallint;
    
    base:smallint;
    
    arr:TArr;
    
    Begin
    
     arr[1]:=Square1[3];
     arr[2]:=Square1[4];
    
     arr[3]:=Square2[3];
     arr[4]:=Square2[4];
    
     arr[5]:=0;
     arr[6]:=0;
    
     for i:=1 to 2 do
    
     begin
    
      if Num_of_Cands(arr,arr[i])=2 then base:=arr[i];
    
     end;
    
     Common_Candidate:=base;
    
    End;
    
    {And finally, here's the actual procedure}
    
    Procedure Find_XY_Wing;
    
    
    Var
    
    
    i,j:smallint;
    
    count:integer;
    
    tries1,tries2,tries3:integer;
    
    remove:smallint;
    
    Point1: TPointCell;
    Point2: TPointCell;
    Point3: TPointCell;
    
    Cell1: TCell;
    Cell2: TCell;
    Cell3: TCell;
    
    Hinge: TCell;
    Wing1: TCell;
    Wing2: TCell;
    
    Possibles:TPossibles;
    
    
    Begin
    
     // Nullify everything and set pointers
    
     Have_Result:=false;
    
    
     for i:=1 to 4 do
    
     begin
    
      Cell1[i]:=0;
      Cell2[i]:=0;
      Cell3[i]:=0;
    
      Hinge[i]:=0;
      Wing1[i]:=0;
      Wing2[i]:=0;
    
      Point1:=@Cell1;
      Point2:=@Cell2;
      Point3:=@Cell3;
    
     end;
    
     //Fill in Possibles and determine number of pairs;
    
     count:=1;
    
     for i:=1 to 9 do
    
     begin
    
      for j:=1 to 9 do
    
      begin
    
       if Grid[i,j].Num_of_Candidates=2 then
    
       begin
    
        Possibles[count][1]:=i;
        Possibles[count][2]:=j;
    
        Possibles[count][3]:=Grid[i,j].Candidates[1];
        Possibles[count][4]:=Grid[i,j].Candidates[2];
    
        count :=count+1;
    
       end;
    
      end;
    
     end;
    
    
     //Check for all possible combination of the pairs on the Grid whether they're valid XY-wings or not. This is loop land...
    
     for tries1:=1 to count do
    
     begin
    
      Point1^:=Possibles[tries1];
    
      for tries2:=1 to count do
    
      begin
    
       if tries2<>tries1 then
    
       begin
    
        Point2^:=Possibles[tries2];
    
        for tries3:=1 to count do
    
        begin
    
         if (tries3<>tries1) and (tries3<>tries2) then
    
         begin
    
          Point3^:=Possibles[tries3];
    
          //Now all pairs have a unique pointer
    
          //Check if they form an XY-Wing based on Candidates and Position
    
          if (ValidCandidates(Point1^,Point2^,Point3^)) and (ValidPosition(Point1^,Point2^,Point3^)<>0) then
    
          begin
    
           if ValidPosition(Point1^,Point2^,Point3^)=1 then
    
           begin
    
            Hinge:=Point1^;
            Wing1:=Point2^;
            Wing2:=Point3^;
    
           end
    
           else
    
           if ValidPosition(Point1^,Point2^,Point3^)=2 then
    
           begin
    
            Hinge:=Point2^;
            Wing1:=Point1^;
            Wing2:=Point3^;
    
           end
    
           else
    
           begin
    
            Hinge:=Point3^;
            Wing1:=Point1^;
            Wing2:=Point2^;
    
           end;
    
           //The XY-Wing is set if found
    
           remove:=Common_Candidate(Wing1,Wing2);  //This Candidate will be eliminated
    
           //Go through the grid and find cells from which the candidate should be eliminated
    
           for i:=1 to 9 do
    
           begin
    
            for j:=1 to 9 do
    
            begin
    
             If ( Cells_Collide(i,j,Wing1[1],Wing1[2])<>'null' ) and (Cells_Collide(i,j,Wing2[1],Wing2[2])<>'null' ) then
    
             begin
    
              //Elimination
    
              Eliminate(i,j,remove);
    
             end;
    
            end;
    
           end;
    
           //End of Grid Check
    
          end;
    
          //End of XY-Wing Check
    
         end;
        end;
       end;
      end;
     end;
    
     //End of try loop
    
     Point1:=nil;
     Point2:=nil;
     Point3:=nil;
    
     //Clearing pointers
    
    End; //End of Procedure
    Now belive it or not, this mess does work very well, and I didn't even have to debug it too much, there were some minor issues with the basic functions, but not the main procedure.

    Here's a picture of what is happening here:



    Now this procedure works perfectly, my problem is the one step more advanced things such as Simple Chains and XY-Chains (entirely different from XY-wings...) Right now I have some pretty nasty exams so I don't even really have time, I just started this topic so I could get help for problems arising. This solver is pretty neat already, it can solve many sudokus, when I'm going to start implementing the more advanced stuff into it, I'm pretty sure I will come back with more specific questions.
    Attached Images Attached Images

  4. #4
    Quote Originally Posted by SilverWarior View Post
    Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

    Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

    So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
    You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
    This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

    I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code

    Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
    As for the need to use objects to make this Sudoku solver I don't think they are required.
    Oh man, I just see that for some reason my reply didn't get posted. Well, anyway. Short story is that I don't feel like doing this decision tree method, because the goal is not really to write a program that can solve any sudoku, I could do that, I'm confident in that, it's not that hard. The goal is to implement the human-like strategies, so that later when I do a visual interface for it, it can actually show you how to solve it.

    I'm not really stuck when there are no more singles, as I've said, I've already written quite a few methods for this. The most complicated one is the XY-Wing, which is a real mess if you looked at the code, you'd see, but it does work, and it is fast thanks to that I used pointers for the arrays. So even if it has to loop for 80000 times, not only this procedure alone, but the entire solution takes less than a second, if it is easy enough that the XY-wing is the most advanced strategy required for the solution.

    Where I am really stuck is when I'd need the program do something, that is called "Chaining" in sudoku strategy. This is not based on general rules and different formations on the grid like the X-wing, or XY-wing. These strategies work with assumptions.

    For example I choose a Cell where only 2 candidates are left, and I follow a chain with strong links, so I pretty much only care about cells that only have 2 candidates, and my target cells are going to be cells that are seen by multiple cells with strong links. So first I choose a candidate, and follow the chain. Then I choose the second candidate and follow the chain. If at any cell on the grid, there is a match between the two chains(e.g. a cell can not take a value, or a cell takes a value in both cases), then that must be correct. This is called an XY-chain, it is one of the more advanced strategies that are required to solve the hardest puzzles.

    Another idea is a bit more simple, it's called Simple coluring, or Singles chaining. In this case, we only pay attention for one candidate, and search for cells that are linked strongly together. Strong link between two cells mean that for at least one candidate they are the only two cells in a house(row, column, or box). Why this is important is because we know for sure that one of them HAS to take the value of that candidate. So I can follow these strong links for this one candidate and assign a colour to each cell inside the chain, one for a colour "A" and one for a colour "B". And then I can draw the consequences, we know that either all cells coloured "A" are correct, or all cells coloured "B" are correct, there is no way some of "A" and some of "B" could be correct it would lead to a contradiction. So if an uncoloured cell sees two cells with different colours, then that candidate can not exist there. Or, for example if two cells of the same colour share a house, then we know that this colour can not be the solution, the other colour has to be correct.

    This sounds a bit complicated, but it's actually very easy for a human to applicate, it's a bit more tough to code it though, especially the XY-Chains, because those can involve "weak links" , and the program would have to be able to differentiate between strong and weak links and how to use both of them too, this is crucial, or else it will start searching for completely useless chains, so to make it efficient, there is a bit of theory the program needs to "know".
    Last edited by audioinstinct; 03-01-2015 at 02:32 PM.

  5. #5
    There are two reasons why I sugested the above mentioned approach.
    1. While implementing a simple algorithm that is capable of solving sudoku like I sugested above is probably to easy for you having that in your program might actually be usefull when designing your more advanced algorithms becouse it gives you the ability to compare the results which I belive could quickly alow you to find errors in your more advanced algorithms.
    2. My knowledge on solvig sudoku is more or les basic. When you are mentioning all those advanced aproaches for solving sudoku it is simply giving me a headacke becouse I probably have never used them or perhaps did used them without being aware of it

    Anywhay as I sad my knowledge on sovig Sudoku is prety limited. I have been taught the verry basics of solving the Sudoku from my mother. But later I actually learned a bit more, especially about searching for singles, from studying a soruce code for a sudoku solver that is written in pascal (using Delphi) and has been posted on Delphi.About comunity by Ron Malizia but I can't find it anymore.
    Ron Malizia's sudoku solver gratly influenced the way how I did mine. Later on I trued to improve mine even further by adding support for multithreading and provide a way for 4 by 4 sudoku. Now if my memory serves me corectly I have sucsesfully implemented 4 by 4 sudoku solver but I failed on multithreading support becouse my knowledge on that matter was just to weak at the time (I kept corrupting my data and the biggest mistake was accesing VCL from other threads).

    So in short I probably won't be of to much help to you unless I learn how to use all these advanced approaches myself

    EDIT: As for your post not being seen after you have posted it. I suggest that next time you try to refresh the webpage before asuming the post wasn't posted. PGD site is being hosted from multiple synchronized servers to provide load balancing capability and sometimes it happens that all the servers might not be in perfect sync therefore your post is still not seen.
    Unfortunately we don't have direct controll on this as it is being controlled by our site host (GoDaddy) so we can't debug the main cause for this. Fortunately these ocurances are quite rare. Infact I belive it has been almost a yer since such thing was last reported.
    EDIT2: I just noticed that the reason why your post wasn't seen is becouse it was waiting for moderation. That shouldn't have happen since you are already a full member. I will report this isue to the site Admin so we can figure out why this happened.
    Last edited by SilverWarior; 03-01-2015 at 03:21 PM.

  6. #6
    Quote Originally Posted by SilverWarior View Post
    There are two reasons why I sugested the above mentioned approach.
    1. While implementing a simple algorithm that is capable of solving sudoku like I sugested above is probably to easy for you having that in your program might actually be usefull when designing your more advanced algorithms becouse it gives you the ability to compare the results which I belive could quickly alow you to find errors in your more advanced algorithms.
    2. My knowledge on solvig sudoku is more or les basic. When you are mentioning all those advanced aproaches for solving sudoku it is simply giving me a headacke becouse I probably have never used them or perhaps did used them without being aware of it

    Anywhay as I sad my knowledge on sovig Sudoku is prety limited. I have been taught the verry basics of solving the Sudoku from my mother. But later I actually learned a bit more, especially about searching for singles, from studying a soruce code for a sudoku solver that is written in pascal (using Delphi) and has been posted on Delphi.About comunity by Ron Malizia but I can't find it anymore.
    Ron Malizia's sudoku solver gratly influenced the way how I did mine. Later on I trued to improve mine even further by adding support for multithreading and provide a way for 4 by 4 sudoku. Now if my memory serves me corectly I have sucsesfully implemented 4 by 4 sudoku solver but I failed on multithreading support becouse my knowledge on that matter was just to weak at the time (I kept corrupting my data and the biggest mistake was accesing VCL from other threads).

    So in short I probably won't be of to much help to you unless I learn how to use all these advanced approaches myself

    EDIT: As for your post not being seen after you have posted it. I suggest that next time you try to refresh the webpage before asuming the post wasn't posted. PGD site is being hosted from multiple synchronized servers to provide load balancing capability and sometimes it happens that all the servers might not be in perfect sync therefore your post is still not seen.
    Unfortunately we don't have direct controll on this as it is being controlled by our site host (GoDaddy) so we can't debug the main cause for this. Fortunately these ocurances are quite rare. Infact I belive it has been almost a yer since such thing was last reported.
    EDIT2: I just noticed that the reason why your post wasn't seen is becouse it was waiting for moderation. That shouldn't have happen since you are already a full member. I will report this isue to the site Admin so we can figure out why this happened.
    Yeah about my post it was interesting. It told me my post had been posted successfully and it would redirect me, it didn't mention any moderation stuff, but it also didn't appear and when I refreshed the page it told me I was trying to "duplicate" the post so it wouldn't let me do that, it was really weird, but I thought if I just waited a couple of minutes and resend the information it would post, apparently it didn't, which is understandable, well anyway...

    As for the advanced methods I am talking about here, it's tough to just explain it, believe me these are really really simple things. Here's a picture of Simple Colouring...



    As you can see I could start anywhere on this grid but the simple way is this:

    If A2=4 then A8 can not be a 4.

    If A2=4 then H8 can not be a 4, then H7 must be a 4 then G9 can not be a 4, then C9 must be a 4.

    This is simply due to the fact that all rows, columns, and boxes must contain a 4 but only one(strong links). Generally, we can say that if A2 is a 4, then all green coloured 4s are correct and all blue coloured 4s are incorrect.


    Now I could start the other way and assume that A2<>4.

    What I'd get is the exact opposite, this time all blue 4s would be correct, and all
    green ones would be incorrect.

    If we look at the grid we can see there are a few 4s that are not coloured green or blue.

    We are uncertain about these because we don't have strong links to them.

    But we do know that either all greens or all blues are correct, so in box 3 we can see there is a blue and there is a green 4. Since one of these must be correct and the box can only have one 4 inside it, we can conclude that on C7 and on B8 there is no way a 4 can exist.

    Surely there are going to be much tougher things, but if I get the hang of how to implement chaining strategies in general into the program, then I will probably do fine on my own. The XY-wing which is already complete also contains two "chains" but they are only two steps long, and it already took me 80000 loops to check the entire grid for it, this approach would be highly inefficient with these chains that can go up to 6 or more links, I could imagine something like 9^12 loops with my original approach, absolutely insane, this should be avoided. The reason is that with the XY-Wing I had to compare all candidates of all cells that have exactly two candidates, and find 3 of them that form a valid XY-wing. Now with these chains this idea would become very inefficient, I need a different approach.
    Attached Images Attached Images

  7. #7
    I just posted another reply and this time, it did warn me about moderation. It seems like I can post freely but if I include a picture in the post, a moderator has to approve it.

  8. #8
    PGD Staff / News Reporter phibermon's Avatar
    Join Date
    Sep 2009
    Location
    England
    Posts
    524
    You may want to examine developing a Monte Carlo simulation as an alternative solver. I see no reason why a Sudoku solution can't be derived using the technique and in fact as a learning exercise I'd highly recommend it.

  9. #9
    Quote Originally Posted by phibermon View Post
    You may want to examine developing a Monte Carlo simulation as an alternative solver. I see no reason why a Sudoku solution can't be derived using the technique and in fact as a learning exercise I'd highly recommend it.
    Wow that seems super complicated, I've just read it up on wikipedia I have absolutely no idea how I would try to code a method like that. I don't even understand it completely. I'm guessing that in my case it would be a probability distribution problem? So I would have to generate a lot of already solved grids and compare the current state with these? Not sure if I'm getting this right...

  10. #10
    Quote Originally Posted by audioinstinct View Post
    I just posted another reply and this time, it did warn me about moderation. It seems like I can post freely but if I include a picture in the post, a moderator has to approve it.
    Hmm that is strange. I will however forward this information to site administrator.

Page 1 of 3 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
  •