Here, Denis Berthier’s trace of a SudoRules basic level puzzle in his The Hidden Logic of Sudoku is reverse engineered to show how it finds hidden singles. Although the method is related to line marking, it is not a practical model for human solving.
Before the heavy lifting, let’s checkpoint the homework with a sysudokie trace of the bypass plowing under Royle 17-3:
In case you missed any of these:
N1m dublex xhatch dublex SW1m => NW1, SE1 is a 6f:c7 hidden single(hs) , S5m xh NE5m => SE5,
N wall => N2, SW2 is a 3f: r8 hs, W3 is a 4f: c2hs, C7 is a 4f:r6hs, the SW square => SW3,
NW6 is a 4f:r1hs, NE5 is a 3f: r1hs.
In THLS every technique is called a resolution method, and is a set of rules of a given level of logical complexity, added to all simpler rules. Royle 17-3 is the first puzzle introduced in THLS, because it is solved with singles, hidden and naked, the least logically complex set of rules. All SudoRules consist of a condition to be met, and an action to be taken, either the removal or confirmation of candidates.
Rules are stated this way, because solving begins with each cell containing candidates of all values. From there, SudoRules starts with the first four rules, Denis Berthier’s Elementary Constraint Propagation rules. The very first ECP rule removes all but the given clue from the clue cells. The next three remove candidates of the given clue number from the three containing units, the row, column and box. This is appropriate computer coding for number scanning.
It may be hard to believe, after the bypass homework and checkpoint, that Royle 17-3 can be solved by singles only, but if we understand this, we will better understand what experts are talking about when they dismiss a puzzle by saying “only singles from here”. For one thing, a cross hatch clue can be interpreted as a hidden single in the box under attack. And a clue we attribute to a dublex is also a hidden single in the line. In the checkpoint trace above, the wall and the square are just names we apply to restrictive patterns of clues that make the cross hatch or dublex work. Puzzles collapsed by the bypass without higher order subsets, we can consider to be solved by singles, although our bypass is much more interesting.
Fortunately THLS gives us a trace of the SudoRules solving of Royle 17-3, on pages 84-85. I’ve reproduced part of the trace here, with each step identified as a hidden single in the right column. For hidden singles in lines, the number of free cells are displayed.
Let’s use this trace to reverse engineer the sequence of basic operations of SudoRules. Fill a copy of the puzzle, as you read down the table and the comments below on each step. That way, you have the state of the grid on each comment.
After posting the 25 steps, your Royle 17-3 grid should look like this:
I’m sure you noticed that in spite of having all candidates available, many solving opportunities are missed. That is due to the restriction to singles, ignoring all higher order subsets, slinks and aligned triples. I think you can agree that adding rules to cover basic and advanced solving, even if all known techniques are covered, will not create a manual for human solvers.
Actually, by putting all of the “depends on” observations together, we can see how SudoRules sequences through its hidden singles. To make that easy, I’ve added step numbers in the 2-D dependence tree:
It’s clear that SudoRules doesn’t start over after posting each hidden single. It mimics our 2-D trace in several ways. The hidden single rules are applied to each of the containing units, for all incomplete numbers, but only one is followed up on the grid at a time, the rest being held for later. In the lists for posting, singles of the same number are followed up first. Although a box was chosen over a line at first, boxes are not taken ahead of lines in later lists, so it appears that grid location of the single may be a tie breaker.
So how is the SudoRules manner of finding hidden singles so different from ours?
A hidden single occurs when there is only one cell left in a unit for a missing number. We scan the grid, seizing on patterns that point to such an occurrence. The human solver does best with a variety of visual tools and less data to process at one time. To us, data not being applied is distracting clutter. We hate boring tasks like number scanning and use line marking only as much as we have to. Computer solvers start with number scanning. As we saw, SudoRules uses the same code for hidden singles for lines, from 2f: to 9f. The fact that it takes us a very large amount of unproductive scanning to do this, just doesn’t matter.
Computer code embodies both a sequence of operations, and the data supporting these operations. Tracking the numbers left for each cell makes the appearance of a naked single when adding a clue immediately known. The setup for that is to number scan candidates before beginning.
The detection of hidden singles can be made as simple, with unproductive scanning drastically reduced, with the right data. Just track, within each box and line, the number of cells left for each number. As the grid is updated for a new clue, reduce these counts. Hidden singles in the containing units announce themselves. Track the location of candidates, or search for the single after it announces, it makes millisecond difference.
Read that paragraph again. It reveals that what we have been interpreting as number scanning, and eliminating cells in boxes and lines to reveal hidden singles, is actually simpler. It is a routine performed for every given clue, and then for every new clue as it is discovered. Update the count of the number in all three containing units, as each candidate is eliminated, making a list of units reaching 1. Then locate and promote the single in the list. Making this happen by interpreting a set of rules is more computationally complex, but not enough to matter.
On the other hand, what does the code and supporting data for the detection of dublexes and cross hatches, squares and walls look like? Not anything like that simple. SudoRules, although driven by sets of rules, another form of data, works like conventional computer code, and not like any human solver.
We learn something surprising about naked singles in the next post, where we will continue the Royle 17-3 trace into naked single territory. To watch it happen, we have to number scan the grid above, to recapture what candidates remain from the original number scan of the givens that SudoRules did, and made little use of, to this point. If you need to find out what this is like, that’s your homework assignment. At least its less burdensome that doing the number scan, then the ECP eliminations, yourself.