3D deconstruction of 9x9 Sudoku provides key to rules

Bob Hanson

[This message refers to standard 9x9 Sudoku, not some sort of 3D analog.]

I have been studying the page developing out of ATT Research at

http://www.research.att.com/~gsf/sudoku/

This is really fascinating. This page attempts to classify constraints into different subclasses, namely "X", "Y", and "W", among others.

I wonder if anyone else has noticed that what this page refers to as "X-constraints" and "Y-constraints" are simply two different projections of a 3D deconstruction of 9x9 Sudoku, where each candidate number is on its own plane, stacked "vertically" above the plane of the board.

See, for example, the interactive 3D model of Sudoku at http://www.stolaf.edu/people/hansonr/sudoku.

Thus, while "X-constraints" focus on a specific candidate number (horizontal slice of a given color on the 3D deconstruction), Y constraints simply extend this to the vertical dimension, where we envision each candidate possibility to be on its own plane.

This suggests no fundamental distinction between "X" and "Y" constraints. Indeed, if one treats a "verticallizing" cell of the Y-constraint examples as a vertical strong edge of a standard cycle, then all rules relating to "X" constraints apply to Y constraints. (Which means, of course, that there are several more subclass examples of Y-constraints.)

Similarly, "W" constraints along with certain X-constraints are simply subset elimination (generally considered ONLY in a vertical sense) done horizontally. Or, to put it another way, allowing X and W constraints to act vertically we have subset elimination.

Thus:

A) "X-constraints" are simply a subset of "Y-constraints."

B) Certain "subset eliminations" and "X- or W-constraints" are one in the same, done in different planes. (hidden pairs and naked pairs are simply two different orientations of Xwings; hidden/naked triples are simply two different orientations of swordfish, etc.).

What I don't quite understand is why people are focusing on "cycles". Yes, cycles are created, but the essential characteristic of a "strong edge" is not that it makes a cycle, but that it determines a "parity" for a subset of the board. An alternating "grid" of points is produced which may or may not be cyclic. It really doesn't matter. When this parity check delivers a logical inconsistency due to an incompatibility with another parity check from another source on the board, we have an elimination. (To be fair, that "form another source" involves a cycle.)

Except for the fact that a weak edge is necessary to separate two "ends" of a strong chain in a particular row, cell, or block, there seems to me no need to focus on them. Thus, for example, Rules X1 and X3 simply state the same thing -- that any cell of a given candidate possibility k being acted upon by two cells of opposite parity must be eliminated. (Because one or the other must then be true.) In the one case we have a weak edge because the cell is in the same column as the two ends of the strong sequence; in the other it is in a column and a block. I guess I don't see the point of making that distinction -- a dependency, whether row, column, block, or cell is just the same fundamentally. This is precisely the principle in the discussion for Y constraints, of course.

At the above web page I show how all this cycle business can be dispensed with. -- at least programmatically. So, for example, noncyclic "W constraints" are the basis for all subset elimination carried out by this web application code.

Please don't get me wrong. The cyclic analysis is brilliant and clear. I think in terms of human solving, the cycle business is a nice trick. I just hope people aren't trying to figure out all the ways to generate all the possible cycles, or to think that you have to find the cycles to solve a Sudoku, although in some cases I guess this could be valuable. Maybe all I'm saying is what everyone already knows: that the cycle analysis is just a shorthand for what I think people call "coloring". (But I'm unclear about that.)
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Lummox JR

dukuso · Posted: Thu Oct 13, 2005 7:01 am Post subject:

(the link doesn't work for me]

don't we get these symmetries gratis with the exact-cover method
("dancing links, DLX) ?
So, when you try to formulate swordfish etc. in binary-matrix-
speak, you should get the symmetric rules automatically.
(I haven't tried, don't even know what swordfish is)

Lummox JR · Posted: Thu Oct 13, 2005 6:32 pm Post subject:

The exact-cover matrix actually operates a bit differently than the 9x9x9 cube. For example, you can use this rule in DLX which is an equivalent to pointing pairs or box-line intersections, but applies to all exact-cover problems:

If all of the choices for constraint A also satisfy constraint B, all other choices that satisfy B can be eliminated.

Swordfish is best understood in the context of a binary grid, and finding subsets. To find a naked or hidden triple, you'd slice the cube in a different direction or take a box section and get a different 9x9. If you sliced the cube so that the columns of the 9x9 grid are digits, and the rows are the positions in a house that they can occupy, a hidden triple appears where in 3 columns of the grid, the only possible choices occupy only 3 rows. Similarly a naked triple finds 3 rows whose only possibilities occupy the same 3 columns. Swordfish is identical to this except it slices the cube into a single digit 9x9 grid where the columns and rows are the actual columns and rows of the puzzle. A swordfish can be found by either columns or rows. X-wing works the same way, but it only finds a pair of columns/rows rather than 3 or more of them.

gsf

dukuso · Posted: Fri Oct 14, 2005 3:59 am Post subject:

>The exact-cover matrix actually operates a bit differently than
>the 9x9x9 cube.
>For example, you can use this rule in DLX which
>is an equivalent to pointing pairs or box-line intersections,
>but applies to all exact-cover problems:
>
>If all of the choices for constraint A also satisfy constraint B,
>all other choices that satisfy B can be eliminated.

(B=A|B)==>B=A
you see, how easy it is formulated with exact-cover-speak ?
you could even use A<=B for B=A|B ("|" for "or" as in C)

>Swordfish is best understood in the context of a binary grid,
>and finding subsets. To find a naked or hidden triple,
>you'd slice the cube in a different direction or take
>a box section and get a different 9x9. If you sliced
>the cube so that the columns of the 9x9 grid are digits,
>and the rows are the positions in a house that they can
>occupy, a hidden triple appears where in 3 columns of the grid,
>the only possible choices occupy only 3 rows. Similarly a naked
>triple finds 3 rows whose only possibilities occupy the same 3
>columns. Swordfish is identical to this except it slices the
>cube into a single digit 9x9 grid where the columns and rows
>are the actual columns and rows of the puzzle. A swordfish
>can be found by either columns or rows. X-wing works the
>same way, but it only finds a pair of columns/rows rather
>than 3 or more of them.

since in exact-cover the constraints are only listed and not
distinguished you needn't slice the cube into different
directions. (rotate) Once you formulated it for one
"direction" you have it for all the others.

"choose the cell with fewest candidates"
would be in exact-cover : "choose the column(=constraint)
with fewest ones(=satisfying placements).
This would not only include cells with fewest candidates
but also e.g. symbols with fewest possible positions in a block etc.

Or did I misunderstand the cube and we have the possible
candidates for a cell as 3rd coordinate ?

Lummox JR · Posted: Fri Oct 14, 2005 4:25 am Post subject:

dukuso · Posted: Fri Oct 14, 2005 12:16 pm Post subject:

here is my attempt to describe subsets (naked or hidden,
that's the same here) in exact-cover-speak.
In fact, it's even more general but for sudoku it would
probably essentially reduce to naked/hidden subsets.
I pretend, that probably most constraint programming
with alldifferent can be done more nicely in exact-cover-speak,
but I couldn't find whether anybody had already tried this.
I had email with W.vanHoeve, he wrote a large online-survey
about alldifferent constraints, but wasn't even aware that these
can be transformed into exact-cover problems, nor had he
any reference for this.
I'd really like to know, whether this sort of formulation has been
described elsewhere.

----------Definitions:
exact-cover problem:
given a binary n*m matrix A with n rows and m columns,
find a subset S of the rows which sums to the all-1-vector.
Row r is adjacent to column c, iff A(r,c)=1
("placement r satisfies constraint c").
Let _S be the set of all solutions.

Two rows(columns) are called adjacent, iff there exists a column(row)
to which they both are adjacent.
For a set D of columns(rows) let N(D) be the set of all rows(columns)
adjacent to any column(row) in D.

The exact-cover problem is being solved by recursively selecting some
row r, deleting columns N({r}) and rows N(N({r}) and thus
reducing it to a smaller exact-cover problem called E(A,r).
Just deleting row r without any other changes gives problem E(r)

For any column c, the exact-cover-problem A has a solution S,
iff there exists r in N(c), r in S such that the reduced exact-cover problem
E(A,r) has the solution S-{r}.

---------------subsets-theorem :
Let D be a set of k different,mutually nonadjacent columns.
Assume N(D) partitions into k disjoint sets R1,..,Rk
each consisting of mutually adjacent rows.
If r is a row not in N(D) but adjacent to all rows in R1 then
_S=_S(E(r)) , so r can be deleted.
proof:
This is because placement r would delete all of R1 but none of D.
Any subsequent placement q in Ri deletes all of Ri and one of D,
so one in D would be left without adjacent rows.

In case of sudokus,the Ri would typically be given as subsets
of neighbor-sets of some columns ci adjacent to D. Ri<=N(ci).

example: (r:row,c:column,s:symbol, "851" is short for r8c5s1)
suppose after some placements block 8 has these candidate-sets:

Bob Hanson · Posted: Fri Oct 14, 2005 3:09 pm Post subject:

Thank you all for contributing here. I see now that I had mistakenly read that description of Y-constraints -- I could suggest some alternative wording that does not include the issue of "exactly two in a given row/column/block". This I think is what threw me off.

Continued success in Sudoku Assistant: http://www.stolaf.edu/people/hansonr/sudoku

This morning I realized that X and Y constraints are indeed simply two flavors of the same thing -- one operating in the plane of the board (X) and one operating perpendicular to it (Y). (Thus, Glenn's Y-constraint entry into a cell with two values {a,b} via {a} and leaving via {b} amounts to the equivalent of THREE X-constraint-like edges, where the a--b switch is one strong edge. (Exactly like a strong naked pair edge in a row/column/block in the case an X-constraint.)

I think I've successfully implemented those now with no "cycle" aspect (at least programmatically), just parity. With one caveate -- I'm not checking for weak links between independent chains the way Glenn Fowler describes. (One odd sequence with weak links to n even sequences....) That amounts to phasing the independent chains so that they contribute to a whole. (Or, just bridging the chains....oh, funny.... sure....I see...too easy! Oh, my!)

I think the connection to multicoloring probably relates to what I am going to say next:

I would like to call my chain-strategy "M" for Medusa. Rather than thinking of cycles, I suggest thinking of the problem in relation to a network of snakes, similar to Medusa's head.

http://www.class.uidaho.edu/mckeever/images/caravaggio_Head%20of%20Medusa.GIF

As these snakely chains wind their way through the 3D cube, they pick up dependencies all over the place -- in every row, column, and block they pass through. The X- and Y- constraint business simply capitalizes on this.

A general "M" strategy would merge these two separate "X" and "Y" labyrinths into one.

A generalization to triples would I suppose take me fully into the world of multicoloring. For example, one could start a binary chain with a triple and see where it leads. A 3-point Medusa search would show up incompatibilities between alternative pairings and perhaps disallow one of them. (Note: still just two colors, I think. Maybe not, though?)

I'll admit to (a) not being a mathematician and (b) working too fast for my own good here. Thanks in advance.

Enjoy.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr