I occasionally solve sudoku puzzles on smartphone in spare time. My approach is based on the belief that at each stage in solving a sudoku puzzle there is at least one cell where there in only one choice of digit which satisfies all the constraints. And then I proceed to find one such cell and fill it with the suitable unique digit. This way the problem looks deterministic.
Some other approaches use backtracking. This is typically used when you have a cell which has two choices of digits based on current data and you put one of the choices in the cell and after sometime if you discover any contradiction, you backtrack and fill the cell with other choice.
If there is a sudoku puzzle with unique solution then can it be shown that there is at least one cell at each stage of the puzzle which has only one choice of the digit without using any backtracking?
In other words will the following procedure work?
Start with any empty cell. Eliminate the digits which are not suitable for that cell by looking in the row, column and the smaller square to which the cell belongs. If there is only one digit which fits this cell then fill it with that digit. If there are multiple options move to another cell and repeat the same logic. It is guaranteed that you will have one cell with only one choice of suitable digit. This way fill all the empty cells.
I have highlighted the word eliminate in last paragraph because sometimes the elimination of digits gets tricky. One common scenario is that by various constraints you can fix two digits of a row (column) into one of the sub-squares and thereby these are eliminated from the remaining part of the row (column).
Note: Just to clarify the sudoku I am talking is the usual one based on 9×9 cells and uses digits 1 to 9.
Best Answer
Using only the techniques you mention in your initial post (i.e. only Naked Singles and Hidden Singles), you can solve about 29.17% of all the minimal 9x9 Sudoku puzzles. However, much more "pure logic" or "pattern-based" solving (without any backtracking) can be done by using more complex resolution rules, either "classical" ones (Pairs, Triplets, ...) or more recently defined ones (whips, braids, ...). There is a fundamental classification parameter for puzzles, the Trial-and-Error depth. For all the known 9x9 puzzles, it is 0, 1 or 2. If it is 0, the puzzle can be solved by (Naked and Hidden) Singles only. If it is 1, it can be solved by braids only. If it is 2, which may happen for about 1 minimal puzzle in 30,000,000, more complex patterns are necessary (B-braids). Needless to say, all the puzzles you can find in newspapers or in apps on your smartphone require much less than the full power of depth 1.
The same classification works for larger puzzles, but the maximum Trial-and-Error depth is higher and the proportion of puzzles with small depth decreases fast with size. (For more detailed information, see my book "Pattern-Based Constraint Satisfaction and Logic Puzzles". A free pdf version is available.)