SudoRules’ Hidden Singles Reverse Engineered


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:

royle-17-3-tr

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.

royle-17-3-singles-trLet’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. 

royle-17-3-singles-remarks

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

After posting the 25 steps, your Royle 17-3 grid should look like this:

royle-17-3-after-25-hsI’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:

royle-17-3-hs-2-d-tr

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.

 

 

 

Advertisements

About Sudent

My real name is John Welch. I'm a happily married, retired professor (computer engineering), timeshare traveling, marathon running father of 3 wonderful daughters and granddad to 7 fabulous grandchildren. The blog is about Sudoku solving. It covers how to start, basic solving to find candidates efficiently, and advanced solving methods in an efficient order of battle. It is about human solving methods, not computer solving.
This entry was posted in Basic Solving Procedures, Berthier, Expert Reviews and tagged , , , , . Bookmark the permalink.

6 Responses to SudoRules’ Hidden Singles Reverse Engineered

  1. Strmckr says:

    Computer coders for solving use Rn,Cn, Bn,RC
    Space to represent the the grid, its very easy for it to replicate all strategies for human solving.

    It is based completely on human methods for solving and is coded that way.

    A hidden single for example
    Picks a cell in a sector
    examine all other 8 cells in that sector for a visible peer ” given” x candidate
    If all 8 cells see x then starting cell is a hidden candidate for digit x as it’s the only cell left that could hold candidate x.

    A naked single for example.

    Picks a cell in a sector
    Checks to see if cell is a peer to all but one number.
    That missing number is a naked single.

    In other words a
    hidden looks at off data for a sector
    and a naked looks at on data for a sector
    From a programmers stand point.

    Rn Cn Bn RC space is defined in Denis book,
    I personally have expanded this further for my own solver but that’s a comment to answer later.
    Cheers strmckr

    • Sudent says:

      Hi strmckr! It’s great to hear from you.

      Generation and maintenance of all candidates and three extra spaces, is smart solver coding, but it’s dumb human solving. Sysudoku makes that obvious. Denis claims hidden logic is his own invention. You could join me in disputing that.

      Be well, Sudent

      • Strmckr says:

        Cell Pencil marks are derived from
        Rn+Cn+Bn space
        There isn’t any extra space to maintained in this data setup. Pencil marks are an illusion to perception as they are a summation for the three constraints of the puzzle.
        Rn stores each potential digit saving Column intersections for The given row
        Cn stores each potential digit saving Row intersections on the given Colum
        Bn stores each potential digit saving (cell number) in the given box.
        Hopefully that gives you some insight to how it works as a manual solver (which is what I use as a manual solver and a coder to evaluate single digit space on a given constraint ei row, box, col with out needing all pencil marks written out) sure coded resources makes this process alot easier but what’s the fun in that!

      • Sudent says:

        Strmckr, you’re looking at the puzzle as a mass of organized data, and calling it manual solving.

  2. Strmckr says:

    RC,Rn, Cn, Bn space was stumbled apon by a manual solver on the enjoysudoko forum way back in early 2004 if memory servers me correctly.

    Basics mechanics for solving strategy was developed off those new insights and coders adapted the technique to improve run times.

    It also allows subsets Ext extensions in quicker time manually when you start dealing with one of these four spaces.

    As far as I’m aware Denise never claimed he discovered basic mechanics
    But dose claim his method is human based on increasing complexities as a guide.
    Which resulted, in an endless forum debate that I did post on as well stating it needed to branch and bound approach showing all valid ways a puzzle could be solved and rate each according and give a min, max and average solving rating.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s