The New Sudoku Players' Forum

[denis_berthier]

What I say here I have already (more or less) said in the Sudoku.org.uk forum (Eureka thread), where it has generated much discussion. But I can see there are different participants here. And it may be good to have a short summary of what I said previously.

Some symmetries (in the general mathematical sense) of Sudoku are obvious and well known:
- you can permute rows and columns,
- you can permute rows (or columns) in the same group of 3,
- you can permute whole groups of 3 rows (or columns)
…
I'm not going to speak of these obvious symmetries.

The topic of this post is other generalised symmetries, that had never been explicited and which I have called supersymmetries in my book "The Hidden Logic of Sudoku".
Roughly speaking, they consist of permuting rows and numbers or colums and numbers. But when you say things that way, it is incorrect, because these supersymmetries are not valid in general, they are subject to some precise restrictions. And nobody can claim to know or understand these supersymmetries if he doesn't also know or understand these restrictions.
I have proven the following theorems:
- a block-free formula (or rule if you prefer), i.e. a formula that does not mention blocks/boxes, is valid for Sudoku if and only if it is valid for Latin Squares (i.e. without the constraint on blocks);
- for any valid block-free resolution rule (and only for such rules), the rules obtained by applying to it the above supersymmetries are valid.
These theorems cannot be extended to non-block-free resolution rules - so that saying (as I've sometimes seen written) that this is a severe limitation can only be a proof of misunderstanding. (Said otherwise, maths are not ruled by our desires.)

Simplest examples:
- from Naked-Subsets rules, one gets Hidden-Subsets rules
- from Naked-Subsets rules, one also gets Super-Hidden-Subsets rules, commonly named X-Wing, Swordfish and Jellyfish.
Part (and only part) of the factual symmetry relationships between these rules have been locally known for some time, although the above general transposition theorems were not formulated.

Having formalised the axioms for Sudoku Resolution Theories and proved the above general theorems allows to go much further than the above mentioned local remarks on relationships between Subsets.
Indeed, to any block-free rule in rc-space there corresponds a rule in each of two new spaces, the rn- and cn- spaces.
As a consequence, you can take almost any (in fact any block-positive) resolution rule R and restrict it to cases which do not make use of blocks. You get a specialisation of R, call it R'. R' is not interesting in itself, but it can now be transposed to both of the rn- and cn- spaces, using the above general theorem. Now you get something new. And anything you used to do with R in the standard representation, you can also do, as easily, in the two rn- and cn- representations. You can even do it more easily, because, in these spaces links between cells are restricted to what is displayed as rows and columns.

In order to ease the application of the super symmetries in the general case, the rn- and cn- representations of the puzzle can been grouped into an Extended Sudoku Grid (a new version of which I have now made available on my web pages, with notations consistent with those used in the book) and I have written a systematic procedure for building them (so that writing a program or a spreadshhet for managing the coherency of the 3 subgrids would be easy) together with recommandations on how to use them.


Let us now see if the above transposition theorems bring anything new.

Firstly, to xy-chains, there correspond hxy-chains in rn- and cn- spaces. Here, "h" stands for "hidden", as in hidden-subsets. hxy-chains appear in rn- or cn- spaces as xy-chains would in the usual rc-space.
hxy-chains do not allow to solve new puzzles if you already know the complex generalised AICs, because they can be shown to be particular cases of them. But they allow to make some (not all) complex AICs appear as much simpler xy-chains in the proper rn- or cn- space. So that, if you didn't know AICs or if you find it difficult to spot them, you can anyway solve puzzles you couldn't solve before. hxy-chains make some complex chains appear simpler.

Secondly, I have also introduced new kinds of chains, the xyt-chains and xyzt-chains, that are of interest in themselves, because they are very powerful, although very simple, generalisations of xy-chains and of respectively XY-Wing and XYZ-Wing. xyt-chains and xyzt-chains cannot be reduced to any known resolution rule.
Moreover, to these new chains there correspond new chains in rn- and cn- spaces, the hxyt-chains and hxyzt-chains. And the rules for the new hxyt-chains and hxyzt-chains cannot be reduced to any known rule.

Finally, what I consider noticeable is that with only these types of chains (plus of course the elementary rules for Subsets and Interactions) you can solve 97% of the randomly generated puzzles - without resorting to any of the much more complex rules that have been devised. It does not mean that these complex rules are no longer justified. But it means that there are more puzzles you will be able to solve without them.

[ravel]

For those, who are only interested, what xy(z)t-chains are, here and there are two threads on the discussions forum.

Denis, are there any activities to provide a program, that can show the 2 additional views (with a possibility for printing and copying the grids) ?

[udosuk]

Denis, are there any activities to provide a program, that can show the 2 additional views (with a possibility for printing and copying the grids) ?

FYI, I wrote a spreadsheet that can automatically work out the digit-appearance tables from a given pencilmark grid. But it's probably not usable by others as I didn't make it too user friendly...

[ronk]

FYI, I wrote a spreadsheet that can automatically work out the digit-appearance tables from a given pencilmark grid. But it's probably not usable by others as I didn't make it too user friendly...

I did as well but, to avoid a circular reference, one must mentally translate a move in the rn- or -cn space to the rc-space. IOW the rn- and -cn-spaces are write protected, which means one can't even highlight cells. Haven't used it much yet though.

[denis_berthier]

Denis, are there any activities to provide a program, that can show the 2 additional views (with a possibility for printing and copying the grids) ?

Ravel, thanks for providing the two links I forgot to give explicitly.

I'm not personally developing any computerised tool for the automatic generation of the rn- and cn- representations (nor I'm aware of anybody doing it, apart from udosuk 's previous post). This should be a very straightforward thing to do, unless you want complex graphics. Anybody willing to do it would be most welcome. It'd be still greater if the software was made available, either on your web pages if you have some or in mine if you prefer.
Nevertheless, such a tool will be useful only when you have a computer with you.

One should not be misled by the fact that I have developed a rule based program and I use it massively. This is mainly for producing statistical results on large collections of puzzles and evaluating the relative efficiency of each rule. This has been useful also for testing the logic of my rules. But the rules and the representations I have devised are totally human oriented.

Indeed, my approach to Sudoku is as a game for a human with only a sheet of paper and a pen. I have just extended the size of the sheet of paper, since it must contain 3 grids instead of 1.
The directives I've given on my web pages (http://www.carva.org/denis.berthier) will allow you to build the new representations easily by hand - although you'll need some time to get used to building and using them, as I needed when I first devised them (but now, it doesn't take me more than 2 minutes to generate them).
And you can build them only at the time you are blocked, so that you won't waste time in case you know how to solve the puzzle without them.
I'd be very interested in opinions of users of these new representations (after you have used them for some time, say on more than 10 puzzles).

[denis_berthier]

I did as well but, to avoid a circular reference, one must mentally translate a move in the rn- or -cn space to the rc-space. IOW the rn- and -cn-spaces are write protected, which means one can't even highlight cells. Haven't used it much yet though.

Ronk, I must have been editing my post while you posted yours.
So, that makes 2 existing tools.
Since any elimination must be transferred to rc-space, the only space where block constraints can be taken into account, the restriction in your program is not dramatic. I would have done the same.

Why would you want to highlight cells? Do you mean decided cells?

[ronk]

Why would you want to highlight cells?

Just to make it easier to see where I've been while following a potential hxy(z)(t) chain.

For my own use I don't actually write-protect the sheet, but wouldn't consider distributing it without doing so.

[udosuk]

I did as well but, to avoid a circular reference, one must mentally translate a move in the rn- or -cn space to the rc-space. IOW the rn- and -cn-spaces are write protected, which means one can't even highlight cells. Haven't used it much yet though.

I don't see the big issue here. My sheet just produces the 2 tables from a starting pencilmark grid, I don't care about the dynamics. At any time you can copy & paste one of the tables to notepad, and then copy & paste that data to another group of cells somewhere else on the sheet, so that they become pure data, and you can perform whatever highlighting/editing on them. And it wouldn't be too complicated to say perform a reverse translation from say a rn-table to the other 2 tables on another sheet. That way you can copy & paste data back and forth between sheets and there's no need to "mentally translate" any move.

[re'born]

xyt-chains and xyzt-chains cannot be reduced to any known resolution rule.

Would you clarify what you mean by this? By the way I think I independently came upon your chains (assuming I understand what you mean by the terms), see my recent post.

[denis_berthier]

xyt-chains and xyzt-chains cannot be reduced to any known resolution rule.

Would you clarify what you mean by this? By the way I think I independently came upon your chains (assuming I understand what you mean by the terms), see my recent post.

I've looked at your post, dated later than my first posts on the subject and after a lot of discussion on xyt-chains on the Sudoku.org.uk forum and the Sudoku Programmers Forum (and more than one month after my book was published).
xyt-chains are not generalisations of wxyz-wing but of xy-wing. I also have xyzt-chains, a generalisation of xyz-Wing. For the generalisation of wxyz-wing, I had introduced wxyzt-chains, but they appear very rarely and I didn't speak of them in my book.

Generally speaking, saying which tricks we used to solve one or two puzzles and providing comments as to a generalisation, is very far from having formulated a general rule.
Anyway, the only place where something general is stated in your post dated 06/20/2007 misses the essential point in the logic of xyt-chains.

In a sense, you might call that for which I'm looking almost xy-chains. The way I go about finding things is by looking for chains of bivalued cells and observing the obstructions to them being xy-chains. If all of the obstructions are 'nice', then I've found the right set. Usually 'nice' means that the extra candidate sees every other instance of itself in my set. Otherwise, I tweak things by adding or removing cells until either I find the right combination or I give up.

Five days before your post, Michael McWilliams, trying to translate xyt-chains in his own terms, wrote (06/15/2007) in my thread on xyt-chains:

In words xyt equates to this : anything already placed in an on-going chain eliminates anything that it sees further along the same chain.
As such, this logic would be used by anyone of a certain experience who is performing an AIC.

To which I answered (06/16/2007):

NO, although the formulation would be nice. In the xyt4-chain pattern:
{1 2} - {2 3} - {3 4 (2#1)} - {4 1 (2#1)(3#2)}
2 in cell 2 does not "eliminate" 2 in cell 4, even if cell 4 sees cell 2.
Only what I call the right linking candidate of a cell (the candidate that it shares with the next cell) can allow you to forget its presence (I prefer this than "eliminate", that may be ambiguous for novice readers) in cells further along the chain.
Paraphrasing your formulation, I’d state : "anything already chosen as the right linking candidate of an ongoing xyt-chain allows you to forget its presence as an extra candidate in any cell that it sees further along the same chain".
Notice that since the same linking candidate can occur in different places in the chain, I had to be careful with the formulation.

Four days later, in your post dated 06/20/2007, you have not noticed that seeing is not enough for allowing the "obstructions" to be eliminated.

[re'born]

xyt-chains and xyzt-chains cannot be reduced to any known resolution rule.

Would you clarify what you mean by this? By the way I think I independently came upon your chains (assuming I understand what you mean by the terms), see my recent post.

I've looked at your post, dated later than my first posts on the subject and after a lot of discussion on xyt-chains on the Sudoku.org.uk forum and the Sudoku Programmers Forum (and more than one month after my book was published).
xyt-chains are not generalisations of wxyz-wing but of xy-wing. I also have xyzt-chains, a generalisation of xyz-Wing. For the generalisation of wxyz-wing, I had introduced wxyzt-chains, but they appear very rarely and I didn't speak of them in my book.

Generally speaking, saying which tricks we used to solve one or two puzzles and providing comments as to a generalisation, is very far from having formulated a general rule.
Anyway, the only place where something general is stated in your post dated 06/20/2007 misses the essential point in the logic of xyt-chains.

In a sense, you might call that for which I'm looking almost xy-chains. The way I go about finding things is by looking for chains of bivalued cells and observing the obstructions to them being xy-chains. If all of the obstructions are 'nice', then I've found the right set. Usually 'nice' means that the extra candidate sees every other instance of itself in my set. Otherwise, I tweak things by adding or removing cells until either I find the right combination or I give up.

Five days before your post, Michael McWilliams, trying to translate xyt-chains in his own terms, wrote (06/15/2007) in my thread on xyt-chains:

In words xyt equates to this : anything already placed in an on-going chain eliminates anything that it sees further along the same chain.
As such, this logic would be used by anyone of a certain experience who is performing an AIC.

To which I answered (06/16/2007):

NO, although the formulation would be nice. In the xyt4-chain pattern:
{1 2} - {2 3} - {3 4 (2#1)} - {4 1 (2#1)(3#2)}
2 in cell 2 does not "eliminate" 2 in cell 4, even if cell 4 sees cell 2.
Only what I call the right linking candidate of a cell (the candidate that it shares with the next cell) can allow you to forget its presence (I prefer this than "eliminate", that may be ambiguous for novice readers) in cells further along the chain.
Paraphrasing your formulation, I’d state : "anything already chosen as the right linking candidate of an ongoing xyt-chain allows you to forget its presence as an extra candidate in any cell that it sees further along the same chain".
Notice that since the same linking candidate can occur in different places in the chain, I had to be careful with the formulation.

Four days later, in your post dated 06/20/2007, you have not noticed that seeing is not enough for allowing the "obstructions" to be eliminated.

Umm...okay...I'm not sure why you are so concerned about dates. This isn't a competition.

Might you answer my question now?

[denis_berthier]

Umm...okay...I'm not sure why you are so concerned about dates.

Dates are only there to bring you back to reality. I'm trying to make you understand that claiming you have done something that you obviously didn't (and this is not the first time you do so) is not the best way for entering a discussion.
The topic of this thread is "Supersymmetries and Hidden chains" and I'd like we more or less stick to it.

[re'born]

Umm...okay...I'm not sure why you are so concerned about dates.

Dates are only there to bring you back to reality. I'm trying to make you understand that claiming you have done something that you obviously didn't (and this is not the first time you do so) is not the best way for entering a discussion.
The topic of this thread is "Supersymmetries and Hidden chains" and I'd like we more or less stick to it.

Eh? I'm sorry. What exactly did I say that was so offensive? And when did I claim to have done something that I hadn't done? If I stepped on your toes somehow, I apologize. My post was meant to accomplish two things:

1) Ask for clarification as to what you meant when you said that xyt-chains and xyzt-chains cannot be reduced to any known resolution rule. I am still interested in this.

2) Share in your excitement over your pattern and to offer support to the position that it is a useful way of looking at difficult puzzles. I had not read any of your posts on the other forums until ravel posted links yesterday. My ideas (correct or incorrect) are the applications of principles I learned from bennys and aeb back in early 2006. Nearly every ALS xz-rule solution I have posted on this forum since I joined in February 2006 has been found using the ideas in my post or extensions of those ideas to more complicated situations.

[ravel]

Dates are only there to bring you back to reality.

Oh, no need to bring re'born "back" to reality. Ok, you wrote a book and want to sell it. And you have to defend its originality. We can see things looser, and we also like these "ah, you have found the same!" moments.
I agree with re'born that saying "xyt-chains and xyzt-chains cannot be reduced to any known resolution rule" easily can be misinterpreted. Of course you can write them as nice loop and i am very sure, that under Carcul's solutions you can find one, that was published before your book.
But this doesn't influence the quality or originality of your book or re'born's thread.

[denis_berthier]

re'born claims about xyt-chains are just unfounded and it's neither a matter of selling a book nor a matter of what anybody likes or not.
xyt-chains have their internal logic, precisely described and proved in my book, which is not what re'born described.

"B can be reduced to A" means two things at the same time:
- A is simpler than B,
- one can explain B in terms of A.
This relationship is particularly interesting when it is not symmetric, i.e. when A cannot be explained in terms of B.
For instance, I proved that xy-chains with loops can be reduced to shorter xy-chains and elementary rules. But the converse is obviously false (an xy-chain cannot always be extended into an xy-loop).

Despite ravel's "of course", xyt-chains cannot be reduced to Nice Loops, because none of the above two conditions is satisfied.
Ravel, if you don't know something but wish it would be true, instead of trying to mislead your readers by expressions such as "of course" or "I am very sure that", can't you say "I wonder if"? Or are you a politician?