Testing random problems
One big problem with testing these kind of solutions is that by nature, the problem is random and therefore will be different each time you test it. Unit testing can help – making sure each section produces the required behavior, but full testing is challenging since you have to reproduce the same scenario to fix problems. Certainly removing the randomness can help to start but ultimately you have to put that back in, since the ability to be random is part of what you are testing.
So I’m going to use soak testing. That means generating thousands of puzzles and making sure that what is generated is solvable, and that everything performs according to expectations. With recursion being involved, there is the added dimension of unpredictably caused by the potential for running out of stack pace if you recurse too many times.
Generating a pretty simple 3×3 puzzle right now is taking around 30 seconds average. Thats too long. It means that when i generate a 4×4 it will take an unacceptable amount of time, so I need to speed this thing up. I’d like to do that before I do the soak test to make best use of the testing time, and more importantly, so that I actually test the end product. My first step will be to profile a few areas using the autoprofiling tools from this site. I chose these to get started
Next I generated 10 puzzles to get these profile results
My first surprise is that isregionsolved is called so many times, and my second is that Slim is taking 52% of the total time. So I’ll have a look at those next.
After some tweaking, its taking about 5-6 seconds per puzzle generation, down from 30 seconds. Still too long, since we want to reduce the givens by a few more, but this is good enough to give the algorithm a good soaking. Most tweaks were to do with caching results, but i also made a couple of big changes. A big help was to change the random algorithms so they would return cells with the least number of possibilities first, and a complete change in the algorithm for finding sets. I can see that there is still some opportunities next in the xwing and xywing (which are really quite rare), so that will be my next target. Here are the new optimization results. I think a factor of 5 reduction is a nice start!
Generating several hundred sudokus showed no errors, and the average generation settled at about 5 seconds. Clearly this still needs some more work but it is good enough for now. . One problem with Sudoku generation is that you cant force a particular level of difficulty. You can generate one, and see if it’s difficult to solve. I will do some more work on this and on devleoping a difficulty algorithm for the next step. For the moment , I have added a simple solve or generate button, so we now have a fully functional tool available on the downloads page. I welcome contributions for optimization or plugins to solve particular strategies i haven’t got to yet.
For help and more information join our community, follow the blog or follow me on Twitter.