The New Sudoku Players' Forum

by **PhilC** » Fri Mar 03, 2006 3:28 am

Another hard one, well maybe just hard for me.

Code: Select all: +-------+-------+-------+ | . 9 . | . . . | . . . | | 4 . . | 5 . . | . . 1 | | 8 . . | . . 6 | . 2 . | +-------+-------+-------+ | . 3 . | . 7 . | 9 . . | | . 5 . | . . 8 | . 6 . | | . . 1 | . . . | . 4 . | +-------+-------+-------+ | . 7 . | 3 . . | . . 5 | | 2 . . | . . 9 | . . 8 | | . . . | . . . | . 3 . | +-------+-------+-------+ +---------------+---------------------+--------------+ | 3 9 2567 | 12478 1248 1247 | 456 57 46 | | 4 26 267 | 5 9 237 | 368 78 1 | | 8 1 57 | 47 34 6 | 345 2 9 | +---------------+---------------------+--------------+ | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | +---------------+---------------------+--------------+ | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | +---------------+---------------------+--------------+

Any help appreciated!

by **QBasicMac** » Fri Mar 03, 2006 4:34 am

r5c5 must be 2,3,or 4.

But trying 2 leads to this invalid result

Code: Select all: +-------------+-----------------+--------------+ | 3 9 267 | 128 18 12 | 456 7 46 | | 4 6 267 | 5 9 23 | 6 78 1 | | 8 1 5 | 7 4 6 | 3 2 9 | +-------------+-----------------+--------------+ | 6 3 8 | 14 7 14 | 9 5 2 | | 7 5 4 | 9 2 8 | 1 6 3 | | 9 2 1 | 6 3 5 | 8 4 7 | +-------------+-----------------+--------------+ | 1 7 6 | 3 68 24 | 246 9 5 | | 2 46 3 | 4 5 9 | 467 1 8 | | 5 468 9 | 1248 168 1247 | 2467 3 46 | +-------------+-----------------+--------------+

And trying 4 leads to this invalid result

Code: Select all: +------------+-------------------+------------+ | 3 9 567 | 2478 128 1247 | 6 5 6 | | 4 26 6 | 5 9 2 | 368 7 1 | | 8 1 57 | 7 3 6 | 4 2 9 | +------------+-------------------+------------+ | 6 3 4 | 1 7 5 | 9 8 2 | | 7 5 2 | 9 4 8 | 1 6 3 | | 9 8 1 | 26 26 3 | 5 4 7 | +------------+-------------------+------------+ | 1 7 68 | 3 268 24 | 26 9 5 | | 2 46 3 | 467 5 9 | 67 1 8 | | 5 46 9 | 24678 1268 1247 | 267 3 46 | +------------+-------------------+------------+

Therefore r5c5=3

After some simple work, we at least get this far

Code: Select all: +-------------+-----------------+-------------+ | 3 9 67 | 128 128 12 | 456 57 46 | | 4 26 267 | 5 9 3 | 68 78 1 | | 8 1 5 | 7 4 6 | 3 2 9 | +-------------+-----------------+-------------+ | 6 3 48 | 14 7 145 | 9 58 2 | | 9 5 24 | 24 3 8 | 1 6 7 | | 7 28 1 | 9 6 25 | 58 4 3 | +-------------+-----------------+-------------+ | 1 7 68 | 3 28 24 | 246 9 5 | | 2 46 3 | 46 5 9 | 7 1 8 | | 5 468 9 | 12468 128 7 | 246 3 46 | +-------------+-----------------+-------------+

Trying 5 at r6c6 gives this invalid result:

Code: Select all: +-----------+--------------+----------+ | 3 9 6 | 18 128 12 | 5 7 4 | | 4 27 | 5 9 3 | 6 8 1 | | 8 1 5 | 7 4 6 | 3 2 9 | +-----------+--------------+----------+ | 6 3 8 | 14 7 14 | 9 5 2 | | 9 5 4 | 2 3 8 | 1 6 7 | | 7 2 1 | 9 6 5 | 8 4 3 | +-----------+--------------+----------+ | 1 7 | 3 28 24 | 24 9 5 | | 2 46 3 | 46 5 9 | 7 1 8 | | 5 48 9 | 148 128 7 | 24 3 6 | +-----------+--------------+----------+

So r6c6=2

That solves easily.

Mac

by **PhilC** » Fri Mar 03, 2006 4:42 am

Hm, I don't like using trial & error..

by **tso** » Fri Mar 03, 2006 7:48 am

Code: Select all: +---------------+---------------------+--------------+ | 3 9 2567 | 12478 1248 1247 | 456 57 46 | | 4 26 267 | 5 9 237 | 368 78 1 | | 8 1 57 | 47 34 6 | 345 2 9 | +---------------+---------------------+--------------+ | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | +---------------+---------------------+--------------+ | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | +---------------+---------------------+--------------+

Take a look at the four cells r26c67. Let's filter everything except 3s, 5s and 8s in those four cells:

Code: Select all: +---------------+---------------------+--------------+ | . . . | . . . | . . . | | . . . | . . 3 | 38 . . | | . . . | . . . | . . . | +---------------+---------------------+--------------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . 35 | 58 . . | +---------------+---------------------+--------------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +---------------+---------------------+--------------+

The 8s are conjugates. (That is, they are the only two places in that column that can hold an 8.)
The 5s are conjugates.

The 3s in row 2 are conjugates.
The 3s in column 6 are conjugates.

Either r6c6 AND r2c7 are BOTH 3 or NEITHER are 3. But if both are 3, then r6c7 must hold both a 5 and an 8. Therefore you can exclude 3 from both r2c7 and r6c6.

Stated another way:
r6c6=3 -> r2c6<>3 -> r2c7=3 -> r6c7=8 -> r6c6=5 -- contradiction
Therefore, r6c6<>3

[EDIT]

I should have stated it as a forcing chain:

r6c7=5 -> r2c7=8 -> r2c6=3
r6c7=8 -> r6c6=5 -> r2c6=3
Therefore r2c6=3

This is *exactly* the same structure as an xy-wing -- but it uses STRONG links instead of WEAK links. Could it be as common? If so, does it rate a name? Strong wing?

by **tarek** » Fri Mar 03, 2006 11:56 am

This is not simple & not the best way to solve it, however it solves it without forcing chains & no contradiction elimination, & it gives a chance to experiment with ALS (Edited):

Code: Select all: *--------------------------------------------------------------------------* | 3 9 -2567 | 12478 1248 1247 |%456 57 %46 | | 4 ^26 267 | 5 9 237 |-368 78 1 | | 8 1 57 | 47 34 6 | 345 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 ^28 1 | 269 236 235 |*58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | *--------------------------------------------------------------------------* Eliminating 6 from r1c3(ALS-XY A=58 in r6c7 B=268 in r2c2,r6c2 C=456 in r1c9,r1c7 x=8 y=5 z=6) Eliminating 6 from r2c7(ALS-XY A=58 in r6c7 B=268 in r2c2,r6c2 C=456 in r1c9,r1c7 x=8 y=5 z=6) The next step is just short of a classic wxyz wing: *--------------------------------------------------------------------------* | 3 9 257 | 12478 1248 -1247 | 456 57 46 | | 4 26 267 | 5 9 *237 | 38 78 1 | | 8 1 57 |*47 *34 6 | 345 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 ^24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | *--------------------------------------------------------------------------* Eliminating 4 from r1c6(ALS-XZ A=2347 in r3c4, r3c5, r2c6 B=24 in r7c6 x=2 z=4) *--------------------------------------------------------------------------* | 3 9 257 | 12478 1248 127 | 456 57 46 | | 4 26 267 | 5 9 237 | 38 78 1 | | 8 1 57 | 47 34 6 | 345 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | *--------------------------------------------------------------------------* Eliminating 7 from r1c4(ALS-XY A=345 in r3c5,r3c7 B=4567 in r1c8,r1c9,r1c7 C=47 in r3c4 x=5 y=4 z=7) Eliminating 7 from r1c6(ALS-XY A=345 in r3c5,r3c7 B=4567 in r1c8,r1c9,r1c7 C=47 in r3c4 x=5 y=4 z=7) *--------------------------------------------------------------------------* | 3 9 257 | 1248 1248 12 | 456 57 46 | | 4 26 267 | 5 9 237 | 38 78 1 | | 8 1 57 | 47 34 6 | 345 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | *--------------------------------------------------------------------------* Eliminating 2 from r2c6(ALS-XY A=58 in r4c8 B=1245 in r7c6,r1c6,r4c6 C=2678 in r2c8,r2c2,r2c3 x=5 y=8 z=2) Then some naked doubles & Box-line eliminations *--------------------------------------------------------------------------* | 3 9 57 | 128 128 12 | 46 57 46 | | 4 26 26 | 5 9 37 | 38 78 1 | | 8 1 57 | 47 34 6 | 35 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 2467 3 46 | *--------------------------------------------------------------------------* r9c7 must only contain 27 (Candidates 46 in r1c7,r1c9,r9c7 & r9c9 form a type-1 unique quadrangle) Next was the step earlier mentioned by PhilC: *--------------------------------------------------------------------------* | 3 9 57 | 128 128 12 | 46 57 46 | | 4 26 26 | 5 9 37 | 38 78 1 | | 8 1 57 | 47 34 6 | 35 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 234 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 27 3 46 | *--------------------------------------------------------------------------* Eliminating 4 from r5c5(ALS-XY A=258 in r6c7,r6c2 B=345 in r3c5,r3c7 C=24 in r5c3 x=5 y=2 z=4) *--------------------------------------------------------------------------* | 3 9 57 | 128 128 12 | 46 57 46 | | 4 26 26 | 5 9 37 | 38 78 1 | | 8 1 57 | 47 34 6 | 35 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 23 8 | 1 6 37 | | 79 28 1 | 269 236 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 27 3 46 | *--------------------------------------------------------------------------* Eliminating 2 from r6c4(ALS-XZ A=258 in r6c7, r6c2 B=235 in r5c5, r6c6 x=5 z=2) Eliminating 2 from r6c5(ALS-XZ A=258 in r6c7, r6c2 B=235 in r5c5, r6c6 x=5 z=2) *--------------------------------------------------------------------------* | 3 9 57 | 128 128 12 | 46 57 46 | | 4 26 26 | 5 9 37 | 38 78 1 | | 8 1 57 | 47 34 6 | 35 2 9 | |------------------------+------------------------+------------------------| | 6 3 48 | 14 7 145 | 9 58 2 | | 79 5 24 | 249 23 8 | 1 6 37 | | 79 28 1 | 69 36 235 | 58 4 37 | |------------------------+------------------------+------------------------| | 1 7 68 | 3 2468 24 | 246 9 5 | | 2 46 3 | 467 5 9 | 467 1 8 | | 5 468 9 | 124678 12468 1247 | 27 3 46 | *--------------------------------------------------------------------------* r6c6 Must only have 25 as valid Candidates (258 is a Hidden Triple in Row 6) (or the naked Quad)

You can see how complex the ALS XZ & XY rules can be

Tarek

by **vidarino** » Fri Mar 03, 2006 12:15 pm

Here's a Nice Loop that uses the same information as in tso's post:

R2C6=3=R2C7=8=R6C7=5=R6C6=3=R2C6 -> R2C6=3, almost solving the puzzle.

("Almost", because you'll need an XY-Wing a bit later, but the rest is singles.)

Vidar

by **PhilC** » Fri Mar 03, 2006 8:23 pm

Thanks for the help!

Tarek, those ALS examples do help, I'm actually starting to understand how they work. Is it common in ALS-XY that set A is only one cell with 2 candidates?

Do you have any tips on how to look for ALS? It's quite obvious from your post that there's almost always an ALS to be found.

Oh, in the last ALS example, does set B really need to be 2457? Can't it just be the one cell with 24?

by **tarek** » Sat Mar 04, 2006 12:12 am

hi PhilC,

I hope that I'm not going to confuse you, but the A,B,C group assignments are different from what benny's original assignments in ALS thread.

I basically see it as your ordinary xy wing........ the A being your xy cell & then the other 2 ALSs are B & C...... the xy wing being the simplest form of the ALS xy rule (a 3 node ALS xy)

so we have 3 groups one central which is A and 2 (wings or branches...) which are B & C. B should have a common restricted candidate with A. C should have a common restricted candidate with A.

So to spot one, you first go for that central ALS(simple first) & then look for possible wings & branches(again simple first) ....... Not easy (My solver can search for up to 15 nodes on a sytematic basis)

for your secong question......... you're right the 24 should be enough.

My solver apparantly has a bug somewhere missing the easier option....

Tarek

by **ronk** » Sat Mar 04, 2006 1:31 pm

tso wrote:I should have stated it as a forcing chain:

r6c7=5 -> r2c7=8 -> r2c6=3
r6c7=8 -> r6c6=5 -> r2c6=3
Therefore r2c6=3

This is *exactly* the same structure as an xy-wing -- but it uses STRONG links instead of WEAK links.

Here is another from this thread.

Code: Select all: 2 8 3 | 46* 5 46* | 1 9 7 7 6 5 | 89 189 19 | 2 4 3 14 14 9 | 7 2 3 | 58 58 6 -------------------+-------------------+----------------- 56 35 4 | 1 68 7 | 9 358 2 156 12359 12 | 2389 4 29 | 568 7 58 8 239 7 | 239 69 5 | 46 13 14 -------------------+-------------------+----------------- 9 124 12 | 5 7 8 | 3 6 14 3 7 6 | 29 19 1249 | 458 158 58 145 145 8 | 46* 3 146* | 7 2 9

A UR type1 (marked by asterisks) solves the puzzle. However, looking instead at only at the 2s, 3s and 9s:

Code: Select all: . . . | . . . | . . . . . . | 9 9 9 | . . . . . . | . . . | . . . -------------+-------------+----------- . 3 . | . . . | . 3 . . 239 2 | 239 . 29 | . . . . 239 . | 239 9 . | . 3 . -------------+-------------+----------- . 2 2 | . . . | . . . . . . | 29 9 29 | . . . . . . | . . . | . . .

Because of conjugate links in 3s in row 5 and col 4, in 2s in row 6, and in 9s in col 2 ...
r5c4<>3 -> r6c4=3 -> r6c2=2 -> r5c2=9 -> r5c4=3, a contradiction implying r5c4=3
... leading to cascading singles (as does the UR1 step above) to solve the puzzle.

But using Carcul's AUR type E3, an even shorter implication chain is ...
r5c4<>3 -> r6c2=3 -> r5c2=9 -> r5c4=3, also implying r5c4=3

[edit: made implication streams (chains) easier to read by starting new lines]

Ron

by **tarek** » Sat Mar 04, 2006 4:32 pm

I found the bug, my previous post will be updated, no Cell markings though

Tarek

by **tso** » Sat Mar 04, 2006 7:14 pm

ronk wrote:... looking instead at only at the 2s, 3s and 9s:
Code: Select all
. . . | . . . | . . . . . . | 9 9 9 | . . . . . . | . . . | . . . -------------+-------------+----------- . 3 . | . . . | . 3 . . 239 2 | 239 . 29 | . . . . 239 . | 239 9 . | . 3 . -------------+-------------+----------- . 2 2 | . . . | . . . . . . | 29 9 29 | . . . . . . | . . . | . . .

Because of conjugate links in 3s in row 5 and col 4, in 2s in row 6, and in 9s in col 2 ...
r5c4<>3 -> r6c4=3 -> r6c2=2 -> r5c2=9 -> r5c4=3, a contradiction implying r5c4=3

Stated as a pair of forcing chains:

r6c2<>2 -> r6c4=2 -> r6c4<>3 -> r5c4=3
r6c2<>9 -> r5c2=9 -> r6c4<>3 -> r5c4=3
Since r6c2 cannot be both 2 and 9, one of these two statements must be true and r5c4 MUST be 3.

The relevant candidates, all of which form conjugate pairs:

Code: Select all: . 39 . | 3 . 29 . | 23

Compare this pattern to an xy-wing, the shortest possible xy-type forcing chain:

Code: Select all: [12]|[13] ----+---- [14]|[34]

All values of [34] force [12] to be 2.

[34]=3 -> [13]=1 -> [12]=2
[34]=4 -> [14]=1 -> [12]=2
Therefore [12]=2

This is a STRONG WING. -- the shortest possible forcing chain using all strong (conjugate) links:

The 1s, 2s and 3s are conjugates in rows and columns. (Each cell may have any other candidates 4 through 9 -- noted with 'any' in each cell.)

Code: Select all: [1 any]|[12 any] --------+-------- [13 any]|[23 any]

All values of [23 any] force [1 any] to be 1.

[23 any]<>2 -> [12 any]=2 -> [12 any]<>1 -> [1 any]=1
[23 any]<>3 -> [13 any]=3 -> [13 any]<>1 -> [1 any]=1
Therefore, [1 any]=1

by **ronk** » Sat Mar 04, 2006 9:30 pm

tso wrote:This is a STRONG WING. -- the shortest possible forcing chain using all strong (conjugate) links:

The 1s, 2s and 3s are conjugates in rows and columns. (Each cell may have any other candidates 4 through 9 -- noted with 'any' in each cell.)

Code: Select all
[1 any]|[12 any] --------+-------- [13 any]|[23 any]

All values of [23 any] force [1 any] to be 1.

A generalized form of a Pure Bilocation Loop with a discontinuity might look like ...

Code: Select all: . . . | . . . | . . . . . 7A | . . 5A | 5a7a . . 2b7a . . | . . . | . . . ---------------+-------------+--------------- . . . | . . . | . . . . . . | . . . | . . . . . . | 5A . 5a | . . . ---------------+-------------+--------------- 2B5A . . | 5a . . | . . . . . . | . . . | . . . . . . | . . . | . . .

The loop is segmented into sub-chains, with a sub-chain per digit. In order to propagate implications, all but one of the sub-chains must have an odd number of links. The remaining sub-chain -- the location of the discontinuity -- must be have an even number of links.

We may examine the loop in terms of colors and the color exclusions. By inspection of the above,

(Color) 7a (true) excludes 5a (true), 5A excludes 2B, and 2b excludes 7a. This is contradiction and, therefore, 7a must be false.

I believe your "STRONG WING" is a subset of the above, and the '7A' in r2c3 corresponds to your '1 any' cell. I don't know about the other cells yet.

Ron

by **tso** » Sun Mar 05, 2006 3:40 am

ronk wrote:I believe your "STRONG WING" is a subset of the above, and the '7A' in r2c3 corresponds to your '1 any' cell. I don't know about the other cells yet.

Agreed. It is not a new pattern, simply the shortest example.

Code: Select all: [1 any]|[12 any] --------+-------- [13 any]|[23 any]

... or as you put it ...

Code: Select all: . . . | . . . | . . . . 1A . | . 1a2a . | . . . . . . | . . . | . . . ---------------+-------------+--------------- . 1a3b . | . 2A3B . | . . . . . . | . . . | . . . . . . | . . . | . . . 1a excludes 2a, 2A excludes 3B, 3b excludes 1a. This is a contradiction, therefore 1a must be false.

I'd find it less confusting with three colors though:

Code: Select all: . . . | . . . | . . . . 1A . | . 1a2c . | . . . . . . | . . . | . . . ---------------+-------------+--------------- . 1a3b . | . 2C3B . | . . . . . . | . . . | . . . . . . | . . . | . . . 'a' excludes 'c', 'C' excludes 'B', 'b' excludes 'a'. This is a contradiction, therefore'a' must be false.

The New Sudoku Players' Forum

Hard one

Hard one