Your post made me realise that I had said nothing about who can do what with my Sudoku program. Basically I wrote this purely for my own amusement and to share with the community. So, basically anyone can use the program or its source code for any purpose whatsoever. If you or anyone else wants to recycle any of the code, please feel free to do so. The only slight caveat to this is that I made use of the following code which may impose some restrictions.
1) The cursor handling code was taken from the cc65 runtime library.
2) The RLE unpack routine came from CodeBase64.
Both were tweaked very slightly.
But if you're only interested in the solving algorithms, neither of these are required.
In theory you could repurpose the solver to check that your generated puzzles (I looked up your original thread and read your paper) are solvable once cells are blanked out. However, there are some traps along the way...
I've been using the term "deterministic solution" to mean a solution that can be found by logic only, no guessing and recursion.
1) The aim of my program is to find a valid solution to the entered puzzle, not necessarily the only valid solution. It will halt as soon as it finds the first valid solution. In this respect only a deterministic solution is sure to be unique (depth = 0 in the status panel).
2) The solver is less sophisticated than a competent human solver. From time to time it will come up with a different solution. This arises when the solver gets stuck BEFORE the human solver and starts recursing. Where there are mulitple solutions from that point, the solver might not pick the same solution as the human. This is most noticable when a human solver can arrive at a deterministic solution but the solver cannot. This behaviour is less noticable in v0.4 where I added an extra algorithm, but I have seen one case in the last couple of weeks where I was able to solve it deterministically but the solver required one guess. However in this case (which I should really have made a note of) we arrived at the same solution. This extra algorithm is still only looking one step ahead, whereas a human may manage more steps.
3) Mitigating this by only accepting deterministic solutions in your program does mean that more complex puzzles will be rejected as unsolveable. You can implement this by removing the recursive section from procedure SolvePuzzle in Core.asm, which is the code from label guess: onwards.
4) I'm trading memory for speed. The program makes heavy use of lookup tables (over 2K just for the solver), which might be an issue if you are still targeting a cartridge solution.
5) The recursive solver can use a lot of memory and it does not check if it is running out. If you compare the memory used by test cases TC1.SUD and HARDEST.SUD (or get it to solve a blank grid) you'll get an idea of memory used by recursion.
You could perhaps make use of the status values to rank puzzles in order of complexity. Some combination of pass count and the number of cells inserted in each pass (fewer = harder) might be a useful metric.
Hopefully this is clear and of some help.
Edited by EdwardianDuck, Wed Sep 23, 2015 1:59 PM.