Fill a 9 by 9 square that contains already some given numbers in a way, that every row, column and box contains all numbers from 1 to 9.
There are other rules to Sudoku, though they are not universally accepted. Around here we specify that a Sudoku puzzle must have exactly one solution. Many people also require that the placement of givens has some kind of symmetry, though we don't accept that one here. Some people further specify that the puzzle should be solvable by logic alone. Unfortunately that rule is poorly defined as brute force can be logically specified and solves all puzzles, yet these same people would not accept brute force solutions as meeting this rule.
a mathematical problem that requires a reasonable amount of logic to solve
Sudoku can be solved with trial and error alone, which many people argue is not logic. A substantial number of people who solve Sudoku puzzles do so with trial and error, even though we frown on that here.
This document addresses a reader already familiar with advanced Sudoku solving concepts that are capable of solving “hard” Sudoku puzzles. These are usually too difficult for humans and require computer aided procedures.
It is still an open question if there even exists a puzzle that is too difficult for humans. Certainly some of the most complex puzzles have been solved by human solvers, and it seems plausible that with sufficient effort any puzzle can be solved by a human solver.
There are a number of concepts for Sudoku that try to measure the severity of a Sudoku puzzle. All of these concepts are based on properties of the most complex elimination pattern only, afaik.
While difficulty measures that only depend on the most complex step are certainly popular, there are many difficulty measures that depend on all of the steps. Of course very very few of either kind are formally defined (unless you accept computer programs as formal definitions).
But we cannot ignore that something is missing, if all but one resolution step is ignored when calculating the severity. Solution paths usually consists of several hard elimination steps.
Why? You provide no justification for this claim either inside or outside your formalism. To my mind, this is an arbitrary decision, both answers are equally valid. That is really the fundamental problem with any effort to define a difficulty measure, it must inherently be based on numerous such arbitrary value judgements.
Sudoku Explainer by Glenn Fowler
Sudoku Explainer was developed by Nicolas Juillerat.
All of them give litte to none explanation, why a particular step was chosen in a situation.
"Little to none" does not seem appropriate to me. I've never seen a solver that gives no explanation for it's choice of solving step. Likewise I have never seen one that gives a complete formal definition (aside from it's source code). But nearly all of them give some fairly intuitive, though incomplete, explanation. For example Sudoku Explainer uses the most complex solving technique required where complex is determined by an ordered list of solving techniques (which is mostly, but not completely, documented) and the assumption that the easiest technique that makes forward progress is used at each step.
We want to assess the quality of a resolution path without using the information what rules or strategies are used to find it. Up to now there seem to be no convincing concept of comparing resolution paths of the same Sudoku problem. Although the claim “my eliminations are simpler” is frequently used in many discussions, a substantial definition of “simplicity” is painfully missing.
I believe that you are mixing up the difference between science and art. In science a formal definition of simplicity is indeed required to answer this question. But on this forum simplicity is defined in terms of artistic merit. In the same sense that someone might compare two paintings and ask which one is "better", we ask which solution is more beautiful.
Then they switch to recursion (brute force) or fail.
Recursion is not a good word to use here. For any recursive algorithm there is an equivalent non-recursive algorithm. Brute force is a much better phrase, as it at least captures the essence of what you are saying. However, brute force has never been formally defined in relation to Sudoku, so you are on slippery ground in any case. The dividing line between brute force and non-brute force methods has been long debated without any generally accepted resolution. It seems possible that the exact location of the dividing line might be another arbitrary choice. While it seems slightly more likely that complexity theory will eventually draw a hard line, we just can't say right now.
