“Can each 9*9 Minimum Sudoku with exactly one solution be solved by logic?”

Nobody knows. It’s even worse: Humans know little about Sudoku.

Thousands of people play with the idea of writing a Soduku solver- or generator-program and set it in practice.There are hundreds of web-pages with solvers to be found in internet. To develop, test and debug a logical solver (not a brute force routine) it takes at least one year of development time (except you copy and/or modify a freeware). To my observation most of the people give up this programming exercise after 1 – 3 years as they reach a dead end. They might continue, when they have commercial interest or if they are extremely enthusiastic or when the exercise has some relation to their professional life (e.g. scientists). I would see myself in the middle.

The logically hardest possible Sudoku can be see in the upper left corner. It is  Black Swan *) and will be found in the next 1, 10, 100 or 1.000 years or so. All known hard Sudoku puzzles today are result of trail and error and something like good luck. When we will consider here, how many soduku puzzles exist (I'm not talking about Sudoku grids (Felgenhauers figure)) we understand that there is a lot of room for invention new puzzels and hard, very hard new puzzles. I will consider the question, why hardness has not improved since more than 5 years and how it comes, that maximum hardness is still remaining on a level of 11.9 SE and no harder Sudoku have been found since 2007.

*) The Theory of Black Swan is a metaphor that encapsulates the concept that an event is a surprise (to the observer) and has a major impact. It is hard to predict. After the fact, the event is rationalized by hindsight.

If you look for a nice Sudoku to solve – you are definitely wrong here. Sudoku I will present aren’t the ones you will most likely find in your newspaper. They are not easy, not medium, they are not hard. I wouldn't call them findish and/or diabolic. They are hard in a sense that humans can’t solve them by logic but only by trail-and-error. This doesn’t mean that they can’t be resolved by logic at all. If humans can’t machine can and/or could do it possibly.

Millions of people are solving a newspaper Sudoku just for fun. Newspaper-Sudoku are rated in easy, medium and hard – in rare cases they are published as findish or diabolic.

To have progress in Sudoku, I’m convinced that we need a better understanding of Sudoku Generation (SG). SG is trail-and-error so far and not a logical procedure. After generating a random puzzle (bottom up – method) a logical Sudoku-solver and/or brute force routines will ensure 5 properties of the new puzzle

·      Validity (more than 0 solutions)

·       Puzzle has exactly one solution (less than 2 solutions)

·         Givens left out create a puzzle with more than 1 solution (minimum puzzle)

·         Puzzle has the property logic

·         Puzzles to be published will have a rating below SE 9.0 – because Newspapers don’t like to frustrate their readers

I’ve been checking Sudoku from the world champion ships, 17ers and handmade Sudoku from Japan (considered as extremely aesthetic for their symmetry and adored as diamonds of human mind - from some people). The truth is that all this stuff to a certain surprise is only light weighted in terms of hardness.

One of the most famous Sudoku solver programs is still Sudoku Explainer (SE). It’s a standard, but it has its deficiencies. I will use SE-rating exclusively as a term of reference here and mention other standards only shortly and give arguments why I’m not using them.

The property logic depends on the logical techniques (Sudoku solution theory) incorporated in a solver. There are up to 50, but in any case less than 100 known logical techniques (pattern based) to solve 9*9 Sudoku by logic. Off course SE is not using techniques developed after 2007, but as it is still able to solve all known Sudoku and it makes almost no difference for the rating of hard Sudoku if some additional new and simple logic have or haven’t been incorporated. Rating of hard Sudoku in SE depends on chains.

Information on Sudoku solution theory in internet is an almost endless ocean. New techniques are coming in and very few disappear from the information pool, e.g. because a technique is found to be a subset of another technique. There is also a lot of confusion about naming and wording and sometimes techniques are only to be found different by naming and not by content. Most of the scientists I spoke to see that amateur work with some suspicion.

Rating of Sudoku is under dispute in the family. Many of those who write a solver like to have their own rating, but most logical Sudoku solvers fail to solve all known 9*9 Sudoku by logic but incorporate some kind of trail-and-error (e.g. a technique called bowman bingo) in their “logical” solution process. This is today’s hardest known Sudoku – Golden Nugget (SE 11.9).

Golden Nugget (SE 11.9) by Tarek 01/2007

Don’t try to solve it – you will only be successful by trial-and-error and not by logic. It is remarkable that this unofficial world record (SE 11.9) has not been broken for more than 5 years. This happens in an age where computer power still develops according to Moore’s Law. In so far it’s remarkable that the record date (01/07) is almost falling together with termination of the Pentium development by Intel. As we will see later creation of hard Sudoku needs an exceptional calculation effort. But it seems not to be supported significantly by multi core processors and the respective programming techniques. Of course this is more my observation rather than a prove. It could be that there are no harder 9*9 Sudoku. But when we later analyze the upper limit of the number of possible Sudoku puzzles, we will better understand that the probability for this becoming true (Max SE rating = 11.9) is very, very low.

Between 2005 - when Sudoku started to get very popular - and 2007 - when golden nugget was created -  there was a short period with lots of activities in forums and other communication platforms on the question of the hardest possible Sudoku. Amateurs and professionals have been dealing with this question and there was constant progress for some time. But then the development got stuck and many of the “heroes” changed their focus of interest, as there was no further progress foreseeable. Some of their comments seem to indicate some kind of disillusion after a powerful start.

Sudoku Explainer (SE) from Nicolas Juillerat (2007) was the first and is still one of the few logical Sudoku solvers that can solve all known 9*9 Sudoku by logic and by a technique called Dynamic Forcing Chains. Juillerat writes in one of his very few comments:

Can the Sudoku Explainer really solve all Sudoku? In theory: no, because none of the solving techniques it uses can be proven to solve every Sudoku. In practice, when the version 1.2 of the Sudoku Explainer was released (November 2006), there was no Sudoku it could not solve. But in the future somebody may eventually find a Sudoku harder than all the previous ones that the Explainer will eventually fail to solve. …”

Having written that, Juillerat closed his Sudoku period and seems to deal now with some more serious and scientific topics. There are no newer comments from him after 2009 – at least not to my knowledge.

The first sentence is important, because it indicates that we have no complete theory, why Sudoku can be solved by logic. But can all 9*9 Sudoku be solved by chains? Of course they can, if chains get up to 81 elements long. But then we have an exponential increase of calculation time, when Sudoku get larger (16*16, 25*25, …) and chaining would be not logical according to a definition of Eppstein (see below). The more precise question therefore is: Does chaining reduce the problem in all cases and lead to a polynomial calculation time?

The last sentence of Juillerat is even of more interest for this page, because we can also answer the question “Can any 9*9 Sudoku with exactly one solution can be solved by logic?” from a practical point of view. If we knew that there is no more difficult Sudoku to be found, we simply could use the solver and would have an exact rate for the maximum hardness.

Each logical technique implemented in SE has a value between 1.0 and 20.0 on the rating scale. A higher value correlates in principle to more logical conclusion steps are required for a single technique. For details and theory of logical Solution techniques and for critics on the SE scale read more here.

Solving a Sudoku by logic means that SE is using the technique with the lowest rating possible for the next step in the solution process. At the end of the whole solution process the Sudoku is rated according to the highest rate of a technique used in the whole process.

What makes a Sudoku hard? There is a convention in the Sudoku family that Sudoku with an SE rating beyond 9 + are hard Sudoku. Comments from various sources indicate that only 1 of 100.000 randomly created Sudoku exceeds the 9.0 SE boundary, but for a 10.0 + Sudoku a much higher calculation effort is needed and there are only a few thousands know (and published) so far.

Many logical Sudoku solvers are created with the intention to support and train humans in the logical solution process. Solution techniques with a rating under SE 9.0 are most likely based on patterns – like Pairs or Fishes, etc. Techniques above SE 9.0 are based on chains and they have no clear pattern. Also SE explains the logical solution of a hard Sudoku e.g. Golden Nugget by logic, i.e. by chains, there is no hope that humans can use those chains. Chains can only be found efficiently by computers as there are too many branches in a “search tree” of a Sudoku solution.  

My investigation of the recent development (2008 and later) of solution techniques in internet seems to indicate, that there is almost no progress in replacing chains by simpler techniques. E.g. Hodoku one of the most elaborated solvers and a masterpiece of good documentation and design has by far more than 50 techniques incorporated, but it is still unable to solve Sudoku beyond the hardness of SE 9.2 – 9.3 without trail-and-error.

However the more general question is: Are chains some kind of logic at all? In a correspondence with Prof. Günter  Rote  (2010) from University Berlin he mentioned that David Eppstein defined as one criteria for a logical algorithm that it is able to find a solution in polynomial time. Some authors like Denise Berthier (the hidden logic of Sudoku) raise the assumption that chains need exponential calculation time as they get longer. But there is no final prove.

Let us start with open question about Sudoku here

Let me say a final word to style. It’s a very good approach to define principle objects of the Sudoku matter like givens or equally clues, rows, columns, blocks or cells like notation specifics and like names of various patterns like pairs and triples and other solution techniques, like chains or nets, and so on and so forth.

For the moment I will leave that step out. I assume that if you have read until here you have some background with the topic what replaces the need of definitions to some degree. Whenever I see a need for definitions to understand the information provided, I give cross reference to a respective definition by a hyperlink. Sorry I’m lazy, but I will try to eliminate this failure stepwise. My assumption is that you will not suffer from this deficiency – except you are in the wrong article anyway.