Currently I have a sudoku puzzle solver program and I've tried all the puzzles I can find that are labeled the "hardest" on various sudoku video games and puzzle books. My solver has solved them all. It currently uses the following 4 polynomial time rules (i.e. polynomial time if the board was $N^2 \times N^2$ instead of $9 \times 9$).
1) Check each cell to see if only one value is possible for the cell
2) Check to see for each row/column/block whether there is a value that only one cell can have
3) Check to see for each row/column/block whether there are 2 cells that can only have the same 2 values. (Then no other squares in the same group can have those values)
4) For each row/column and block that intersects it, see if there is a value that can only appear in the intersection 3 cells either for the row/column or for the block. Then no other squares in the row/column or block can have that value.
After these rules are applied repeatedly, if the puzzle is not solved, then the program guesses a value for a cell and sees if this leads to a solution or contradiction when the above four rules are applied repeatedly. If a contradiction is found, then the value is removed from the possible values for the cell. This guessing is applied separately for each cell+possible value if the number of possible values for the cell is 3 or less. There is no simultaneous guessing for multiple cells. If at least one possible value is removed for some cell, then the above 4 rules are again applied repeatedly until guessing is required again. And repeat. If it ever happens that the 4 rules and guessing don't provide any additional information, then the program gives up and prints out the partial solution it found.
Now, there are about 10 or 20 different polynomial time rules that have been devised to rule out possibilities and infer cells' values in sudoku, and I only implemented 4. Furthermore, the guessing only guesses one cell's value at a time and merely removes the value from the possible values for the cell if a contradiction is found. So it's weird to me that this solves all the hardest puzzles I can find. Can someone produce a puzzle hard enough that my program can't solve it?
In response to the OP's request I'm posting this as an answer - although all I did was happen to know of a place where he found a puzzle that defeated his algorithm.
Peter Norvig's lovely essay here - norvig.com/sudoku.html - discusses the design and (Python) implementation of his sudoku solver. Whether or not it answers your question about backtracking recursion depth its worth a read. – Ethan Bolker Jun 19 at 19:03
@EthanBolker thanks for the link. Norvig definitely allows guessing at a "depth" (number of guesses made simultaneously) greater than 1. But it seems he only uses 2 very basic polynomial time deduction rules, whereas I use 4. He did mention a few of his hardest puzzles, although some of them have multiple solutions and some of them have none. In my paradigm (and most Sudoku player enthusiasts' paradigm), we assume that a puzzle has exactly 1 solution. Some of his "hardest" puzzles had this property. I'll try them out and see what happens. Thanks again for the info. +1. – user2566092 Jun 19 at 19:34
@EthanBolker If you post this as an answer, I'll accept and award the bounty because the one puzzles out of Norvig's 95 "difficult" he posted that took the longest time for his solver to solve was not able to be solved by my solver. Also he provided a link to "hardest Sudoku" that led to a puzzle by Inkala that my solver also failed on. – user2566092 2 hours ago