This post begins a sysudokie reading of Denis Berthier’s weighty and challenging treatise on Sudoku, The Hidden Logic of Sudoku, or in this report, THLS. I start with an overview of the agenda of the book, which  differs greatly from the human solving theme of the Sysudoku blog.

Most of the examples in THLS come from an exhaustive collection of puzzles with 17 given clues, compiled by Gordon Royle.  Here is Royle 17-3, the only one for which Denis explains his basic level solution in detail.

I’ll checkpoint the sysudokie basic solving next time. The bypass is all that is necessary, but for reasons of my own, please include SE1 as the second new clue, even if you don’t normally examine 6f: lines in the bypass. The THLS solution, compared to your bypass, suggests why this book offers little direct help for human solvers, although it offers considerable innovative material on Sudoku.

THLS begins with an amusing account of what happens when a scientist trained in formal logic and the rule based technology of artificial intelligence encounters the addicting fascination of Sudoku.  The book dates back to 2007, and was preceded by an era of rule based AI machines called expert systems.  In this early AI era, practitioners would deeply interview experts with commercially valuable, but hard to transfer knowledge and mental skills. They would codify these abilities in a set of rules.  Then, when the experts were no longer available, these software systems could function in the same way, asking the right questions, classifying the situation, and providing answers.

Quite naturally, a teaching scientist in the AI field would be attracted to Sudoku solving as a practice problem for students of rule based Artificial Intelligence. But on a deeper level, such an individual is also compelled to understand how to encapsulate human expert Sudoku solving in a set of rules of an AI engine.   In that endeavor, Denis writes of his frustration at the lack of well defined expertise on which to build a set of rules.  Instead, he turned to a very different goal: to develop Sudoku solving rules for a rule based solver he calls SudoRules. Berthier’s solver takes advantage of implied, but normally hidden structure of Sudoku, and ranks puzzles in order of increasing “logical complexity”.

I wonder what Berthier would have done with an opportunity to evaluate Sysudoku solving, with its Order of Battle and constructive techniques, as a model of expert human solving. Would he have been drawn into the project of emulating the ideal sysudokie with a rule based expert system?

From the Sysudoku perspective on human solving, the following quote is significant:

It is easy for readers of THLS to be misled by such statements.  And I doubt its writer believes “simulating human solvers” is what his solver is doing. This review will demonstrate the contrary.   In the quote above “relative efficiency” means the level of complexity of the rule set that solves the puzzle. But this is a very subjective definition, burdened with a detailed theory of logical complexity of interest to very few. The generally understood meaning of relative efficiency is more related to computational complexity, the number of operations needed to solve a problem of a given size. Computational complexity is the critical factor separating human and computer solving methods.

In the case of Sudoku puzzles there is a problem with computational complexity. There is no agreed upon measure of size. In Sysudoku, as a substitute measure of computational complexity, puzzles are ranked by how long they hold out against the Sysudoku Order of Battle. The SOB methods are subjectively ordered by increasing computational complexity, including searching and construction in its operations.

Berthier’s SudoRules is yet another computer solver, exploiting the inhuman ability to execute millions of instructions in less than a second. The next posts will uncover the elephant in the room, that the execution of rules in increasing order of logical complexity does not simulate what any human solver should attempt to do, much less how an expert solver would do it.

A major factor is that solvers like SudoRules are not coded to exploit the visual pattern recognition ability of the human solver. Enlisting these abilities to construct solving patterns is a primary way humans overcome computational complexity.  In his introduction, Berthier mentions the “great gap between abstract logical complexity and psychological complexity for the human solver.” Working with an expert solver, in the manner of an expert system practitioner, might have led him to some surprising psychological discoveries.

The next two posts will reverse engineer Denis’ basic solving technique of your homework puzzle, Royle 17-3. It is solved by L1-0, the logically most simple rule set of SudoRules. L1-0 is revealed to be too narrowly focused to serve as a basis for human solving.  Beyond that, the Berthier order of battle continues into advanced techniques following the abstract notion of increasing logical complexity, and departing seriously from a reasonable track of increasing difficulty for the human solver.  The logical complexity agenda also leaves serious gaps in the SudoRules advanced techniques repertoire. These gaps damage the credibility of Berthier’s claim for his “hidden logic” rules such as:

While such claims, and Berthier’s carefully crafted presentation of Sudoku as a logical structure, has led readers to believe that THLS is an instruction manual for human solvers, it was clearly not intended to be that. As I said above, human solving is not its goal, though I wish it had been.

On the other hand, there is fiercely independent thinking, with novel approaches worth examining for practical solving ideas. In the review I will avoid the issues of logical representation of rules, and explain what I understand in THLS in a manner familiar to Sysudoku readers.

Do your homework.