Very Hard - from Times Website

All about puzzles in newspapers, magazines, and books

Postby Guest » Fri Apr 01, 2005 11:12 pm

Well, I have the vino open anyway :o). But... I still agree with Sue De Coq that this is another Nishio - a neater example perhaps, but those four cells don't tell you anything on their own. You need row 1, and boxes 8 & 9. It is very neat, but I still doubt anyone could resolve it without the "well if this is 6, then that's a 2, so that's a 7, etc.". To me, at least, if it's to count as logic it needs to be definable by a general rule, which could be used to recognise the pattern in other puzzles, and infer the solution without having to test cells/values. Am I being too fussy? Can anyone think of a way to describe this as a rule?

Postby su_doku » Sat Apr 02, 2005 12:56 am

IJ wrote:You need row 1, and boxes 8 & 9. It is very neat, but I still doubt anyone could resolve it without the "well if this is 6, then that's a 2, so that's a 7, etc.".

The logic I presented does not start from "well if this is 6, then.." That is T&E. I 'll try to articulate again but may need help if I cant get this across succuinctly.

From the point where IJ and others were stuck, we know Row 1 and Row 9 as well as Column 6 and Column 9 together with boxes 2,3,8 and 9 need the 6 in the right positions.

Now consider the 4 cells r1c6, r1c9, r9c6 and r9c9 forming the infamous X- Wings. Disect the wings to give wing / between r1c9-r9c6 and wing \ between r1c6-r9c9. It is logically clear that the two 6's can only go at the opposite ends of one of the two wings but to make the next logical step it is not necessary to know which wing it is because for either wing, there will be a 6 at the extremes that will place a 6 in the relevant rows, columns and boxes. Note we are not doing any T&E here.

Hence when one homes in on column 9, it is obvious that a 6 will be present either in r1c9 (and hence r9c6) or in r9c9 (and hence r1c6)only, again we dont care where exactly, thus allowing us to safely and logically conclude even before ascertaining where exactly that 6 is that r7c9 can be 9 only.

I don't agree this is Nishio - this is pure logic.

It is from the 9 in r7c9 that the exact positions of the 6's 2's, 7's and 1's fall in to give that Eureka moment!

I hope that helps.
Posts: 30
Joined: 19 March 2005

Postby Guest » Sat Apr 02, 2005 1:24 am

Right! That's brilliant. Truely! As promised I am now prostrating myself and starting the timer...

Postby Guest » Sat Apr 02, 2005 1:31 am

Ok. Times up. I'm done with being humble ;o) Now I've got to code this into my solver. Who needs sleep?

Postby Sue De Coq » Sat Apr 02, 2005 2:11 am

Please consider the following two pieces of logical deduction:

I. (X-Wings)

Assume r7c9 is a 6.
Trivially, r1c6 must be a 6. (Look along Row 1).
Trivially, r9c9 must be a 6. (Look along Row 9).
Whoops!, we have two 6s in Column 9.
Therefore, r7c9 can't be a 6.

II. (Nishio)

Assume r8c4 is a 7.
Trivially, r1c6 must be a 7. (Look along Column 6).
Trivially, r1c1 must be a 7. (Look along Column 1).
Whoops!, we have two 7s in Row 1.
Therefore, r8c4 can't be a 7.

Clearly, the underlying logical processes are similar. I fail to see why I should be legal but not II - surely geometric aesthetics aren't that important.
Sue De Coq
Posts: 93
Joined: 01 April 2005

Postby Guest » Sat Apr 02, 2005 2:19 am

Well, as a new convert to the course, I'll try to explain without being too evangelical! The steps you describes for the X-wing may work, but are not necessary.

I've just coded this in my solver and it works a treat, without ever assuming a value for any of the four squares. The logic goes like this -

Find two rows where a give digit appears only twice and in the same two columns (thus forming a rectangle, or X).

Remove that digit as a possibility from the other cells in the two columns.

This obviously works if you swap rows and columns too.

This is because you know that the digit in question must, for each column be on one of the two rows, therefore it can't be anywhere else on those columns.

Make sense?

BTW - I may have a bug, as I knocked the code out quickly, but it doesn't solve Shakers puzzle. I'll report back on that :o)

Postby Guest » Sat Apr 02, 2005 2:23 am

That English was pretty embarassing :o(

I really ought to go to bed now!

Postby Guest » Sat Apr 02, 2005 2:30 am

Was a bug, it does solve Shakers - there is an X of 1s in cols 4 & 6

Postby Sue De Coq » Sat Apr 02, 2005 2:39 am

IJ - don't go to bed - it's only 2.30am and there's plenty more mileage in this debate yet.

Your explanation is fine - though it might have been a little clearer to say 'Find two rows where a given digit appears as a possibility only twice'. I fully accept the validity of X-Wings - my issue is that I can't see why Nishio (II from the recent example) should be declared invalid.
Sue De Coq
Posts: 93
Joined: 01 April 2005

Postby Guest » Sat Apr 02, 2005 2:53 am

It maybe 2:30 where you are, but it's half past sloshed here!

They are very different because the technique you describe is necessary (as far as I can see) for the Nishio, but not for the X-wing. The X-wing allows you to eliminate possibilities without the "Assume rYcX = Z" stage.

You just need to find the pattern, and then you can remove possibilities from other cells. This is much like finding 3 cells where the possibilities are limited to three values (such as 12, 23, 13), and eliminating those three values from the rest of the unit - It doesn't tell you how the 1,2 & 3 are arranged, nor do you have to try them, but it does tell you that they can't be anywhere else.

BTW for clarification, and to add to the evidence of alcohol tonight, it was an X of 3s in cols 2 & 8 in Shakers puzzle, not what I said before.

Postby Sue De Coq » Sat Apr 02, 2005 3:21 am

Clearly, X-Wings is far more computationally efficient than Nishio, of which it is a special case. Wayne will have to rule on whether all proof by contradiction, even that as trivial as in II, is invalid in true Sudoku.

I can't see how II could be expressed in a logically-positive form that might validate it in others' eyes. Any ideas?

At worst, Nishio could reveal geometric patterns of invalid cells for given values that could hint at logically-positive rules.
Sue De Coq
Posts: 93
Joined: 01 April 2005

Postby Guest » Sat Apr 02, 2005 3:54 am

Well, I'd been feeling dumb before, but now I feel extraordinarily brainy. I have had an epiphany!

Nishio is as valid as X-Wing, and does not require T&E. I'll repeat that (I'm feeling so smug - don't you hate it!) - It does not require T&E, assumptions nor is it a proof by contradiction.

Go back to the example of the 7s...

You have two columns (1 & 6) where 7 is only possible in two cells. In this case those possibilities are on 3 rows (1, 7 & 8), though it could be four.

Now, as per the X-Wing, you can discount 7 from rows 1, 7 & 8 for all cells except those in columns 1 & 6. So in this case 7 can be eliminated from r1c9, r7c3 and r8c4.


I'm sure you're unconvinced - go back and check! At no stage have I either assumed, or directly learnt anything about the two key columns, or the four key cells - just used their current state to eliminate possibilities elsewhere.

I think this is beautiful - It fits the criteria of being a pattern that can be recognised and used to eliminate possibilities without ever having to test a value in a cell.

So, neither X-wing or Nishio are T&E, or more accurately, they do not require T&E. I might even go so far as to say that neither is really unfair - just difficult.

Now back to that solver program...

Postby Sue De Coq » Sat Apr 02, 2005 4:07 am

Perhaps it finally is time you went to bed, IJ. You can't eliminate 7 from r1c9. Check the puzzle solution!

The geometry doesn't work here. There are three possibilities for a 7 in c6, so the presence of a 7 in r8c1 (it's there in the final solution) doesn't enforce a 7 at r1c6.
Sue De Coq
Posts: 93
Joined: 01 April 2005

Postby Guest » Sat Apr 02, 2005 4:21 am

Quite so. I knew it all along. :o)

Postby Sue De Coq » Sat Apr 02, 2005 4:27 am

I've appreciated your opinions tonight, IJ. I've just implemented X-Wings in my solver ... and it flies!
Sue De Coq
Posts: 93
Joined: 01 April 2005


Return to Published puzzles