OK, there’s something I have to confess. Up until now there have been 10,000 puzzles in the database. But of those 10,000 only 76 were classified as “hard” … As I wasn’t quite satisfied with this, I started work on an algorithm to make harder puzzles. The algorithm worked, but took way to long to make a new puzzle. Our basic algorithm for solving puzzles works fine for valid sudoku puzzles (i.e. puzzles that only have 1 unique solution), but takes a lot longer to exhaustively search the entire solution space of any grid. After some research I found a java-implementation of Knuth’s Dancing Links algorithm (check wikipedia) by Stan Chesnutt (check his page here). I translated it to PHP (all my pages & algorithms are written in php so far), but after 3 evenings of debugging my code, I found that my php-translation of the Dancing Links algorithm was even slower than my original implementation. Stan’s original (java) code however, was very fast. So I decided to rewrite my php code to java, and use Stan’s classes for solving puzzles in the process.
I finally got the new classes to work last night, and I’m very satisfied with the results. My php program constructed about 100 puzzles in 1 hour on an Intel Core 2 Duo 1,8 GHz, way too slow to my liking. But the new java implementation takes only 3 to 4 minutes to make 100 puzzles on my old iBook G4 1 GHz. I haven’t even bothered installing the Java Virtual Machine on my Core 2 Duo PC yet, but I suspect it will construct the same 100 puzzles in less than 2 minutes.
All I have to do now is find a way to feed the java output to the MySQL database and I’ll be upping the 10,000 puzzles to 100,000 very soon. Then there should be about 700-800 “hard” puzzles.