Android Example Sudoku generator and solver

Discussion in 'Tutorials & Examples' started by Johan Schoeman, Feb 1, 2015.

  1. Johan Schoeman

    Johan Schoeman Expert Licensed User

    The attached project will generate and solve Sudoku puzzles (9x9). The code to solve the puzzles with was adapted from here (converted to B4A). The code to generate Sudoku puzzles with comes from here. It was adapted and then compiled to a B4A library. The library files (jar and xml) are in the /files folder of the attached project.

    When it starts up it will randomly select one of the Sudoku puzzles that @Erel has posted in the project that you can find here. Just click/press on "Solve" and the puzzle will be solved (it also reports the time taken in milliseconds to solve the puzzle).

    Click/press on button "Create" to randomly create a new Sudoku Puzzle. It will report the number of non-zero cells in the newly created puzzle. Then click/press "Solve" to solve the puzzle. Take note that generating new Sudoku puzzles can take a while...

    Posting the following:
    1. The B4A project (with library files in the /files folder - copy it to your additional library folder)
    2. The zipped java source code that the library files (jar and xml) were generated from

    This was done.....just for fun....:)
     

    Attached Files:

    cimperia, DavideV, MarcoRome and 3 others like this.
  2. Johan Schoeman

    Johan Schoeman Expert Licensed User

    A question for the B4A doctors. The project in post #1 makes use of a recursive process in the B4A code to solve the puzzle. The time that it sometimes take to solve the puzzle is far shorter than the time to return control back to the user interface. Probably because the one sub keeps on calling itself to solve the puzzle. What is the quickest way to hand control back to the User interface once a solution has been found (other than perhaps having to rewrite the code)?
     
  3. Erel

    Erel Administrator Staff Member Licensed User

    You need to stop the recursion once you find a solution.

    Does your code continue to look for solutions after it find the first one?
     
  4. Johan Schoeman

    Johan Schoeman Expert Licensed User

    Hi Erel

    See code below with comments added. The problem (delay in returning the control to the B4A UI) is not so visible with the puzzles in your competition but some puzzles with 21 or 20 "givens" causes a severe delay between the time that the puzzle has actually been solved and UI control in the B4A project. Sometimes as much as 7+ seconds!

    I have added an additional button (New puzzle) to the project attached to this post that will randomly select one of 640 different unsolved puzzles (although I still need to check for perhaps some duplicates). Some of these puzzles has 20 or 21 "givens" and the time difference between getting to the solution and returning control to the UI can be excessive. Puzzle No16 is amongst others an example of the excessive delay that I see.

    Code:
    Sub solve(sudoku1(,) As Int, cellX As Int, cellY As Int)

        
    'If the y value is 9 then the sudoku has been solved. How do we exit from here as fast as possible?
        If(cellY > 8Then
          endtm = 
    DateTime.Now
          
    Dim cnt As Int = 0
          
    For i = 0 To 8
            
    For j = 0 To 8
              lab(cnt).text = sudoku(i,j)
              cnt = cnt + 
    1
            
    Next
          
    Next
          
    'I SOMEHOW NEED TO EXIT FROM HERE AS THE SOLUTION HAS BEEN FOUND
          'USING Return DOES NOT SOLVE THE PROBLEM
          'IS IT BUSY PROCESSING EVERYTHING THAT HAS BEEN PUSHED ONTO THE STACK BEFORE IT RETURNS CONTROL TO THE UI?
          Log("Solved puzzle No " & randnum & " in " & (endtm - starttm) & "ms")
          Label1.Text = 
    "Solved puzzle No " & randnum & " in " & (endtm - starttm) & "ms"
          
    Return
        
    Else
          
    Dim nextX As Int = cellX
          
    Dim nextY As Int = cellY
          
    If(cellX = 8Then
            nextX = 
    0
            nextY = nextY + 
    1
          
    Else
            nextX = nextX + 
    1
          
    End If

          
    If(sudoku1(cellY,cellX) <> 0Then
            solve(sudoku1, nextX, nextY)          
    'SUB IS CALLING ITSELF - is it adding too much to the stack and then once a solution has been found the excessive
                                                                'delay to process the stack before returning control to the B4A UI?
          Else
            
    For checkNum = 1 To 9
              
    If (checkSquare(sudoku1, cellX, cellY, checkNum) AND checkRow(sudoku1, cellY, checkNum) AND checkCol(sudoku1, cellX, checkNum)) Then
                sudoku1(cellY,cellX) = checkNum
                solve(sudoku1, nextX, nextY)     
    'SUB ALSO CALLING ITSELF
              End If
            
    Next
            sudoku1(cellY,cellX) = 
    0
          
    End If
        
    End If


    End Sub
     

    Attached Files:

    Last edited: Feb 5, 2015
  5. Erel

    Erel Administrator Staff Member Licensed User

    The 7 seconds delay is not related to the deep stack.

    If I understand your code correctly it continues to look for solutions even after a solution was found.
     
  6. Johan Schoeman

    Johan Schoeman Expert Licensed User

    Erel, so how should I then break out of the first If....then...else... block once the solution has been found? The return statement does not work as it probably return back to the same sub (it was called multiple times so return returns to the same sub?). Any better way to terminate the processing?
     
  7. Johan Schoeman

    Johan Schoeman Expert Licensed User

    Erel, you were right. It kept on calling the sub even though a solution was found. The attached project seems to have solved that problem.
     

    Attached Files:

    SIMAjoon likes this.
  8. Johan Schoeman

    Johan Schoeman Expert Licensed User

    There are 642 base puzzles in this B4A project. Have added some code that will turn this 642 puzzles randomly into approximately 21.037056 million different puzzles (give or take a few should my reasoning be correct) when the "New puzzle" button is pressed. There are many more ways to add more variants by making use of this 642 base puzzles.

    An interesting fact from http://en.wikipedia.org/wiki/Mathematics_of_Sudoku:
    The number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005
    to be 6,670,903,752,021,072,936,960 . This number is equal To 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime.
    The result was derived through logic AND brute force computation.

    This is apparently the most difficult/hardest Sudoku puzzle to solve without aid of a computer (i.e by hand):
    800000000003600000070090200050007000000045700000100030001000068008500010090000400
    (read from top left to bottom right in the 9x9 grid)
    On a rating of 1 to 5 it has been given a score of 11!
     

    Attached Files:

    Last edited: Feb 8, 2015
    ellpopeb4a likes this.
  9. Johan Schoeman

    Johan Schoeman Expert Licensed User

    The attached project solves Sudoku puzzles making use of the Dancing Links algorithm (DLX) by Dr Donald Knuth. Inline Java code from here. It is very rare that it does not solve (randomly generated) Sudoku puzzles in less than 5ms on a Samsung S4 mini - with as little as 17 "givens" (17 givens are the minimum that is required for a Sudoku puzzle).
     

    Attached Files:

    cimperia likes this.
  10. Johan Schoeman

    Johan Schoeman Expert Licensed User

    The attached project solves Sudoku puzzles by making use of the Dancing Links algorithm (DLX) by Dr Donald Knuth. It also creates new puzzles in one of two different ways:

    1. With the predefined puzzles that are hard coded in the project. Clicking on button "New puzzle" will select one of the predefined puzzle at random and it will then be "shuffled" thereby creating a new variant of the randomly selected puzzle).
    2. Using the Dancing Links algorithm (generator and solver) when button "Create" is pressed

    Classes DLXEngine, dlx_generator, and dlx_solver in the B4A project contain inline Java code that was adapted from here
     

    Attached Files:

    Last edited: Feb 21, 2015
    cimperia likes this.
  11. Johan Schoeman

    Johan Schoeman Expert Licensed User

    Attached project just makes it a bit easier to view the puzzles. The givens will be in Red (also after the puzzle has been solved) and the 0's have been eliminated in unsolved cells. The end of my Sudoku travels...

    Sudoku.png
     

    Attached Files:

    Last edited: Aug 16, 2015
    inakigarm likes this.
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice