gsf's "A Ternary Monoid for Sudoku Coloring"

Advanced methods and approaches for solving Sudoku puzzles

gsf's "A Ternary Monoid for Sudoku Coloring"

Postby re'born » Fri Apr 13, 2007 2:52 pm

gsf,

Your article is very nicely done. I love the observation that double 3's acts as an identity. I have a few questions if you don't mind.

Firstly, you present a very helpful multiplication table:

Code: Select all
000 0      100 0      200 0      300 0
010 0      110 0      210 0      310 0
020 0      120 0      220 0      320 0
030 0      130 0      230 0      330 0
001 0      101 0      201 0      301 0
011 0      111 0      211 0      311 0
021 0      121 1      221 0      321 1
031 0      131 1      231 0      331 1
002 0      102 0      202 0      302 0
012 0      112 0      212 2      312 2
022 0      122 0      222 0      322 0
032 0      132 0      232 2      332 2
003 0      103 0      203 0      303 0
013 0      113 0      213 2      313 2
023 0      123 1      223 0      323 1
033 0      133 1      233 2      333 3


and write, for example that

gsf wrote:...a segment { 1-edge 3-edge 1-edge } (denoted 131) is equivalent to a single 1-edge.


In the case where the segment is even a tri-cycle, one obtains a 1-edge from the "exceptional" vertex to itself, implying that the vertex is not the induced subgraph color. Is this correct? The reason I doubt it is that this would imply that any of the combinations in your table that produce a 1 would imply that the vertex is not the induced subgraph color. But you only list 4 of the 7 as being able to make a coloring deduction. A similar situation occurs for tri-cycles multiplying to give you 2, where you would be able to deduce instead that the exceptional vertex is the induced subgraph color. Again, there are 6 such instances in the table, but you only point out 3 specific cases as causing deductions. I suppose what makes me most skeptical of my interpretation is the clearly nonsensical situation that occurs when the tri-cycles multiply to 3. For then you should simultaneously be able to deduce that the vertex is and is not the induced subgraph color.

To put my question a different way, when you write:
gsf wrote:This next figure shows the seven tri-cycles that provide coloring information.
Code: Select all
        (0)            (0)            (0)
        / \            / \            / \
       1   1          1   1          3   3
      /     \        /     \        /     \
     *---2---*      *---3---*      *---2---*


        (1)            (1)            (1)            (1)
        / \            / \            / \            / \
       2   2          2   3          3   3          2   2
      /     \        /     \        /     \        /     \
     *---1---*      *---1---*      *---1---*      *---3---*


(0) means that the vertex cannot be the induced subgraph color, and (1) means that the vertex must be the induced subgraph color.


why are these "the" seven tri-cycles...? What doesn't work, for instance, with

Code: Select all
       (0)
       / \ 
      1   3
     /     \
    *---2---*       

:?:

My second question has to do with your example:

gsf wrote:......5.9..7..462.....2..7......6.134.6...8.587.1......2..7.....358..2..1.8......

contains a few y-cycles and y-knots:

y-cycle 4 5 a/9 [96]-[66][65][25]=[98] => [96]-[78][98]-

denotes a Y cycle on color 4 of size 5 (5 vertices, 5 edges). 1-edges are denoted by "-" ([96]-[66]), 2-edges are denoted by "=" ([25]=[98]), and 3-edges are denoted by adjacent vertex labels ([66][65]). This cycle collapses to a tri-cycle with two 1-edges ([96]-[78] and [98]-[96]) and one 3-edge ([78][98]). From the tri-cycle figure above vertex (cell) [96] cannot be the color 4.


What is "color 4"? Looking at my pencilmark grid, it doesn't appear to be the number 4.

Have you already suppressed the links giving the 2-edge between [25] and [98] or is there a brutally obvious reason for them being 2-linked?

Using your multiplication table, I would view the above deduction as (133)21 =>121 implying the exceptional vertex, [96], is not color 4. Where does the tri-cycle [96]-[78][98]- come from? [78] isn't even in the original cycle.

Hmm. Maybe I will stop now and let you respond.
Last edited by re'born on Fri Apr 13, 2007 12:16 pm, edited 1 time in total.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Fri Apr 13, 2007 3:54 pm

rep'nA wrote:gsf,

Your article is very nicely done. I love the observation that double 3's is acts as an identity. I have a few questions if you don't mind.

thanks for starting the thread
first I'll clear up the bugs/typos and then deal with the first question, which probably means
the tri-cycle part needs more detail
rep'nA wrote:My second question has to do with your example:

gsf wrote:......5.9..7..462.....2..7......6.134.6...8.587.1......2..7.....358..2..1.8......

contains a few y-cycles and y-knots:

y-cycle 4 5 a/9 [96]-[66][65][25]=[98] => [96]-[78][98]-

denotes a Y cycle on color 4 of size 5 (5 vertices, 5 edges). 1-edges are denoted by "-" ([96]-[66]), 2-edges are denoted by "=" ([25]=[98]), and 3-edges are denoted by adjacent vertex labels ([66][65]). This cycle collapses to a tri-cycle with two 1-edges ([96]-[78] and [98]-[96]) and one 3-edge ([78][98]). From the tri-cycle figure above vertex (cell) [96] cannot be the color 4.
Have you already suppressed the links giving the 2-edge between [25] and [98] or is there a brutally obvious reason for them being 2-linked?


What is "color 4"? Looking at my pencilmark grid, it doesn't appear to be the number 4.

rats
that's why I called it a first draft
I fixed the note
in short its cycle number 4 (cycles are labeld from 1 .. n for the -Kc display option)
on color 5 of size 9
and like you noticed, the [25]=[98] 2-edge hides 4 multigraph bivalue edges that are traced with -v3
rep'nA wrote:Using your multiplication table, I would view the above deduction as (133)21 =>121 implying the exceptional vertex, [96], is not color 4. Where does the tri-cycle [96]-[78][98]- come from? [78] isn't even in the original cycle.

double rats
the -v2 trace looks wrong there
nothing like code review on the open web
hold off analyzing the example until its fixed

thanks
Last edited by gsf on Sat Apr 14, 2007 11:27 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Sat Apr 14, 2007 8:08 am

I corrected the draft note and and posted it here
I'll edit this copy to keep it up to date
---
A Ternary Monoid for Sudoku Coloring

Introduction
A traditional 9x9 sudoku puzzle can be modeled as a multigraph with 81 vertices, one for each cell, where the edges
represent the row, column and box cell value constraints between cells. The 9 cell values are represented as the edge
colors 1 through 9. A sudoku solution corresponds to a vertex coloring of the multigraph.

Edge Types
In this model there are four edge types for each of the 9 colors:
  • 0-edge: No relationship.
  • 1-edge: If one vertex is color c then the other vertex is not color c.
  • 2-edge: If one vertex is not color c then the other vertex is.
  • 3-edge: One vertex is color c if and only if the other vertex is not. A 3-edge is both a 1-edge and a 2-edge
    (conveniently 3=1+2).
In some sudoku formulations 1-edges and 2-edges are considered weak and 3-edges are considered strong.

Color Induced Subgraphs
Each color induces a subgraph (a graph, not a multigraph) on the original multigraph that can be examined
independently. In particular, some edge configurations can be shown to admit or preclude the induced color on
constituent vertices. The remainder of this note assumes edges in the color induced subgraphs.

Edge Relationships
Two edges that share at least one vertex are adjacent. Adjacent edges can be joined to form a path. A
cycle is a path where every edge is adjacent to two other edges. The cycle size is the number of edges in the
cycle. The smallest cycle size is 3. A segment is a subset of edges that form a path. Segments of size three
(three edges) can be combined to form a new edge according to the following ternary "multiplication" table on the four
edge types:

Code: Select all
      000 0      100 0      200 0      300 0
      010 0      110 0      210 0      310 0
      020 0      120 0      220 0      320 0
      030 0      130 0      230 0      330 0
      001 0      101 0      201 0      301 0
      011 0      111 0      211 0      311 0
      021 0      121 1      221 0      321 1
      031 0      131 1      231 0      331 1
      002 0      102 0      202 0      302 0
      012 0      112 0      212 2      312 2
      022 0      122 0      222 0      322 0
      032 0      132 0      232 2      332 2
      003 0      103 0      203 0      303 0
      013 0      113 0      213 2      313 2
      023 0      123 1      223 0      323 1
      033 0      133 1      233 2      333 3


For example, a segment { 1-edge 3-edge 1-edge } (denoted 131) is equivalent to a single 1-edge. 0 is the
multiplicative zero: a 0-edge in combination with any other two edges is equivalent to a 0-edge. From a coloring
viewpoint 0-edges provide zero information. The multiplicative identity element is an adjacent pair of 3-edges:
adjacent 3-edges in combination with any other edge type is equivalent to that edge type.

Ternary Monoid
A monoid is a set with an associative operation on the set elements that also contains an identity
element. Edge multiplication operates on three edges, hence ternary. The ternary operator is closed, a
monoid requirement. This particular monoid also has a multiplicative zero element.

Relationship to Coloring
Cycles are the key to extracting coloring information. Using ternary edge multiplication any odd cycle can be
collapsed into a tri-cycle (cycle of size three). The next figure shows the seven tri-cycles that provide coloring
information.

Code: Select all

        (0)            (0)            (0)
        / \            / \            / \
       1   1          1   1          3   3
      /     \        /     \        /     \
     *---2---*      *---3---*     (1)--2--(1)

        112            113            233

        (1)            (1)            (1)            (1)
        / \            / \            / \            / \
       2   2          2   2          3   3          2   3
      /     \        /     \        /     \        /     \
     *---1---*      *---3---*     (0)--1--(0)     *---1--(0)

        122            223            133            123



(0) means that the vertex cannot be the induced subgraph color, and (1) means that the vertex must be the
induced subgraph color. The tri-cycles 111 and 222, and any tri-cycles containing 0-edges do not provide any
assignment/elimination information. The 333 tri-cycle is self-contradictory and therefore impossible in a valid
sudoku. This accounts for the 10 tri-cycle forms: seven provide assignment/elimination information, two are
inconclusive, and one is contradictory.

The disposition of a vertex in a tri-cycle is determined by the multiplication table entry for the three adjacent edges:
  • 0 => inconclusive (*)
  • 1 => the vertex cannot be the induced subgraph color (0)
  • 2 => the vertex must be the induced subgraph color (1)
  • 3 => contradiction
Another observation on these diagrams: for any tri-cycle replace 1 edges with 2 edges and vice versa,
and replace (0) with (1) and vice versa, and the result is a valid complementary tri-cycle. The complements
appear above/below each tri-cycle in the diagram above.

Cycle Coloring Algorithm
The cycle coloring algorithm is simple:

  • Induce a subgraph for each color.
  • Determine the type 1,2,3 edges.
  • Combine edges into paths until odd cycles are formed.
  • Collapse each odd cycle into a tri-cycle using the ternary multiplication operator. If the tri-cycle matches one of
    the seven forms above then apply the color elimination or assignment.

X and Y cycles
X cycles contain 1-edges and 3-edges. Y cycles contain all edge types. Even though all edge types correspond to one
color in the induced subgraph, 2-edges are formed by bi-value vertices in the original multigraph, and then mapped
into the subgraph. A bi-value vertex can admit only one of two colors. A single 2-edge consists of one or more edges
between bi-value vertices in the multigraph, where both endpoints contain the induced subgraph color.

2-edge construction can lead to contradictions in the multigraph (and not by cycles in the induced subgraph). These
contradictions are called y-knots.

The Algorithm in Action
Download my solver and run it with the -v2 option on some puzzles known to require/contain coloring, turbot
fish, kites, and or skyscrapers. The X and Y cycles are labeled, and the collapse from full cycles to tri-cycles is
denoted by "=>".

For example, this puzzle
Code: Select all
  ......5.9..7..462.....2..7......6.134.6...8.587.1......2..7.....358..2..1.8......

contains a few y-cycles and y-knots:

Code: Select all
  y-cycle  5  9  6a [21]-[71][92][97]=[33]-  =>  [21]-[97]=[33]-

denotes a Y cycle number 5 on color 9 of size 6 (6 vertices, 6 edges). Cycle numbers may be passed to the -Kc option
to display cycles in postscript. In the cycle output, 1-edges are denoted by "-" ([21]-[71]), 2-edges are denoted by
"=" ([97]=[33]), and 3-edges are denoted by adjacent vertex labels ([71][92]). The size for x-cycles and y-cycles
includes sizes for segments hidden by 2-edges and box hinges (described below). e.g., [97]=[33] contains some
bivalue edges not displayed in the -v2 trace. -v3 lists the y-edge details, which for [97]=[33] is:
Code: Select all
  y-edge      9  3  [33]1[37]3[97]9

(color 9, size 3, no edge type notation between vertices). This cycle collapses to a 112 tri-cycle: two 1-edges
([21]-[97] and [33]-[21]) and one 2-edge ([97]=[33]). From the 112 tri-cycle figure above, vertex (cell) [21] cannot
be the color 9.

Code: Select all
  y-cycle  4  5  9a [96]-[66][65][25]=[98]  =>  [96]-[78][98]-

denotes a Y cycle number 4 on color 5 of size 9 (9 vertices, 9 edges). The [25]=[98] details (listed by -v3)
are:
Code: Select all
  y-edge      5  6  [25]1[29]8[79]1[78]8[18]3[98]5

(color 5, size 6). This cycle collapses to a 113 tri-cycle with two 1-edges ([96]-[78] and [98]-[96]) and one 3-edge
([78][98]). From the 113 tri-cycle figure above vertex (cell) [96] cannot be the color 5.

This cycle exposes a deficiency in the y-cycle trace. The algorithm collapses edge segments as it progresses and must
emit hints for cycle reconstruction. In some cases the reconstruction may trace artifacts of the algorithm rather than
the actual segments from the original cycle. -v5 displays the original edge triplets (four vertices) that are
used by the reconstruction. In this case the following triplets were used (to seemingly pull [78] from thin air):
Code: Select all
  y-trip 190  5     [96]-[25][65]-[78]
  y-trip 184  5     [78][98]=[25][65]

Although the display may seem incorrect, the underlying logic is sound.

This y-knot
Code: Select all
  y-knot   8  1  9z [25]5[34]3[14]7[54]2[56]7[16]8[18]3[29]8[22]5[25]5

is number 8 on color 1 and contains 9 vertices/edges. The y-knot premise is that the first cell is not the color ([25]!=1). In
this case it leads to the contradiction [22]=5 and [25]=5; therefore [25]=1. y-knots are essentially y-edges gone bad.

Pseudo Edges
The beauty of the ternary edge collapse algorithm is that only edge types matter, not how edges are derived.
2-edges show that edges need not follow intuitive paths through a sudoku puzzle grid. There are other 1-edge
derivations besides cell [rc] sees cell [r'c']. One such derivation is the box hinge illustrated by this puzzle:
Code: Select all
  6..8352.9.89.......5219..8.92..8.7.383.9..4..41..23896.983.........7893...3.591.8

    6     47   147  |  8     3     5   |  2    147    9
   137    8     9   | 2467   46   2467 | 356  14567  1457
    37    5     2   |  1     9    467  |  36    8     47
  ------------------+------------------+------------------
    9     2     56  | 456    8    146  |  7     15    3
    8     3    567  |  9     16   167  |  4    125   125
    4     1     57  |  57    2     3   |  8     9     6
  ------------------+------------------+------------------
   1257   9     8   |  3    146   1246 |  56  24567  2457
   125    46   1456 | 246    7     8   |  9     3    245
    27   467    3   | 246    5     9   |  1    2467   8

If [79]=4 (cell r7c9 is color 4) then [78][76][75]^4 (cells r7c568 are not color 4) and one of [84] or [94] must be 4,
which implies [44]^4 and [24]^4. Hinges are traced by -v4:
Code: Select all
  x-hinge     4  8  [79][44]

which denotes and x-hinge on color 4 in box 8 with cells [79][44]. x-hinges are treated as normal 1-edges by the
ternary collapse algorithm. Here is the x-cycle that incorporates the hinge:
Code: Select all
  x-cycle  1  4  6a [79]-[39][36]-[46][44]-  =>  [79]-[46][44]-

The cycle size 6 includes 1 for the hinge. Tri-cycle type 113 means that cell r7c9 cannot be color 4, denoted this way
in the trace:
Code: Select all
  X1  [79]^4

which reads: 1 X cycle elimination; r7c9 cannot be color 4.

Conclusion
The literature has no concrete (i.e., useful) examples of ternary monoids or other algebras. My original notes on this
are dated 2005-10-21 -- talk about writer's block.
Last edited by gsf on Wed May 30, 2007 2:28 am, edited 4 times in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: gsf's "A Ternary Monoid for Sudoku Coloring"

Postby gsf » Sat Apr 14, 2007 8:14 am

rep'nA wrote:gsf,
Your article is very nicely done. I love the observation that double 3's acts as an identity. I have a few questions if you don't mind.

thanks
its a draft to invite questions and corrections
rep'nA wrote:why are these "the" seven tri-cycles...? What doesn't work, for instance, with

Code: Select all
       (0)
       / \ 
      1   3
     /     \
    *---2---*       


this is a mirror image of one of the 7 tri-cycles, so it does work
the ones that don't work (provide eliminations or assignments) are 111, 222, 333,
and tri-cycles with any 0-edges -- I fixed the note to emphasize this, thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Fri May 04, 2007 9:11 pm

Two questions, without having studied as carefully as I should've:

1. What about even cycles? A - B = C - D = A, for example, has four edges and implies (back of the envelope ...) that A equals C and B equals D. Does your ternary thing help there?

2. How do you choose which nodes to lose when collapsing a cycle? Is it possible to collapse one way and fail to reach a conclusion, but collapse another way and succeed?

I must also say that the presentation could be clearer. There's no need to talk about colouring multigraphs; it's just a recipe that (a) can be used to reduce chains of any type of logical proposition, but (b) seems to work particularly well when the propositions are all of the type "cell foo has value bar" (for variable foo, fixed bar).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Wiring diagrams

Postby Red Ed » Sat May 05, 2007 8:36 am

Here's a more general, binary, method from which the basic (but perhaps not all?) aspects of your scheme can be derived. I don't claim for a moment that it's any better; perhaps the beauty of your ternary monoids is that they use only the parts of the more general method that are likely to be encountered in real life. Whatever, this is just food for thought.

We'll use the following notation:
  • A ~ B means A equals B
  • A - B means A NAND B (weak link)
  • A = B means A OR B (strong link)
  • A ^ B means A XOR B (type 3 link)
  • A > B means B IMPLIES A (subset notation, so for example 0>1 is false)
  • A < B means A IMPLIES B
The A's, B's etc. are any logical proposition as you might find in AIC or similar.

Now we need two multiplication tables, one for links in series, one for links in parallel (to use an electrical analogy).

The first table tells us how to convert A (rel1) X (rel2) B to some relation (or possibly no relation) between A and B. I'm too lazy to write down the whole table now, but it has rules in it that look like this for example:
  • A - X = B is equivalent to A < B
  • A < X - C is equivalent to A - C
  • A - X - C is equivalent to (no relation)
  • etc.
From this you can deduce, for example, that A - X = Y - B is equivalent to A < Y - B is equivalent to A - B, which is well known to AIC people.

The second table tells us how to resolve A (rel1) B and A (rel2) B to some relation between A and B (or even to resolve their values). Again, laziness is reducing my contribution to mere examples at this stage:
  • A < B and A > B is equivalent to A ~ B
  • A - B and A = B is equivalent to A ^ B
  • A - B and A < B is equivalent to A ~ 0
  • etc.
Now we can resolve ternary monoids. For example, A - B - C = A is equivalent to A - B < A (series rule) is equivalent to B ~ 0 (parallel rule).

We can also use this series/parallel model to resolve the even cycle A - B = C - D = A given earlier, since then A < C - D = A (series), A < C < A (series), A ~ C (parallel). Or if I resolve if by reducing B = C - D first then I end up with B ~ D.

The question is: which approach - binary or ternary - is better in practice?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Steve R » Sat May 05, 2007 1:29 pm

I wonder whether the list of edge types might sensibly be extended:
• 4-edge: If one vertex is not color c then the other vertex is not color c.

The extension would bring in near-fish links. For example:

Code: Select all
+-----------------------+
¦ . . . ¦ . . . ¦ . . . ¦
¦ . . . ¦ . . . ¦ . . . ¦
¦ . x . ¦ . x . ¦ x . . ¦   Only three cells for x in this row
-------------------------
¦ . . . ¦ . . . ¦ . . . ¦
¦ . . . ¦ . . . ¦ . . . ¦
¦ . x . ¦ . x . ¦ . . . ¦    Only two cells for x in this row
-------------------------
¦ . . . ¦ . . . ¦ . . . ¦
¦ . x . ¦ . . . ¦ . . . ¦
¦ . . . ¦ . . . ¦ . . . ¦
+-----------------------+

If r3c7 does not contain x, an x-wing is formed so r8c2 does not contain x.

Such links find their way naturally into nice loops (via r3c7 = x- r8c2) since they preserve all the usual propagation properties and I think it would be a pity to leave them out of the new analysis.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Red Ed » Sat May 05, 2007 2:01 pm

Steve R wrote:I wonder whether the list of edge types might sensibly be extended:
• 4-edge: If one vertex is not color c then the other vertex is not color c.
Let:
  • A = "one vertex has colour c"
  • B = "the other vertex has colour c"
Then in my framework your 4-edge is equivalent to ...
  • A > B
... but I can't see how that is catered for in the ternary monoid model.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Mon May 07, 2007 4:48 pm

just back from KY with H.M.
will respond early tomorrow
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Wed May 09, 2007 4:54 am

gsf wrote:just back from KY with H.M.

mini vacation put me back farther than I planned ...
I'll address the recent comments in this post with a little background peppered in

first, thanks for the comments

the multigraph maps one to one to the pm grid
the vertices are the grid cells
edges with label c are between cells in the same row/col/box with label c in the pm grid
the induced subgraph for label c is the pm grid restriced to label c -- exactly the grid used for "fishy" analysis

I prefer using multigraph/induced-subgraph and associated graph theoretic terms instead of "x sees y" etc. in the pm grid domain

along with the (now refuted) singles backdoor conjecture, my big contribution to sudoku
(way back when I joined the forum) was going to be a cycle-based unification of x-wing
and friends (thus X-cycles) with the assorted fish (why not aim high -- work still in progress)

initial work covered x-wing but not all other *fish forms
it was based on { 1-edge 3-edge } combinations
I looked at binary edges operations, but that introduced a bunch of new edge types that
didn't have a direct counterpart in the pm grid
ternary edge operations introduced only 1 new edge type { 2-edge }, which maps directly to
degree 2 (bivalue/bilocation) chains in the pm grid (or equivalently multi-valued edge chains
in the multigraph)
the four edge types { 0 1 2 3 } along with the ternary operator produces a (closed) algrebra

a binary formulation may cover more sudoku properties, but also introduces more complexity

other edge types, like a 4-edge (if one vertex has value c then the other vertex has value c),
are not ternary, and are covered as combinations of { 1 2 3 } edge types in the ternary algebra

the main property of the 4 edge types is that the edges, and paths/chains formed by
adjacent edges, are by definition undirected (or equivalently, bi-directional)
I'm pretty sure this is not the case for binary multi-value/color formulations

a neat property of the cycle algorithm based on the ternary algebra is that it splits into
four distinct and independent phases:
(1) identify all simple type { 1 2 3 } edges
(2) combine edges to form cycles
(3) collapse odd cycles to form tri-cycles
(4) apply eliminations/assignments corresponding to the tri-cycles

a good point brought up by Red Ed is the significance of application order of the ternary edge operator
when collapsing odd cycles to tri-cycles
it turns out that a different sequence of collapses can produce a different tri-cycle type
this could mean the difference between an elimination vs. an assignment
(in general assignments are more productive in the solution process)
the ternary collapse algorithm currently does not take this into account
it also reduces every odd cycle, no matter how large, to one tri-cycle, potentailly missing
some eliminations/assignments in the original cycle -- I had originally thought that any
elimination/assignment along a cycle would cover (via say singles propagation) all of the
other (implied) eliminations/assignments in the cycle
its good to review old work -- this will be improved

Red Ed also brought up even cycles
first note that the mere existence of an odd cycle that collapses into one of the 7 tri-cycle
types, produces eliminations/assignments, no propositions to prove or disprove
(the tri-cycle eliminations/assignments occur at the tri-cycle vertices)
not so for even cycles
these can collapse to bi-cycles (two vertices, two edges) where one or both vertices can
take on the induced value and still satisfy the edge properties
but note that adjacent 1-edges always form cliques of size 3 or larger
suppose the bi-cycle is:
Code: Select all
     (a)
     /  \
    1    3
     \  /
     (b)

here one of (a) and (b) must have the induced value, and the other not,
so no vertex elimination/assignment information gained there
but there is an implied clique for the 1-edge between (a)(b), and none of the
other vertices in the clique besides (a) and (b) can have the induced value,
so the induced value can be eliminated from those vertices
(even cycles are currently ignored by my implementation -- always room for improvement)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Wed May 09, 2007 7:58 pm

OK, thanks for that. I played around a bit with the binary model, using matrices M such that Mij is the relation between node i and j and then trying simple matrix algebra to "solve" sets of binary relations. It sort-of worked, but wasn't looking especially positive (matrix multiplication being non-associative over this non-ring, ho hum) so I gave up. Happy to cheer on the sidelines if/when you get further with your monoids.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby StrmCkr » Thu May 10, 2007 6:58 am

isn't this method similar to using dancing links, where it test "values" in each cell looking at sub set sum values = 0 proving the contradiction.

(colors = value tested) for subset sum errors in reduced(imposed) subgrids.?
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby gsf » Thu May 10, 2007 7:16 am

StrmCkr wrote:isn't this method similar to using dancing links, where it test "values" in each cell looking at sub set sum values = 0 proving the contradiction.

(colors = value tested) for subset sum errors in reduced(imposed) subgrids.?

dancing links (DLX) is Knuth's tree search data structure
used on problem instances where guessing is required to progress the solution

there's no guessing in the cycle analysis
if a cycle exists then so do its eliminations
(just like swordfish etc., if a swordfish exists then so do its eliminations)

the search for structure (like cycles or swordfish or naked pairs) is entirely different than
a search over guesses
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Thu May 10, 2007 7:56 am

i never mention it was a guess.

i was implying that if said events are a cotradiction by testing the cycle = true/false then the sub set sum = 0

i know dancing links evauates subset sums = 0 by testing all candidates at each and every spot in a problem untill all subsets don't produce contradictiosn (o solutions) thus the cells are correct

. problem is no one really knows exactly how it works.

im suggesting that it tests cycles as you are doing in a controled manner rather then all checks.

for subset sums equalling false and removing that propositon from test cell. and carries on.

i view your method as a branch / good off shoot approach similar to dancing links in the above mannerism.

looks promising. keep it up.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby gsf » Thu May 10, 2007 2:21 pm

StrmCkr wrote:i never mention it was a guess.
looks promising. keep it up.

thanks and aha
I saw dancing links and assumed guessing before reading deeper
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next

Return to Advanced solving techniques