Is there a tip to solve the most difficult sudokus (for example if you have 3 candidate digits)?

Answer

Dear Hugo,

Below is a short and long answer to your question:

Short answer:
Yes, first try the choice that limits the possible values ​​for other cells as much as possible (or even better determined). This will usually give you the least amount of work, but not always.

For example, standard techniques to disable as many choices as possible can be found here:

http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/

Long answer:
The sudoku puzzles as we know them from magazines and newspapers always have 3×3 regions that consist of 3×3 cells. If we generalize this to NxN regions with NxN cells, we can study its difficulty by seeing how much more difficult the problem becomes as we make N larger. This problem has been shown to be NP-complete. This means that while we can easily check whether a given solution is correct, we know of no strategy that is significantly better than going through all the possibilities to fill in the cells (and there are exponentially many such possibilities relative to N ).

Nevertheless, you can use a strategy to narrow that exponentially large space of possibilities by using small tricks that allow you to quickly see that certain choices can never lead to a solution. If we can thus limit the possible choices for a cell to 1, we fill them in.

One such trick, if you have several choices to fill in a cell, is to take the choice that is the most restrictive, in other words the choice that limits the possibilities for other cells as much as possible.

In fact, it is that principle that we automatically apply when we try to solve a sudoku puzzle: we look for that cell where we can see in the simplest way possible which number should be. So we normally choose a cell whose number of possible values ​​is limited as much as possible and apply the principle further by seeing whether the number we just entered further limits the possible values ​​of other cells.

Unfortunately, even this method cannot be guaranteed to be the least amount of work in the end — that’s why I called it a trick. In computer science, such a trick that usually works well is called a ‘heuristic’.