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.

  • 1
    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. – Terra Hyde Jul 31 '15 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. – Paramanand Singh Jul 31 '15 at 4:04
  • 1
    I may be missing one, but this seems to have no single choice cells: en.wikipedia.org/wiki/… – Terra Hyde Jul 31 '15 at 4:45
  • 2
    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). – Micah Jul 31 '15 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 – Paramanand Singh Jul 31 '15 at 7:29
up vote 4 down vote accepted

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.)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.