# Is it possible to solve sudoku without backtracking?

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 9x9 cells and uses digits 1 to 9.

• I have come across puzzles in my own experience where there were no cells with exactly one "choice". That may have been me missing something, but I don't think it is possible to avoid backtracking on all puzzles. Jul 31, 2015 at 4:01
• @TerraHyde: Although I am not a regular puzzle solver (like one who solves sudoku daily), what I have found is that sometimes I feel hopeless in my approach and leave the puzzle as it. Then say by chance one week later I look at it and see some way of elimination which I missed and I am able to find a cell with unique choice. But then this is based on limited experience and I need a proper logical proof / refutation of my belief mentioned in my post. Jul 31, 2015 at 4:04
• I may be missing one, but this seems to have no single choice cells: en.wikipedia.org/wiki/… Jul 31, 2015 at 4:45
• You may be interested in playing with this solver. It's worth noting that 1) it has an extensive list of deductions it can use, including some that are too non-local to fit in the paradigm of "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", and 2) there are still some grids it can't solve (including the last few in the example popup). Jul 31, 2015 at 5:04
• @TerraHyde: does the wiki puzzle have a unique solution? If yes, I will try to use my technique to find a cell with unique digit Jul 31, 2015 at 7:29