As the sudoku solving contest winner I will now explain the solution I created. I must say that my solution is highly based on a solution I found in a blog post from a canadian student on the internet. Though I took a ready and very quick algorithm there was still many work to do. So this tutorial is more about porting Java code to B4A and then try to improve it than developing a completely new solution.
When I first saw the announcement about the contest I started to think about how to solve a sudoku puzzle. I did know a simple solution would be a dumb backtracking algorithm but I thought the fastest solution would be to solve the puzzle with rules. Since I thought not every puzzle can be solved just with rules a backtracking algorithm will still be necessary to solve every puzzle.
I started to search the Internet for sudoku solvers and found many solutions mainly based on plain backtracking with some improvements. Then I found a blog with two solutions which looked very interesting and seemed to do exactly what I have thought about. Another interesting thing with the solution was that the author provided the source in highly optimized Java.
After a first look into the Java source I thought that it would be very easy to convert it into a B4A library. Of course libraries were not allowed in the contest but I just wanted to give it a try, how fast this solution is. It just took me half an hour and I had the library working and added it to the contest test program. The result was amazing. On my LG P500 device with overclocked 729MHz processor I immediately got a result of 30ms with this library solution.
This result aroused my interest. Can the code be ported to B4A? Can I even improve it?
First I took a very close look into the Java source to fully understand how it works. The key concepts of the algorithm is to store two two dimensional arrays. One for the board with 0 values for not placed numbers and one array for a bitfield which stores which numbers are still allowed for a particular field on the board. With this two arrays it is possible to implement two types of rules. The first type of rule can place numbers directly on the board and the second type of rule can eliminate numbers from the allowed values array. For a more detailed explanation of the algorithm please have a look at these blog posts here and here.
After analyzing the code I thought that it must be possible to port it to B4A and so I started with it and I immediately applied some changes to make some things simpler. I was surprised, how easy it was to port the source to B4A. There were only some very small things I had to modify that I will explain now:
The backtracking method returns a two dimensional array. If no solution could be found then the method returns a Null value. If you declare a Sub in B4A which returns a two dimensional array you can't return a Null value so I had to declare a global array RetNull with a special value set so I can detect this special Array as Null result.
For the backtracking we need to clone the current arrays of the board and the allowed values bitfield. In the Java source this was done with Arrays.copyOf(). This method is only available in a library in B4A so I had to copy the arrays with simple for loops.
Because the Java code makes use of many final and static variables there are many places where for speed reasons a complete row of the two dimensional arrays are assigned to a one dimensional array (it is faster to use one dimensional arrays in Java than two dimensional arrays). This is not possible with B4A so I always had to access values in the two dimensional arrays.
In the Java source there is one place which uses a label and a "break label" to exit a for loop and jump to the label. Since there is nothing like that in B4A this part has to be rewritten with an If construct.
These were the main "problems" I had to solve while porting the code. Overall I must say that I have thought this would be harder. All bit operations could be simply converted and were very easy to port.
I don't know exactly the time my one to one port of the algorithm took but I think the solution with the library was more than twice as fast as the B4A-only solution. I think this is mostly because the original java source was highly optimized to use static and final varibles. I think this was still a very good result for the B4A compiler.
After the code worked I started to try to improve it. One interesting thing I found was that in the original source there was a switch-case construct that had a single case line for every value but this could be compressed so I converted it in my code to have a case for three values. Interestingly this gave a noticeable speed improvement.
Then I added some code for profiling to the rules so I could see how often each rule was called and how many numbers they could place so I got a feeling which rules were effective and which not. I played days with reordering the rules and created test loops to determine when to call which rule, when to fall back to backtracking etc. Once I had my laptop calculate complete two days to find the best values. I must say that the original algorithm was very good and my best results could only improve the result slightly. I even tried to apply two more rules but they did not give any improvements so I discarded them again.
I had a look at the generated Java code and could eliminate some additional lines. I too have added some other small improvements that save some CPU cycles like inlining the setValue Sub and added a new exit condition to a loop etc.
With all my tests with the fastest results (called in a loop so they were not the first run like Erel tested) around 11-13 ms per puzzle my goal was to get it below 10ms. After adding one rule which is quite cost intensive and is only called when the other, simpler rules only could place less than 7 numbers I managed to get results of 9ms sometimes. This was the point I stopped searching for any better solution and sent the project to Erel.
The final solution has three rules that directly place numbers on the board and two rules that reduces the allowed values for the fields on the board. These rules are called in a loop (with some additional conditions for some of the rules) until they couldn't place more than 5 numbers or more than 70 numbers of the whole board (with a total of 81 numbers) are placed. Then the rest is solved with a backtracking solution (which will again try to apply the rules if less than 70 numbers are placed).
Overall I think that the end result is slightly faster than the original code in B4A (About 10% to 20%. The solution with the library is still faster because of better optimized Java code I think.
Attached to this post is the solution with the original Java code as a library. Put the jar and xml files from the SudokuSolver_Library.zip to your B4A libraries folder to comile it. If you install the apk be aware that the program only makes log output.
The solution I have created for the contest can be found here.
When I first saw the announcement about the contest I started to think about how to solve a sudoku puzzle. I did know a simple solution would be a dumb backtracking algorithm but I thought the fastest solution would be to solve the puzzle with rules. Since I thought not every puzzle can be solved just with rules a backtracking algorithm will still be necessary to solve every puzzle.
I started to search the Internet for sudoku solvers and found many solutions mainly based on plain backtracking with some improvements. Then I found a blog with two solutions which looked very interesting and seemed to do exactly what I have thought about. Another interesting thing with the solution was that the author provided the source in highly optimized Java.
After a first look into the Java source I thought that it would be very easy to convert it into a B4A library. Of course libraries were not allowed in the contest but I just wanted to give it a try, how fast this solution is. It just took me half an hour and I had the library working and added it to the contest test program. The result was amazing. On my LG P500 device with overclocked 729MHz processor I immediately got a result of 30ms with this library solution.
This result aroused my interest. Can the code be ported to B4A? Can I even improve it?
First I took a very close look into the Java source to fully understand how it works. The key concepts of the algorithm is to store two two dimensional arrays. One for the board with 0 values for not placed numbers and one array for a bitfield which stores which numbers are still allowed for a particular field on the board. With this two arrays it is possible to implement two types of rules. The first type of rule can place numbers directly on the board and the second type of rule can eliminate numbers from the allowed values array. For a more detailed explanation of the algorithm please have a look at these blog posts here and here.
After analyzing the code I thought that it must be possible to port it to B4A and so I started with it and I immediately applied some changes to make some things simpler. I was surprised, how easy it was to port the source to B4A. There were only some very small things I had to modify that I will explain now:
The backtracking method returns a two dimensional array. If no solution could be found then the method returns a Null value. If you declare a Sub in B4A which returns a two dimensional array you can't return a Null value so I had to declare a global array RetNull with a special value set so I can detect this special Array as Null result.
For the backtracking we need to clone the current arrays of the board and the allowed values bitfield. In the Java source this was done with Arrays.copyOf(). This method is only available in a library in B4A so I had to copy the arrays with simple for loops.
Because the Java code makes use of many final and static variables there are many places where for speed reasons a complete row of the two dimensional arrays are assigned to a one dimensional array (it is faster to use one dimensional arrays in Java than two dimensional arrays). This is not possible with B4A so I always had to access values in the two dimensional arrays.
In the Java source there is one place which uses a label and a "break label" to exit a for loop and jump to the label. Since there is nothing like that in B4A this part has to be rewritten with an If construct.
These were the main "problems" I had to solve while porting the code. Overall I must say that I have thought this would be harder. All bit operations could be simply converted and were very easy to port.
I don't know exactly the time my one to one port of the algorithm took but I think the solution with the library was more than twice as fast as the B4A-only solution. I think this is mostly because the original java source was highly optimized to use static and final varibles. I think this was still a very good result for the B4A compiler.
After the code worked I started to try to improve it. One interesting thing I found was that in the original source there was a switch-case construct that had a single case line for every value but this could be compressed so I converted it in my code to have a case for three values. Interestingly this gave a noticeable speed improvement.
Then I added some code for profiling to the rules so I could see how often each rule was called and how many numbers they could place so I got a feeling which rules were effective and which not. I played days with reordering the rules and created test loops to determine when to call which rule, when to fall back to backtracking etc. Once I had my laptop calculate complete two days to find the best values. I must say that the original algorithm was very good and my best results could only improve the result slightly. I even tried to apply two more rules but they did not give any improvements so I discarded them again.
I had a look at the generated Java code and could eliminate some additional lines. I too have added some other small improvements that save some CPU cycles like inlining the setValue Sub and added a new exit condition to a loop etc.
With all my tests with the fastest results (called in a loop so they were not the first run like Erel tested) around 11-13 ms per puzzle my goal was to get it below 10ms. After adding one rule which is quite cost intensive and is only called when the other, simpler rules only could place less than 7 numbers I managed to get results of 9ms sometimes. This was the point I stopped searching for any better solution and sent the project to Erel.
The final solution has three rules that directly place numbers on the board and two rules that reduces the allowed values for the fields on the board. These rules are called in a loop (with some additional conditions for some of the rules) until they couldn't place more than 5 numbers or more than 70 numbers of the whole board (with a total of 81 numbers) are placed. Then the rest is solved with a backtracking solution (which will again try to apply the rules if less than 70 numbers are placed).
Overall I think that the end result is slightly faster than the original code in B4A (About 10% to 20%. The solution with the library is still faster because of better optimized Java code I think.
Attached to this post is the solution with the original Java code as a library. Put the jar and xml files from the SudokuSolver_Library.zip to your B4A libraries folder to comile it. If you install the apk be aware that the program only makes log output.
The solution I have created for the contest can be found here.
