From Sudopedia, the free Sudoku reference guide

From Sudopedia

Professor Prune, I'm very grateful for your contributions here and the last thing I want to do is step on your toes. However I would like to take a rain check on your Hidden UR section. It tends to suggest that this is the only other deduction available when a potential UR lurks in a mass of other candidates, but as I'm sure you know, this is far from true! A better approach I feel would be to start a new entry for advanced UR techniques. It's possible that a further entry for URs in Sudoku variants would be possible (but there I can't contribute I'm afraid).

It must take you ages to pen your descriptions and (as a bit of feedback) they take ages to digest! The Hidden UR description has typos in it too (I think) which is quite understandable. I would suggest that you use thumbnail diagrams giving the disposition of the candidates in the cells, as being easier and less error prone to write and quicker for the reader to absorb.

I've only taken a recent interest in URs so this is work in progress for me which I don't intend to rush! However here is a cock-shy using your example of the direction a new entry could take.

Dpbobelisk 02:36, 22 January 2008 (CET)

Advanced UR Techniques

Higher forms of UR deductions are possible when one or both UR candidates are locked in certain sides of the rectangle, and/or the set of disrupting candidates is subject to constraints. A collection of these is listed in the Players' forum:

Take this latent UR:

 (ab)A      (abx)B    Candidate a is locked in sides BD and DC 
         a    || a    x, y and z are any number of disrupting candidates possibly with some common digits  
(aby)C  === (abz)D 

Using a trial and error placement of (b)D it will be seen that this will force one of the deadly patterns, so showing it to be false.

Here is an example where this pattern is rotated:

.------------------.------------------.------------------.
| 135   19    6    | 24    27    247  | 8     1359  39   |
| 358   29    23   | 8     6     1    | 379   34579 3479 |
| 17    8     4    | 5     9     3    | 2     17    6    |
:------------------+------------------+------------------:
| 2     3     18   | 149   17    478  | 479   6     5    |
| 4     6     58   | 29    35    278  | 379   379   1    |
| 9     7     15   | 146   35    46   | 34    8     2    |
:------------------+------------------+------------------:
| 18    12    9    | 3     4     5    | 6     27    78   |
| 6     5     23   | 7     8     9    | 1     234   34   |
| 38    4     7    | 126   12    26   | 5     39    389  |
'------------------'------------------'------------------'

Possible Eureka notation:

(5|7|9)r2c8 =[(34)UR]= (2|7|9 - 4#2)r2c9,r8c8 = (4)r2c8 => r2c8 <> 3

1. Strong Inference: at least one disrupting candidate must be true in one of the UR cells
2. Weak Inference: the diagonal cells can't hold both a disrupting candidate and two 4s
3. Strong Inference: both row 2 and column 8 must contain a 4

This inference chain therefore shows that r2c8 can only contain a disrupting candidate or 4 to provide the exclusion.

AIC Inferences Arising from URs

1. A chain (c)Q = [. . .] = (ab)UR:ABCD proves (c)Q is true as the UR node is false
2. (x)A =[(ab)UR:ABDC]= (y|z)B The disrupting candidates form a strong set - one of them must be true.
3. (ab)AC -[UR]- (ab)BD Two opposite sides of a UR can't hold both digits
4. (a #2)AD -[UR]- (b #2)BC The two diagonals can't both hold two (a)s and two (b)s
5. (a)X-wing:ABCD -[UR]- (b)X-wing:ABCD The four UR cells can't hold two (a)s and two (b)s

Repeating the inference symbol on either side of [UR] indicates the basis of the inference. If the composition of the UR being used isn't immediately apparent from the adjacent nodes, specifying it in full (as in 2 above) improves the clarity of the notation.

These inferences still apply even if one of the UR cells has been resolved to hold one of the UR candidates PROVIDED it wasn't given by the puzzle composer. See Avoidable Rectangle

Reply to Dpbobelisk

The Hidden Rectangles section that I added is taken from the strategy described in Andrew Stuart's book The Logic of Sudoku. As you point out, this is not the only possible deduction in this class. I like your idea of "Advanced UR Techniques" as a separate topic, with "Hidden Unique Rectangles" as a subtopic. I do suggest that we include the subcase where one of the UR digits is strongly linked twice in the opposite corner under the name "Hidden Unique Rectangles" since that's how it's named in Andrew Stuart's book and elsewhere in Sudoku literature.

My description is indeed a terse, but very precise, description of the conditions under which a Hidden Unique Rectangle occurs, and of the removal it permits. I have checked both the description and the example and I believe them to be correct. The example is in fact taken from a solution to the Daily Telegraph website's Extreme Sudoku #10 that was found by my solving program.

I would love to use thumbnail diagrams. I think they are far more understandable and easier to read than code examples. Do you know where I can find software or a website that will let me generate them?

Professor Prune 14:26, 30 January 2008 (EST)

PP Thanks for your response. I'm pleased that you like the idea of spawning a separate entry for the more complex cases. As I've already suggested, we can leave the main entry as it is until we're happy with the new one. In the re-working of your example I simply used fixed spacing to produce the thumbnail, but it's rather amateurish. There are instructions on how to create tables for these pages in Wiki Help which will do it. This allows the thumbnail to be placed on the left with the description on the adjacent cells to the right, but it takes some experimentation to get it looking good.

So far I've got 13 different UR deductions classified, but I've still got a way to go (it's rather tedious and I peck away at them in between other activities). I'm leaving the best way to order them until the list is complete. Here is an example where I'm using a cell qualifier X{QT} to mean that X is any cell which sees both Q & T.

The only digits available to disrupt the UR are x & y, one of which must be in cell T. Therefore any cell which sees all instances of x or y in the UR and cell T can't hold that digit, otherwise either T would be empty or the UR would be forced to hold a forbidden pattern.

It's taken me over an hour to get this effect, and I know I've only scratched the surface so far! It seems that a template can be made for a layout which is used repeatedly.

As soon as I've waded through the cases I'll create a draft of the new entry. In the meantime if you have the inclination you could delve into how to make best advantage of tables! I also get the feeling that you aren't very familiar with AIC notations - am I right? If so I would encourage you to study them as if you can notate a deduction as a proper AIC, you can be sure its right.

Dpbobelisk 12:50, 1 February 2008 (CET)

Dpobelisk: Go for it regarding the new page.

I know about AICs (programmed them in my solver). I find them highly useful for proving the validity of deductions, but not so useful as a way to explain a technique or deduction.

Professor Prune 11:25, 1 February 2008 (EST)

Dpobelisk,

I went ahead and revised the Uniqueness Test page to include most of the information from the Sudoku Players' Forum article on Unique Rectangles, as you suggested. I'll add the rest of the rectangle patterns soon, probably tomorrow. The new classification subsumes my previous "Hidden Unique Rectangles" section, plus a lot more.

The new material could use more examples, and more Eureka notation (not my forte, I'm afraid).

Professor Prune 00:52, 7 February 2008 (EST)

Prof Prune, I can't answer for the DLX algorithm, but this is how I would modify the backtracking description with respect to Ariadne's Thread:

Ariadne's thread can be performed manually or on a computer. It starts by placing an assumed digit into one of the cells with the most restricted choice, then working out the direct consequences. A copy of the grid is now taken and the process repeated until either a contradiction or a solution is found. In the case of a contradiction, the most recent copy is restored and the testing continued using the next digit choice in the current test cell. If at some point it is found that the first assumed candidate must be false, it is excluded and any consequences followed before systematic testing is resumed.

This method of exploring every fork in a path is an example of Bifurcation and can be classified as a Trial and Error and Brute Force method.

Edit and use this as you see fit.

I'm close to finalising my list of UR deductions (it's slow as I've been rather tied up this week). I've found some of them don't rely on uniqueness at all though and are rather out of place as some people prefer not to use uniqueness based deductions.

Dpbobelisk 12:34, 16 February 2008 (CET)

Dpobelisk,

I like your description. Go ahead and make the edit.

It doesn't surprise me that some of the UR deductions actually don't require the uniqueness assumption. This is certainly worth pointing out, and maybe they should go on a different page.

Thanks,

Professor Prune 12:04, 16 February 2008 (EST)

On the catalogue of UR deductions, once I had condensed the duplications in the ones that were originally listed I found several more which were more complicated and of questionable merit for inclusion. I then had to take a break over some health issues and lost momentum. I'll try to get back to that!

Dpbobelisk 11:24, 29 March 2008 (CET)

Professor Prune - you are definitely getting there! Although I still have a few residual reservations, your latest changes are a great improvement. I have fairly major maintentance to do on my computer now, as it seems I must reinstall everything to get a new broadband connection working properly. It may therefore be some time before I re-appear.

Dpbobelisk 11:16, 2 April 2008 (CEST)

Dpbobelisk,

I'll be the last person to claim that I have a complete understanding of AICs. Far from it. Witness my confusion regarding inferences vs. premises. Please let me know what your residual reservations are, or just go ahead and correct them. I think an example or two of some of the more complex premises that can take part in AICs would be useful, too. And also an example of an AIC with useful eliminations that starts and ends in a weak link (all the ones I've dealt with start and end with strong links). I understand conceptually how that can work, but I haven't encountered a practical example of it in action (probably mostly because I haven't looked, or because I have expressed the AIC in another way, such as multi-coloring).

Looking forward to your contributions, especially regarding unique rectangles.

Professor Prune 22:40, 4 April 2008 (EDT)