Page 1 of 2 1 2 LastLast
Results 1 to 15 of 28

Thread: Sudoku solve algorithm

  1. #1
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458

    Sudoku solve algorithm

    Beste,

    Ik probeer een Sudoku solving algorithm te schrijven. Althans.... vertalen vanuit een voorbeeld in Java.

    Dit is de Java code:
    Code:
    	public boolean solveSudoku()
    	{
    		for(int row=0;row<9;row++)
    		{
    			for(int col=0;col<9;col++)
    			{
    				if(sudoku[row][col]==UNASSIGNED)
    				{
    					for(int number=1;number<=9;number++)
    					{
    						if(isAllowed(row, col, number))
    						{
    							sudoku[row][col] = number;
    							if(solveSudoku())
    							{
    								return true;
    							}
    							else
    							{
    								sudoku[row][col] = UNASSIGNED;
    							}
    						}
    					}
    					return false;
    				}
    			}
    		}
    		return true;
    	}
    En dit is wat ik ervan heb gebakken:
    Code:
    function TForm1.Solve: boolean;
    var  i , j  , n: integer;
    begin
      for I := Low(Matrix) to High(Matrix) do //Matrix is een 2d array of integer met sudoku data
       for j := Low(Matrix[i]) to High(Matrix[i]) do
        begin
         if Matrix[i,j] = 0 then
          for n := 1 to 9 do
          begin
            if IsValidNumber(n , i , j) then //IsValidNumber = boolean function die getest is en werkt
             begin
               Matrix[i,j] := n;
               if solve then
                result := true else
               Matrix[i,j] := 0;
             end;
          result := false;
         end;
        end;
    result := true;
    end;
    Nu heb ik dit getest en iedere keer mis ik een aantal getallen in mijn grid.
    Maar.... die grid wordt getoond als function Solve een true teruggeeft.
    Dus ja: wat zou er beter kunnen? Ik zie het even niet?¿

    Alvast bedankt voor jullie reacties.
    Greetzz Jacco

  2. #2
    mov rax,marcov; push rax marcov's Avatar
    Join Date
    Apr 2004
    Location
    Ehv, Nl
    Posts
    10,357
    exit(true); ipv result:=true;


    result zet alleen de return waarde, maar gaat door tot de procedure afloopt. Exit stopt ook de procedure.

  3. #3
    Er is een Sudoku solver in de Lazarus wiki.

    Bart

  4. #4
    Senior Member Wok's Avatar
    Join Date
    Dec 2002
    Location
    Alkmaar
    Posts
    2,085
    Quote Originally Posted by Bart B View Post
    Er is een Sudoku solver in de Lazarus wiki.
    Er zijn wel meer oplossingen te vinden, maar zelf heeft de grootste leercurve en doen geeft de meeste voldoening
    10.4.2, Delphi2010, of Lazarus 2.2.0

  5. #5
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458
    @Marcov. bedankt voor de tip. Alleen heeft het bij mij geen effect. De getallen die wel ingevuld worden zijn trouwens ook niet goed, vandaar dat de laatste getallen niet ingevuld worden omdat er geen valid getal beschikbaar is. Dus ergens gaat het fout met backtracking.. maar waar? Wellicht dat er ergens een begin en end niet goed staan, maar als ik daar mee 'speel' doet ie of niks, of komt in een endless loop?

    @Bart Klopt , bedankt voor de tip. Die ben ik ook al aan het doorspitten kijken of ik daar iets uit kan halen.
    Maar zoals @Wok al zegt......
    Greetzz Jacco

  6. #6
    Quote Originally Posted by Bolus View Post
    @Marcov. bedankt voor de tip. Alleen heeft het bij mij geen effect.
    Hoe ziet je code eruit na de aanpassingen van de tip van Marco?
    Want er zijn meerdere results :=

    In java is een return een commando. Niet alleen een result :=
    Verander dus alle return false door exit(false) en alle return true door exit(true).

  7. #7
    In enig verleden heb ik weleens een recursief experiment gedaan om een 'japanse' puzzel op te lossen. Hierbij staan aan de zij- en bovenkant van een rechthoek getallen die aangeven hoeveel aanééngesloten vakjes zwart zijn en zo een pixelfiguur vormen. Na heel veel rekenwerk kwam er vaak een oplossing, soms niet. Dit laatste waarschijnlijk door een programmeerfout ergens. Die fout heb ik nooit gevonden. Een leuk experiment, maar het leverde weinig inzicht op in het efficiënt oplossen van de puzzel. Bovendien was de rekentijd vaak enorm.
    Zo kijk ik ook naar de oplossing die jij lijkt na te bouwen. (Dit is geen kritiek, het is goed te experimenteren met recursie!).

    Ik heb voor mijzelf ook een oplosmethode bedacht voor de Sudoku. Die is enerzijds flexibel en efficiënt, maar lost nog niet alles op ...
    Flexibiliteit krijg je door de series van 9 (of 16, of 25, etc) getallen onder te brengen in groepen. Dit zijn groepen van (1) horizontale lijnen, (2) verticale lijnen en (3) al dan niet regelmatige vakken. Deze indeling geeft je de flexibiliteit om afwijkende indelingen (Volkskrant, Tubantia - beide in de weekenden) aan te kunnen zonder veel extra programmeerwerk.
    Binnen een groep heb je de regel dat als een getal voorkomt, die niet meer in de andere elementen (enkelvoudige hokjes) van die groep mag voorkomen.
    Je gaat nu op zoek naar hokjes waar nog maar één enkel getal is toegestaan. Door dit getal in te vullen loop je weer alle hokjes lang van de groepen waar het ingevulde hokje deel van is.
    Wat blijkt? De meeste Sudoku's zijn hiermee oplosbaar. Een zeker percentage niet, maar daar verzin je een extra oplosmethode voor.

    Bovengenoemde methoden dwingt je het probleem te analyseren en (pas daarna) te programmeren.
    Het heeft mij bovendien geholpen Sudoku's sneller en efficiënter met de hand op te lossen.

    Succes en veel plezier!

  8. #8
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458
    @rvk:
    Code:
    function TForm1.Solve: boolean;
    var  i , j  , n: integer;
    begin
    
      for I := Low(Matrix) to High(Matrix) do
       for j := Low(Matrix[i]) to High(Matrix[i]) do
    
         if Matrix[i,j] = 0 then
         begin
          for n := 1 to 9 do
            if IsValidNumber(n , i , j) then
             begin
               Matrix[i,j] := n;
               if solve then
                exit(true) else
                begin
                 Matrix[i,j] := 0;
                 exit(false);
                end;
    
             end;
    
        end;
    
    
    exit(true);
    end;
    Code ziet er nu zo uit. Steeds hetzelfde resultaat. Maar ik denk dat ik wel weet waar het probleem is, maar nog na moet denken over de oplossing.
    Gaan we nl stap voor stap kijken wat de code doet:
    Loop door de matrix:
    Code:
      for I := Low(Matrix) to High(Matrix) do
       for j := Low(Matrix[i]) to High(Matrix[i]) do
    Als de waarde 0 is check of ereen ValidNumber is en plaats het daar.
    Code:
     if Matrix[i,j] = 0 then
         begin
          for n := 1 to 9 do
            if IsValidNumber(n , i , j) then
             begin
               Matrix[i,j] := n;
    if Solve... gaat hier dus terug naar de nested loop voor de exit.
    En hierboven is de matrix dus al aangepast.
    Code:
               if solve then
                exit(true) else
    Maar wat er zou moeten gebeuren is dat er gechecked wordt of het vanaf aan bepaalde positie oplosbaar is, zo niet moet de waarde van de oorspronkelijke positie weer 0 worden.
    Code:
                exit(true) else
                begin
                 Matrix[i,j] := 0;
                 exit(false);
                end;
    Maar hierboven zijn er in de matrix al aanpassingen gedaan...
    Of maak ik nu een denkfout?
    Greetzz Jacco

  9. #9
    Quote Originally Posted by Bolus View Post
    @rvk:
    Code:
     if Matrix[i,j] = 0 then
         begin
          for n := 1 to 9 do
            if IsValidNumber(n , i , j) then
             begin
               Matrix[i,j] := n;
    if Solve... gaat hier dus terug naar de nested loop voor de exit.
    En hierboven is de matrix dus al aangepast.
    Code:
               if solve then
                exit(true) else
    "En hierboven is de matrix dus al aangepast."

    Maar dat is nu de kracht van de recursie.
    Je zet dus een willekeurig mogelijk nummer neer en gaat "in de recursie" kijken of die klopt.
    Als die niet klopt (omdat verderop toch iets fout ging) dan wordt het vlak weer op 0 gezet.

    Maar aangezien dat in recursie is kan het ook zijn dat vlakken die veel eerder al gevuld waren toch weer op 0 gezet worden (als je uiteinelijk uit die recursie komt). Helemaal terug tot de eerste vulling.

    Je hebt alleen de exit(false); op de verkeerde plaats staan (of een exit(false); te weinig).
    Volgens mij was je originele code bijna goed (op de exits na). In je laatste code heb je daar iets heel anders van gemaakt.

    Volgens mij (zonder te testen) zou het zoiets moeten zijn.

    Delphi Code:
    1. function TForm1.Solve: boolean;
    2. var
    3.   i, j, n: integer;
    4. begin
    5.   for I := Low(Matrix) to High(Matrix) do
    6.     //Matrix is een 2d array of integer met sudoku data
    7.     for j := Low(Matrix[i]) to High(Matrix[i]) do
    8.     begin
    9.       if Matrix[i, j] = 0 then
    10.         for n := 1 to 9 do
    11.         begin
    12.           if IsValidNumber(n, i, j) then
    13.             //IsValidNumber = boolean function die getest is en werkt
    14.           begin
    15.             Matrix[i, j] := n;
    16.             if solve then
    17.               exit(true)
    18.             else
    19.               Matrix[i, j] := 0;
    20.           end;
    21.         end;
    22.         exit(false);
    23.     end;
    24.   exit(true);
    25. end;

  10. #10
    Quote Originally Posted by MaartenW View Post
    Binnen een groep heb je de regel dat als een getal voorkomt, die niet meer in de andere elementen (enkelvoudige hokjes) van die groep mag voorkomen.
    Je gaat nu op zoek naar hokjes waar nog maar één enkel getal is toegestaan. Door dit getal in te vullen loop je weer alle hokjes lang van de groepen waar het ingevulde hokje deel van is.
    Wat blijkt? De meeste Sudoku's zijn hiermee oplosbaar. Een zeker percentage niet, maar daar verzin je een extra oplosmethode voor.
    Hahahahaha
    Je bedoeld dat de meeste makkelijke Sudoku's hiermee zo opgelost kunnen worden.
    De Sudoku's die ik doe kunnen zo absoluut niet opgelost worden.
    Daar red ik het soms zelfs niet mee met de meest gangbare oplossingstechnieken (en dat zijn niet de 'single possible digit' technieken).

    Brute force is in ieder geval veel makkelijker te programmeren

  11. #11
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458
    rvk: dank voor je bericht.
    Lijkt nog steeds niet te werken. Ik heb een breekpunt gezet aan het begin van de nested loop.
    Springt dan naar
    Code:
     if Matrix[i,j] = 0
    (is in mijn test niet zo) en daarna gelijk naar exit(false).


    Delphi Code:
    1. function TForm1.Solve: boolean;
    2. var
    3.   i, j, n: integer;
    4. begin
    5.   for I := Low(Matrix) to High(Matrix) do //<< hier breakpunt gezet en met F8 een run gedaan.
    6.     //Matrix is een 2d array of integer met sudoku data
    7.     for j := Low(Matrix[i]) to High(Matrix[i]) do << code springt hiernaartoe
    8.     begin
    9.       if Matrix[i, j] = 0 then << daarna hiernaartoe
    10.         for n := 1 to 9 do
    11.         begin
    12.           if IsValidNumber(n, i, j) then
    13.             //IsValidNumber = boolean function die getest is en werkt
    14.           begin
    15.             Matrix[i, j] := n;
    16.             if solve then
    17.               exit(true)
    18.             else
    19.               Matrix[i, j] := 0;
    20.           end;
    21.         end;
    22.         exit(false); << en dan rechtstreeks hiernaartoe
    23.     end;
    24.   exit(true);
    25. end;
    Greetzz Jacco

  12. #12
    Quote Originally Posted by Bolus View Post
    rvk: dank voor je bericht.
    Lijkt nog steeds niet te werken. Ik heb een breekpunt gezet aan het begin van de nested loop.
    Springt dan naar
    Code:
     if Matrix[i,j] = 0
    (is in mijn test niet zo) en daarna gelijk naar exit(false).
    Ik heb die IsValidNumber() niet dus kan hem niet zo testen.
    Maar er staat inderdaad een begin/end te weinig in.
    De exit(false) moet binnen de if Matrix staan en dat is nu niet het geval omdat er geen begin/end is.

    Dus dan zou het ongeveer dit kunnen zijn. (begin/end kun je ook gebruiken als het niet perse hoeft)

    Delphi Code:
    1. function TForm1.Solve: boolean;
    2. var
    3.   i, j, n: integer;
    4. begin
    5.   //Matrix is een 2d array of integer met sudoku data
    6.   for I := Low(Matrix) to High(Matrix) do
    7.   begin
    8.     for j := Low(Matrix[i]) to High(Matrix[i]) do
    9.     begin
    10.       if Matrix[i, j] = 0 then
    11.       begin
    12.         for n := 1 to 9 do
    13.         begin
    14.           if IsValidNumber(n, i, j) then
    15.           begin
    16.             Matrix[i, j] := n;
    17.             if solve then
    18.               exit(true)
    19.             else
    20.               Matrix[i, j] := 0;
    21.           end; // isvalidnumber
    22.         end; // for 1 to 9
    23.         exit(false); // NA de for 1 to 9 maar binnen if matrix=0
    24.       end;
    25.     end;
    26.   end;
    27.   exit(true);
    28. end;

    Volgens mij is ie nu hetzelfde als de java code (ook met de begin/end).

    Ps. als je al kant en klare pascal code wil bestuderen dan kun je eens hier kijken. https://forum.lazarus.freepascal.org...html#msg225911. Maar ik denk dat er ook nog genoeg andere Delphi/Pascal code te vinden zal zijn (weet ook niet waarom je vanuit java code uitgegaan bent).
    Last edited by rvk; 17-Feb-21 at 19:03.

  13. #13
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458
    Quote Originally Posted by rvk View Post
    Ik heb die IsValidNumber() niet dus kan hem niet zo testen.
    Maar er staat inderdaad een begin/end te weinig in.
    De exit(false) moet binnen de if Matrix staan en dat is nu niet het geval omdat er geen begin/end is.
    Delphi Code:
    1. type Col = array of integer;
    2.   type Row = array of integer;
    3.   type Square = array of integer;
    4.  
    5. function TForm1.IsNumberInArray(n: Integer; a: array of integer):boolean;
    6. var i : integer;
    7. begin
    8. result := false;
    9.   for I := Low(a) to High(a) do
    10.     if n = a[i] then
    11.      result := true;
    12. end;
    13.  
    14. function TForm1.MatrixCol(i: Integer):Col;
    15. var aRow : integer;
    16. begin
    17.  
    18.   for aRow := 0 to 8 do
    19.     result := result + [Matrix[i, aRow]];
    20. end;
    21.  
    22. function TForm1.MatrixRow(i: Integer): row;
    23. var aCol : integer;
    24. begin
    25.   for aCol:= 0 to 8 do
    26.     result := result + [Matrix[aCol , i]];
    27. end;
    28.  
    29. function TForm1.MatrixSquare(P: TPoint): Square;
    30. var x , y : integer;
    31. begin
    32.    for x := 0 to 2 do
    33.      for y := 0 to 2 do
    34.       result := result + [Matrix[x+P.X,y+P.Y]];
    35. end;
    36.  
    37. function TForm1.IsInSquare(aCol: Integer; aRow: Integer):TPoint;
    38. var X , Y : integer;
    39. begin
    40.   if aCol < 3 then X := 0 else
    41.   if (aCol > 2) and (aCol < 6) then X := 3 else X := 6;
    42.  
    43.   if aRow < 3 then Y := 0 else
    44.   if (aRow > 2) and (aRow < 6) then Y := 3 else Y := 6;
    45.  
    46.   result := Point(x,y);
    47. end;
    48. function TForm1.IsValidNumber(n , aCol , aRow: Integer):boolean;
    49. var
    50. C : Col;
    51. R : Row;
    52. S : Square;
    53. begin
    54. result := true;
    55.  C := MatrixCol(aCol);
    56.  R := MatrixRow(aRow);
    57.  S := MatrixSquare(IsInSquare(aCol,aRow));
    58.  if  IsNumberInArray(n , C) then result := false;
    59.  if  IsNumberInArray(n , R) then  result := false;
    60.  if IsNumberInArray(n , S) then  result := false;
    61. end;

    Is wellicht wat overdone, maar ik vind dit prettig lezen.
    Greetzz Jacco

  14. #14
    Hobby fröbelaar
    Join Date
    Nov 2002
    Location
    Goes
    Posts
    458
    Bedankt voor je hulp! Nu werkt het.

    Ik was uitgegaan van de java code omdat dit in een tutorial stap voor stap uitgelegd werd wat de code deed (of zou moeten doen) , mijn naïviteit en ik dachten dat het dan een fluitje van een cent zou zijn om dat 'even' te vertalen.
    Greetzz Jacco

  15. #15
    Op zich ook niet slecht een tutorial te volgen zodat de manier duidelijk is.

    Enige waarmee je de mist inging was de return = exit(true/false) en het juist vertalen van de { en } in begin en end.

    Als je nu beide stukjes code bekijkt zal het waarschijnlijk wel simpel lijken. Dan gaat het de volgende keer weer makkelijker

Page 1 of 2 1 2 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

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
  •