exact-cover-speak is better than sudoku-jargon

dukuso

I was trying to reformulate sudoku-rules in
more formal exact-cover-speak.
If you like this, please help to extend this list
and advance sudoku-theory !

Given the binary exact cover matrix A(n,m), R={1..n},C={1..m}
for a row r in R and a column c in C let
N(r):={c in C, A(r,c)=1} and N(c)={r in R, A(r,c)=1}
and #c:=#(c):=|N(c)|.
For a set X of rows and a set Y of columns let N(X) [N(Y)]
be the union of the N(x) [N(y)] with x in X [y in Y]

A solution is a subset S of R which sums to the all-1-vector.
Let Sol(A) be the set of all solutions.
A row r can be "removed", if it is not in any solution S.

Choosing a row r propagates to another smaller matrix A(r) with
columns N(r) and rows N(N(r)) removed and Sol(A)=r+Sol(A(r)),
where r+X:={x\/{r}, x in X}.

Just deleting a row r from A gives the matrix denoted by A-r

some results:

(0) r in N(c) <=> c in N(r)
(1) if c in C with #c=0 then Sol(A)={}
(2) "FN","singles",
if c in C, r in R; N(c)={r} then Sol(A)=r+Sol(A(r))
(3) if c1,c2 in C ; #c1=#c2=1 ; N(N(c1))/\N(N(c2))!={} then Sol(A)={}
(4) "Jaap1" follows from (6)
c1,c2 in C ; N(c2)>N(c1) ; r in N(c2)-N(c1) then Sol(A)=Sol(A-r)
(5) "Jaap2"(generalized)
r1,r2,r3,r4 in R ; c1,c2 in C ; N(c1)={r1,r2} ; N(c2)={r3,r4} ;
r3 in N(N(r1)) ; r4 in N(N(r2)) ; r in N(N(r1)) /\ N(N(r3)) ;
then Sol(A)=Sol(A-r)
(6) "Bo1", "block-block-interaction"
r in R ; c in C ; c not in N(r) ; N(N(r))>=N(c)
then Sol(A)=Sol(A-r)

soduko · Posted: Sun Nov 06, 2005 2:30 pm Post subject:

Interesting suggestion

Where can i find a formal description of exact-cover-speak?

Or if this is all there is to a formal discription can you give some worked out examples.

dukuso · Posted: Sun Nov 06, 2005 3:16 pm Post subject:

it's very fundamental, so you need no preliminarities.
You can have a look at :
http://magictour.free.fr/suexco.txt

it's so nice and basic, that I assume there should already be papers
or books about this stuff, but I don't know where to search.

soduko · Posted: Mon Nov 07, 2005 1:33 pm Post subject:

Sorry it is not that simple

dukuso · Posted: Mon Nov 07, 2005 1:56 pm Post subject:

>Sorry it is not that simple
>
>>Given a binary matrix A(n,m) with m columns and n rows
>>find all subsets of the rows which sum to the all-1-vector
>
>What is an all-1-vector?

(1,1,1,1,1,..,1,1) [m ones]
so, for each column c there is exactly one row r in that subset
with A(r,c)=1

>>For a standard sudoku we have a binary matrix A(729,324).
>>Each row stands for a placement of one of the 9 symbols
>>into one of the 81 cells. The columns stand for the constraints
>>which must be met:
>>exactly one row matching a given symbol and column
>>exactly one symbol per column
>>exactly one symbol per block
>>exactly one symbol per block
>
>
>why twice an array for block?

oops, thanks. One of the blocks should be "row"

>>From the first post:
>>Quote:
>>Given the binary exact cover matrix A(n,m), R={1..n},C={1..m}
>>for a row r in R and a column c in C let
>>N(r):={c in C, A(r,c)=1} and N(c)={r in R, A(r,c)=1}
>>and #c:=#(c):=|N(c)|.
>>For a set X of rows and a set Y of columns let N(X) [N(Y)]
>>be the union of the N(x) [N(y)] with x in X [y in Y]
>
>Sorry I do not understand it.

it's very formal, so it can't be misunderstood.
Maybe you mean it's not so easy to visualize or interpret ?
Well, "N" is from graph-theory and stands for neighbors.
A binary matrix is just a bipartite graph.
N(X) is the set of all columns which have a 1 in any of the
rows from X.

>I am making something simular (but haven't got it working yet)
>but i use an array size of
>9^3 (729) by 2* 9^3 (1458)
>
>the row are all options:
>R1C1= 1
>R1C1= 2
>...
>R1C1= 9
>ect till
>R9C9 = 9
>
>The columns are all possible consequences of the option
>R1C1=1 ... R1C1=9 ... R9C9=9 and R1c1 <>1 till R9C9 <> 1
>
>an 1 means it is a FALSE consequence of the option
>an -1 means it is a TRUE consequence of the option
>an 0 means it is Unknown if this is a consequence of the option.
>
>
>so
>table( R1C1=9 , R1C1 = 8) = 1 (R1C1 =8 is FALSE if R1C1=9 is TRUE)
>table( R1C1=9 , R1C1<>8) = -1 (R1C1<>8 is TRUE if R1C1=9 is TRUE)
>
>For efficiency only :
>a 2 is a consequence of the clues and allways FALSE
>a -2 is a consequence of the clues and allways TRUE
>
>And (a lot ) of other arrays to make it all a bit more efficient.
>
>But In my humble opinion what i am doing is just a variation of Tabbling.
>But where does my method differ from what you describe?

more columns, more entries,

my method works for any matrix, not only sudoku-problems.

soduko · Posted: Mon Nov 07, 2005 3:12 pm Post subject:

There is some light comming....
But not a lot....

What do the different collumns in A(n,m) mean?

I figured out that they are constraints but how do you come to (only) 324 constraints?
Depending on what I count I come to 1458 or 729 constrains but maybe i am counting the wrong things.

If you just explain
When is A(n,m) =o and when A(n,m) =1 ?
for the different sub arrays. ( I think you have 4 subarrays each containing 81 contraints)
one for places
one for collumns
one for rows
and one for blocks.
But they have the same index for the row.

What means:
#c:=#(c):=|N(c)|.

and:
For a set X of rows and a set Y of columns let N(X) [N(Y)]
be the union of the N(x) with x in X [y in Y]

The last doesn't seem to mean: (AFAIK)
For a set X of rows let N(X)
be the union of the N(x) with x in X
and
For a set Y of columns let N(Y)
be the union of the N(y) with y in Y

but what does it mean???

And that is just the start.

Sorry for all this

But you wanted that everybody started using this language...

it's very formal, so it can't be misunderstood.

It cannot be misinterpreted/ misunderstood by experts that is hopefully true,
but understanding it in the first place is something different altogether

>why twice an array for block?

oops, thanks. One of the blocks should be "row"

Ah, I should have seen that myself, but i am just a bit flabbergasthed by this all.

I hope you don't find me a to hopeless case for your language.
(But if you do, i won't be the only one)

dukuso · Posted: Mon Nov 07, 2005 5:07 pm Post subject:

>I figured out that they are constraints but how do you come to (only) 324 constraints?

the matrix is designed such that an exact covering is just
a solution of the sudoku

>Depending on what I count I come to 1458 or 729 constrains but maybe i am counting the wrong things.
>
>If you just explain
>When is A(n,m) =o and when A(n,m) =1 ?

n,m are the ranges of the matrix, so let's say A(i,j).
Fixing i, A(i,j) is 1 for exactly 4 values of j
Fixing j, A(i,j) is 1 for exactly 9 values of i
If i is placement xyz then A(i,rxcy)=A(i,rxsz)=A(i,cysz)=A(i,bwsz)=1
and all others are 0 in that row.
Here w is the block corresponding to row x, column y.

>for the different sub arrays. ( I think you have 4 subarrays each
>containing 81 contraints)
>one for places
>one for collumns
>one for rows
>and one for blocks.
>But they have the same index for the row.

yes, but you can forget that they are "subarrays"
once you have the big matrix.

>What means:
>#c:=#(c):=|N(c)|.

the size of the set N(c), the number of ones in column c.

>and:
>For a set X of rows and a set Y of columns let N(X) [N(Y)]
>be the union of the N(x) with x in X [y in Y]
>
>The last doesn't seem to mean: (AFAIK)
>For a set X of rows let N(X)
>be the union of the N(x) with x in X
>and
>For a set Y of columns let N(Y)
>be the union of the N(y) with y in Y

it does mean this

>but what does it mean???
>
>
>And that is just the start.
>
>Sorry for all this
>
>But you wanted that everybody started using this language...

yes, it can be done without preliminaries but a little
experience in math and graphtheory helps.
Also experience with using ASCII here for math-terms.

>it's very formal, so it can't be misunderstood.
>
>It cannot be misinterpreted/ misunderstood by experts that is hopefully true,
>but understanding it in the first place is something different altogether
>
>
>>why twice an array for block?
>
>oops, thanks. One of the blocks should be "row"
>
>Ah, I should have seen that myself, but i am just
> a bit flabbergasthed by this all.
>
>I hope you don't find me a to hopeless case for your language.
>(But if you do, i won't be the only one)

I admit, I was basically addressing the mathematicians and programmers.
But you _can_ do this all without such knowledge.
It's just a little difficult to get familiar with the terms etc.

For the average human sudoku-solver it's probably
useless - , ... although...

-Guenter

soduko · Posted: Mon Nov 07, 2005 10:54 pm Post subject:

Ahh It is getting lighter with every post.

but i am still struggeling with:

Choosing a row r propagates to another smaller matrix A(r) with
columns N(r) and rows N(N(r)) removed and Sol(A)=r+Sol(A(r)),
where r+X:={x\/{r}, x in X}.

Removing columns????
(But I now understand the removing of rows, it is the same as removing of a candidate from a square)

Just deleting a row r from A gives the matrix denoted by A-r
Is A-r not the same as A(r)?

I think you make it more complex than it is by sticking to Cand R for your matrix it is confusing because the Sudoku grid also has C and R's but maybe i have to learn to live with that.

(0) r in N(c) <=> c in N(r)
???

(1) if c in C with #c=0 then Sol(A)={}
???

(2) "FN","singles",
if c in C, r in R; N(c)={r} then Sol(A)=r+Sol(A(r))
???

(3) if c1,c2 in C ; #c1=#c2=1 ; N(N(c1))/\N(N(c2))!={} then Sol(A)={}
???

(4) "Jaap1" follows from (6)
c1,c2 in C ; N(c2)>N(c1) ; r in N(c2)-N(c1) then Sol(A)=Sol(A-r)

??? What is Jaap1 ?

(5) "Jaap2"(generalized)
r1,r2,r3,r4 in R ; c1,c2 in C ; N(c1)={r1,r2} ; N(c2)={r3,r4} ;
r3 in N(N(r1)) ; r4 in N(N(r2)) ; r in N(N(r1)) /\ N(N(r3)) ;
then Sol(A)=Sol(A-r)

???? What is Jaap2 ??

(6) "Bo1", "block-block-interaction"
r in R ; c in C ; c not in N(r) ; N(N(r))>=N(c)
then Sol(A)=Sol(A-r)

But I still don't understand N(r) and N(c)

But i feel i am getting closer..
Thanks anyway

dukuso · Posted: Tue Nov 08, 2005 4:25 am Post subject:

>Ahh It is getting lighter with every post.
>
>but i am still struggeling with:
>
>Choosing a row r propagates to another smaller matrix A(r) with
>columns N(r) and rows N(N(r)) removed and Sol(A)=r+Sol(A(r)),
>where r+X:={x\/{r}, x in X}.
>
>Removing columns????
>(But I now understand the removing of rows, it is the same as
>removing of a candidate from a square)

yes, and when a constraint (=column) is already met, then there is no need
to consider it any longer.
E.g. if there is already a 7 in row 3, then column r3s7 can be deleted.
But, well the thread is about using non-sudoku-specific- general
exact cover speak, so this reads: when column c is already covered
(=met=intersected) by a row in our temporary solution set, then we remove it.
Whenever we add a row r to our temporary solution set,
then we remove this row together with all its neighbors
(=intersecting columns) and all the neighbors of these
neighbors (=rows which have a column in common with r)

>Just deleting a row r from A gives the matrix denoted by A-r
>Is A-r not the same as A(r)?

no, since N(r),the neighbors of r, and N(N(r)),the neighbors of those
neighbors are not removed. r is not included in our solution set, but rather
excluded as a candidate

>I think you make it more complex than it is by sticking to Cand R for
>your matrix it is confusing because the Sudoku grid also has C and R's
>but maybe i have to learn to live with that.

I should more consequently call them Rows,Columns,Blocks with capitals

>(0) r in N(c) <=> c in N(r)
>???

row r is adjacent to column c, if and only if column c is adjacent to row r

>(1) if c in C with #c=0 then Sol(A)={}
>???

empty column, then there is no solution

>(2) "FN","singles",
>if c in C, r in R; N(c)={r} then Sol(A)=r+Sol(A(r))
>???

only one row r to meet a constraint c, then it must be taken
and it will be in every solution

>(3) if c1,c2 in C ; #c1=#c2=1 ; N(N(c1))/\N(N(c2))!={} then Sol(A)={}
>???

two constraints with exactly one candidate can't be "adjacent"

>(4) "Jaap1" follows from (6)
>c1,c2 in C ; N(c2)>N(c1) ; r in N(c2)-N(c1) then Sol(A)=Sol(A-r)
>
>??? What is Jaap1 ?
>
>(5) "Jaap2"(generalized)
>r1,r2,r3,r4 in R ; c1,c2 in C ; N(c1)={r1,r2} ; N(c2)={r3,r4} ;
>r3 in N(N(r1)) ; r4 in N(N(r2)) ; r in N(N(r1)) /\ N(N(r3)) ;
>then Sol(A)=Sol(A-r)
>
>???? What is Jaap2 ??

Jaap's second rule.see the quoted text in the first post in this thread
OK, in words rather than symbols it reads:
(you see, it's much shorter with symbols)

My first rule is this:
Suppose there are two columns in the matrix, A and B, and that
for every row where A has a non-zero entry B also has a non-zero entry.
Any move that satisfies constraint A then also satisfies constraint B.
Therefore we can eliminate any other entries in column B (i.e. any matrix
row that has an entry in B but not in A).

My second rule is this:
Suppose there are 2 columns A and B, each with exactly two entries,
say A1, A2, and B3,B4.
Suppose also that A1 conflicts with B3 (there is some column that
has entries in rows 1 and 3) and similarly that A2 conflicts with B4.
Then we must have one of the moves 1 or 3, and also have one of the
moves 2 or 4.
Any column with entries in 1 and 3 can have its other entries eliminated.
Similarly, any column with entries in 2 and 4 can have its other entries
eliminated.

>(6) "Bo1", "block-block-interaction"
>r in R ; c in C ; c not in N(r) ; N(N(r))>=N(c)
>then Sol(A)=Sol(A-r)
>
>
>But I still don't understand N(r) and N(c)

well, that explains all your ??s .
But it's a simple definition. It's just all columns [rows] in the matrix
which have a one at position r [c] .
N(r)={c in C , A(r,c)=1} , what else could I say ?

>But i feel i am getting closer..
>Thanks anyway

will you help to formulate a version which is easier to
understand for the math-laymen ?

You must admit that the notations are short,exact, non-ambiguous
once you understand it, which should be no problem for someone
familiar with math-texts.

-Guenter

soduko · Posted: Tue Nov 08, 2005 9:49 am Post subject:

will you help to formulate a version which is easier to
understand for the math-laymen ?

I think lets call
Cullumns Tests
and
Rows Placements

and always when nescesary refer to them in code
so
A(P[R1C1S1], T[R1S1]) =1

or
A(P[i], T[j])
or
A(Pi, Tj)
(always keep the P and T)

And write every quotation twice if it is for placements and for tests
(do not muddle them together just to get shorter code)

Or is this against the grain of your notation?

But I think everybody who reads this tread will understand it a little better.
I am of for two weeks but will help you afterwards.
If you have a draft send me a PM with your text and i will send you an edited version back. But i am off for two weeks.

Maybe we can make a (e)book mathematical Sudoku.
That explains (all) known solution methods.
(I have also some ideas of a different grid representation)

You must admit that the notations are short,exact, non-ambiguous
once you understand it, which should be no problem for someone
familiar with math-texts

I admit that, but i did not deny that, i just didn't understand it.

Last question,
This looks to me a bit like DLX (Dancing links) are they based on the same theory/notation?
Or are they two completly unrelated methods.
And i just didn't understand them both.

See You in two weeks.

LangPol · Posted: Mon Mar 20, 2006 2:53 am Post subject:

New and just started reading this thread. You (dukuso) stated an attempt to create a formal definition for Sudoku, but I don't think you're doing that. The definition is simple: it's just an NxN array, A, of NxN arrays, M, where the contents of each of the M arrays contain unique values 1 to N-squared, with the constraint that each A[i,*] and A[*,j] are also unique. Or something like that. What you seem to e groping at is some sort of of formal definition for defining an exact cover of A and that is just a formal definition of one of any number of possible solutions. Or am I just confused?

dukuso · Posted: Mon Mar 20, 2006 6:50 am Post subject:

I think my description and language is more general and superior.
You can formulate and develope and proof new theorems and
properties easier and more legant.
It's not primarily directed towards sudoku but exact-cover solving
in general, sudoku just serves as a nice example.

When you compare this with books about constraint satisfaction
problems with alldifferent constraints, you'll find that their
descriptions and definitions are less satisfying than
the exact-cover approach.

(IMO)

pablo

Well, interesting approach this exact-cover-sets anyway, but still not general enough, me thinks. I want to post an equally interesting problem formulation that gets rid of all those number juggling - not sure whether this thread is the right place, so Ruud, feel free to shift it to another (new?) thread ...

What do we really have if we look BEHIND all those rows, columns, block, cells and numbers placed into them? It's all PARTITIONS and clever combinations of them!

Look it at this way. We have a set S of somethings (here: 81 places). We want to partition them in several ways. Get any one partition P1. Now we want to find and add to our bucket of partitions another one (P2) that is orthogonal to the first one (P1). Orthogonal? Yes, it should be such that the intersection of any member of P1 with any member of P2 is non-empty (perhaps this should rather be called non-orthogonal, or interlocking, or ...? don't mind my terminology for the moment, keep thinking...). Is this always possible? Surely. Apply the "choice axiom", several times. Easy!

How do the two partitions relate to each other? Hm, interesting questions, depends of course upon the size of the partitions as well as the resp. sizes of all elements (which are themselves sets, remember?) within those partitions. E.g., suppose, we are only interested in "nice" partitions with the peculiar property that there are as many elements (i.e., places) within each element (some subset of S) of the partition as there are elements of those partitions. Shorter: the size of subsets within P equal the size of P itself. Got it? What do we get for P2 if we start with such a P1? (Please figure out yourself).

OK, back to the general case. So we had two orthogonal partitions P1 and P2. The straightforward next step is to look for a third partition P3 which is pairwise orthogonal to the ones we already had. Is this possible? Well, not so easy and quickly to answer, isn't it? Of course we know that it is possible: the rows, the columns and the "templates" (I borrow the term from Ruud) of a Sudoku have this property, but how would you approach this problem generally (and without the additional constraints of a Sudoku, in the first place)?

And now it comes: as a mathematician you don't stop with 2 or 3, especially not when you have found something to be true for case n=2,3. The next question is thus: What about n>3? Can you always add another orthogonal partition, e.g. P4, which is orthogonal to the ones you already had? Sudoku? NO!! Oh yes, Sudoku HAS a fourth partition in it, the blocks, but these are not orthogonal to P1 (rows) and P2 (columns), only to P3 (templates). So Sudoku has an imperfect structure (sorry folks...), but perhaps we can't expect more, if we go beyond n=3?

I know, there is a huge literature on partitions, of sets as well as numbers, and also a lot about latin squares and even orthogonal latin squares (n=4?), etc. (e,g, see http://www.elsevier.com/wps/find/bookdescription.cws_home/505639/description#description).
Does anybody know of any research of Sudoku's along these lines? Or do you think, this doesn't add any insight (or fun, for that matter Laughing

)

yours, pablo

[added on 2006.03.21:]

for the mathematically inclined: <S, P1, P2, P3, ...> could be viewed as a kind of hypergraph, or multi-hypergraph (set of hypergraphs), with very special properties/constraints between P1 etc. Equally well, noting that any partition uniqueline defines an equivalence relation, it can be reformulated as a proper algebraic (relational) system, i.e. a set with multiple relations, in this case all equivalence relations (with particular constraints ... didn't work that out so far). Whether these embeddings of the structure within well-known categories does help us much, I don't know.

for the practically inclined: there is a funny (useful?) application of these sorts of partitions. Think of P1 as a country divided up in regions, or towns if you like, and of P2, P3,... as any other collection of exclusive groupings of the country (parties, unions, etf.) The existence of orthogonal partitions, especially of the Sudoku type, means that you can assign PINs to individual members in such a way, that knowing any two associations suffices to identify that person. And each person only has to remember one PIN only. Think of this!