Android Example Sudoku generator and solver

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

 

[Johan Schoeman]

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)?

 

[Erel]

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?

 

[Johan Schoeman]

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?

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.

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 > 8) Then
      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 = 8) Then
        nextX = 0
        nextY = nextY + 1
      Else
        nextX = nextX + 1
      End If

      If(sudoku1(cellY,cellX) <> 0) Then
        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

 

[Erel]

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.

 

[Johan Schoeman]

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?

 

[Johan Schoeman]

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.

 

[Johan Schoeman]

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!

 

[Johan Schoeman]

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).

 

[Johan Schoeman]

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

 

[Johan Schoeman]

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