Finally found the bug in my backtracking algorithm, in which I again forgot to delete a cell if a invalidation occurred.
Now, I can optimize my backtracking algorithm by limiting the number of backtracks by only applying moves to possible values than trying all 1…n values. That should limit the branching factor.
Now, I just need to create the data necessary to test all these algorithms.
First, with backtracking and backtracking with CPS, QQwing will generate n puzzles of easy, medium, and hard, and diabolical levels. These two algorithms will be timed, and their branching factor will be measured. Also, each algorithm will solve the Al Escargot puzzle n times and determine the average branching factor. Also, it would be neat to reverse/shuffle the order of values possible in the cell and see if that makes a difference.
Lastly, I will use that same data to test my human logic solver against a large number of Sudoku puzzles of various difficulties and see how many can be solved. Each puzzle should take no more than a second, so I will limit the time the human logic solver can take per puzzle. The program will keep a count of how many puzzles were solved out of those that were skipped. It is more than likely those puzzles that were skipped couldn’t be solved using the human logic solvers, and needs to be searched for the answer.
Mooshu's Blog 