Sysudoku Traces

A distinctive and extremely useful feature of Systematic Sudoku is its efficient and reproducible marking and tracing technique.  Marking is the recording of the effects of a change on the puzzle grid.  Tracing is the separate recording of the solving actions in text form, allowing a reader to reproduce them exactly.  Tracing is useful for the human solver, in that the exact departure from a solution can be identified.  An efficient and unambiguous tracing technique allows a Sudoku author to publish completely reproducible results in a practical amount of space.  And most valuable of all, tracing is a resource for learning how to solve Sudoku puzzles in the least burdensome, and most pleasurable way.

Frequently in this blog, you are challenged to solve an example puzzle up to a point where a technique is illustrated.  In the next post, a checkpoint solution is given, not only with a diagram showing where you should be in the solution, but also a trace showing how I got there. The trace tells each exact step, but it is up to you to figure out why that step works.  You read the what, and supply the why.  Short and sweet.

A trace is a record of cause and effect.  It starts the change on the grid, a cause, or a list of causes.  For each cause, the trace lists its immediate effects. Then the effects of each cause are listed. The effects of a cause are listed below it, indented to the right. Effects become causes, and  causes and effects cascade left to right and down the screen or page.

There are two ways to do this. Ordinary Sysudoku traces, the two dimensional, or 2-D traces, generate lists in breadth first order.  All effects of a cause are listed at once, but effect become causes one at a time, left to right across the list. A series of lists string out, down the page, but shifted left to right, until first effects as causes have no effects.  Then the second effect on the bottom list becomes a cause.

That happens on every list.  All the cascaded effects of previous causes on the list are explored in depth, before the immediate effect of a cause are listed, if there are any left.

When a list of causes are all explored, the trace continues on the list immediately above it with the next cause to the right.  When writing the trace, the cause is pulled over to the right, to allow its effects to cascade down.

This looks complicated in words, but when you apply them to blog traces, it becomes simple.  Unless your trace has => in it.  An earlier posts, list followed causes in left to right text with nested parentheses to mark the lists. My apologies for the 1-D trace.  Eventually I’ll get them all converted to 2-D form.

Sometimes the trace slides off the page, and I have to bring a section back left below. I try to pick the right place to do that, preserving the ability of causes above to be explored.  One trick is maximize the window and do the whole thing before any editing.

What Effects?

If you’re curious about traces, you know that I name boxes for compass points, and designate rows and columns by lower case “r” and “c”.  I assume you’re reading the trace by filling in the grid as you go, so I don’t have to say where in the box a new clue is going. The box and number is a clue.  A slink pair in a box is an ‘m’ for marks.  Following the trace, you know where slink marks should go. Aligned triples are a ‘t’.  In a box marking list, everything is about the current number, so I don’t have to put that in.  You know about the cell marking positions along the top, corners and sides of the cell.  It’s very compact and readable.

Here is the syntax of abbreviations used for effects in the Sysudoku blog traces:

trace abbrevsAnything else should be spelled out.

Bypass traces only record clues and other closed sets as effects.  I drop the number headings and just separate the number lists by commas.

Writing a Sysudoku Trace

Why would you ever want to write such a trace?  Suppose you solve a challenge puzzle from a forum or  website, such as Andrew Stuart’s “Unsolvable” series.  Or you could have cracked a monster puzzle in a new way.  You could transmit it to fellow sysudokies for checking before putting it out there.  Me, I locate mistakes with traces, and I make a lot.

Simply for the sake of communication with traces and diagrams, I try to follow these conventions on the order of operations:

Numbers 1 – 9 and boxes left to right and top to bottom in the bypass and box marking.

In effect lists, all the cause number effects first, then by increasing number, regardless of position. Not the only choice but easy to remember. In line marking, order by increasing cells to fill, considering sets in the line as filled in the line.

The Sysudoku Trial Trace

There is a specialized sysudokie trace that traverses lists breadth first, instead of depth first, and for a good reason. The trial trace generates a list of effects for each cause on each list on the same line, left to right, before going to the next line.

It explores all immediate effects on the same logical level (trace line) simultaneously, casting for a contradiction in the smallest number of levels. Ultimately,  most of the results will be discarded.  The point is to find the shortest logical path from the assertion on trial to a contradiction.

Here is a trial trace from the solving of Insane v.4, b.7, N.5 in review of the Insane collection of www.krazydad.com .

IN 475 AIC traceA promotion of a 4-candidate in the NE box would imply the clues in the effect list of the next line.  Working left to right, each of these clues gets one effect before the first one, NW6, is taken as a cause.  The SW9 effect SW3 is a cause, before the first SW6 effect gets to be one.  The tree includes the assertion that the cluster color blue is true, adding three effects to the SW6 list.  The contradiction between clues S2 and C2 is the first one encountered by this tree.

IN 475 AIC trial gridWith the trial trace completed, we can now ignore effects not essential to this shortest path, and make this graphical representation of the effects essential to it.  The net result is that the NE4 assertion is rejected, but with a fully documented reason.  The complexity of this reason reflects the complexity of this puzzle. Note  that one essential node of the logical chain is a hidden triple!

Advertisements

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