The New Sudoku Players' Forum

by **tso** » Fri Jul 29, 2005 7:34 pm

This post is primarily about solving technique and difficulty ratings.

I found this puzzle interesting.

Code: Select all: . 8 . | 7 . 5 | . 4 . . 9 2 | 8 . 1 | 6 3 . 7 . . | . . . | . . 1 -------+-------+------ . . 6 | . 8 . | 2 . . . . . | . . . | . . . . . 9 | . 5 . | 4 . . -------+-------+------ 3 . . | . . . | . . 9 . 1 7 | 5 . 3 | 8 2 . . 6 . | 4 . 9 | . 1 .

I got to the position below *very* quickly -- maybe 5 minutes -- without using any pencil marks:

Code: Select all: 6 8 1 | 7 3 5 | 9 4 2 5 9 2 | 8 4 1 | 6 3 7 7 . . | . . . | 5 8 1 -------+-------+------ . . 6 | . 8 . | 2 . 3 . . . | . . . | 1 . . . . 9 | . 5 . | 4 7 . -------+-------+------ 3 . . | 2 1 8 | 7 6 9 9 1 7 | 5 6 3 | 8 2 4 2 6 8 | 4 7 9 | 3 1 5

It took a couple minutes longer to see that at this point I would have to enter some pencil marks. As is my custom, I filled in only those cells that had exactly 2 candidates, shown below. Only if I cannot solve a puzzle with 2 candidates per cell do I fill the cells that need 3, etc. It's too much work to fill them in and is often overkill. Plus it makes it harder for me to see the connections. Other cells are left blank here for clarity:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . 34 34 |69 29 26 | . . . ----------+-----------+---------- 14 57 . |19 . 47 | . 59 . 48 . 35 | . 29 47 | . 59 68 18 23 . | . . 26 | . . 68 ----------+-----------+---------- . 45 45 | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

No other pencil marks or any other kind of notations were required to finish the puzzle.

At this point, I identified the groups of cells that were connected in such a way that they could only be in one of two states, for example, the eight cells r3c12468 + r4c168 + r5c1 could only be in one of these two states:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . -------+-------+------ 1 7 . | 9 . 4 | . 5 . 4 . . | . . 7 | . 9 . 8 . . | . . . | . . . -------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . or . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . -------+-------+------ 4 5 . | 1 . 7 | . 9 . 8 . . | . . 4 | . 5 . 1 . . | . . . | . . . -------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

I find four such groups plus one lone cell:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . b b | c c c | . . . -------+-------+------ a a . | a . a | . a . a . b | . c a | . a d a e . | . . c | . . d -------+-------+------ . b b | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

A proof, either by contradiction or forcing chains, must form a loop connecting at least two groups. (I haven't proved this, but since I'm defining a group as having two possible internally consistent states, it must be so.)

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . 34 34 |69 29 26 | . . . ----------+-----------+---------- 14 57 . |19 . 47 | . 59 . 48 . 35 | . 29 47 | . 59 68 18 23 . | . . 26 | . . 68 ----------+-----------+---------- . 45 45 | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

Looking only for connections between groups, I find one using groups A, C and D:

1) r3c6=2 => r6c6=6 => r6c9=8 => r6c1=1
2) r3c6=6 => r3c4=9 => r4c4=1 => r4c1=4 => r6c1=1
3) Therefore, r6c1=1 and the rest solves quickly.

Just the cells involved in the solution with the rest removed for clarity:

Code: Select all: . . . | . . . | . . . . . . | . . . | . . . . . . |69 . (26)| . . . ----------+-----------+---------- 14 . . |19 . . | . . . . . . | . . . | . . . (18) . . | . . 26 | . . 68 ----------+-----------+---------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

Ok, my point: Other than filling in the candidate pairs, my total solving time was *maybe* 10 minutes, yet this puzzle was rated TOUGH.
(The puzzle is from today's LA Times.)

Paul's Pages (http://www.paulspages.co.uk/sudoku/) says: "WARNING - This puzzle has an 'outlaw' rating. During verification, it was not solved using the five solving rules described in 'How to solve Sudoku'. It may be necessary to use guesswork to solve it. Try it if you're tough enough!"

Argusj's Simple Sudoku is unable to solve it.

The solver at http://act365.com/sudoku/ says it requires a "guess".

It seems like the consensus on ratings for puzzles that require forcing chains and similar tactics is out of whack. Some of the puzzles in the Times and the UK Telegraph have even simpler forcing chains at the end and still get these ratings. This one stands out for me because the first part of the puzzle was soooo easy and solved so quickly. Puzzles that require swordfish or multiple x-wings, hidden trips, etc. are subjectively *much* more difficult for me, by a level of magnitude. You have to decide what to look for, where to look, and even then, it can be tedious. Plus, it is often *objectively* more difficult because it *requires* that you fill in *all* the candidates, even in cells that might have 4 or more -- and do so in a way that you can read your own writing. Even if I KNOW there's a swordfish and I'm taking the easy way out by using Argusj's Simple Sudoku to filter for it -- it's still easy for me to overlook it.

I know that difficulty is partly subjective, but maybe puzzles that include this type of structure shouldn't automatically be considered especially difficult. This was really only medium difficulty -- and if rated exclusively by solving time, it was the very easy.

Also, I don't claim the way I solved this is the only way or even the best way, only *a* way. It's what is easiest for me given my personal preferences -- I prefer to use less pencil marks if possible and solve as much in my head. I've posted several solutions using forcing chains previously, but this is the first time that I've tried show that I actually have a method to find them rather than just blindly searching. (Explaining is much harder than the doing.)

Is the identifying of connected groups like this of any interest to anyone else?

What do you see are the pros and cons of using different tactics to complete this puzzle from the sticking point? Would you have used colors? Assuming you solved this on paper, would you use additional notations?

Does anyone see a way that this puzzle could have been finished without using *any* pencil marks or notations of any kind?

by **simes** » Fri Jul 29, 2005 9:18 pm

Hi TSO,

This is a subject I've been looking into recently. I've just added rating to my solver (BTW, it can solve this puzzle, and rates it HARD)

Yes, rating is very subjective. A hard puzzle one day, may be easy the next, and vice versa of course.

My solver's rating is based on the techniques required to solve it, and the "length" of those techniques. For example, a quad is harder than a triplet is harder than a pair (look here for the current rating system - it'll probably get fine tuned - or even completely rehashed when people discover it rates their "fiendish" puzzle is mild.)

Simes

by **su_doku** » Sat Jul 30, 2005 12:07 am

TSO

Interesting puzzle. I am not sure whether this logical thought is right but if it is it could be a simpler way to solve from the "easy" point you reached.

Looking at row 5, note that as a pair 2,7 are restricted from occupying
r5c1, r5c3, r5c4, r5c7 and r5c8 ie 5 cells in that row. Of the 3 cells that remain where the 2,7 could go, r5c6 is certain to have either a 4 or 7.

Thus this "overlap" introduces a 4 to the 2 7 we are seeking a home for within 3 cells. Hence is it not the case that 2, 4, 7 now form a "chained triplet" that must occupy r5c2, r5c5 and r5c6?

Consequently r5c5=2 and the rest solves fom there.

by **Nick70** » Sat Jul 30, 2005 12:06 pm

Hi tso,
thanks for the usual clever arguments.

My solver currently rates the puzzle as "diff 13 [forcing chain] (chain score 501)". This is just slightly harder than xy-wing (which would have a 400 chain score).

The chain found by my program is shorter than yours, but it passes through a cell that has four candidates:

Code: Select all: Found a forcing chain: r5c3=3 => r6c2<>3 => r6c2=2 => r5c2<>2 => r5c5=2 r5c3=5 => r5c8<>5 => r5c8=9 => r5c5<>9 => r5c5=2 - Put 2 in r5c5

I am very interested in the intricacies of rating sudoku difficulty. It is a very complex matter. Did you see my post about rating EASY puzzles? That's already a difficult task.

The increasing levels of difficulty I am currently using are
0) single candidate
1) single sector candidate
2) naked pairs
3) hidden pairs
4) x-wing
5) naked triplets
6) hiddent triplets
7) swordfish
8) naked quadruples
9) hidden quadruples
10) jellyfish
11) xy-wing
12) turbot fish
13) double forcing chains
14) multi forcing chains
15) guessing

Note: I still have to find a puzzle that falls in the 9) or 10) categories. All the ones I have are either below or above that.

The could be a lot of arguing about the order above. You could say for example that a xy-wing is easier to see than even a hidden pair under certain circumstances.

The number of times each technique has to be used is also a factor in the perceived difficulty. This is made even more complicated by the fact that a more advanced technique might allow to proceed further, therefore making the solution easier in the end. But when we rate a puzzle, how can we know which route will the solver take? Techniques that allow to place a big number instead of just removing candidates should probably take precedence. But will the player see them? Will she apply a single forcing chain that solves all, or will she apply three consecutive x-wings to remove enough candidates to move ahead?

There are so many factors that influence how difficult a chain is to see. To a computer all constraints are the same, but to the human eye they aren't. Just the position on the grid can change how obvious a clue is to the human solver, and of course it will be different from person to person.

One thing that's certainly true is that solving with or without pencilmarks, on paper or on computer, are completely different games.

by **angusj** » Sat Jul 30, 2005 12:21 pm

Nick70 wrote:9) hidden quadruples
Note: I still have to find a puzzle that falls in the 9) or 10) categories. All the ones I have are either below or above that.

It took me quite a while to generate a "hidden quad" puzzle too:

Code: Select all: 4..|..9|61. ..5|6..|.79 .1.|42.|3.. ----------- .51|.6.|... ...|...|... ...|.1.|83. ----------- ..7|.83|.6. 53.|..6|7.. .69|2..|..3

Also, you seem to be missing "Locked Candidates" from your list.

Otherwise, I'm in general agreement with your difficulty scale, though I think simple colouring could slot in below "Naked Triples" and I'd move "Hidden Triples" below Swordfish.

Edit: here's my tentative scale of difficulty ...

by **Nick70** » Sat Jul 30, 2005 3:07 pm

angusj wrote:It took me quite a while to generate a "hidden quad" puzzle too:

You don't need hidden quad for that, hidden triplet is enough.

The cause of the rarity of hidden quad puzzles is that in a unit with 8 free cells or less, a hidden quad is the dual of a simpler pattern - from naked quad down to naked pair. So to find a "pure" hidden quad you need 9 free cells in a unit.

angusj wrote:Also, you seem to be missing "Locked Candidates" from your list.

That's what I call "single sector candidate".

by **tso** » Sat Jul 30, 2005 6:15 pm

su_doku wrote:TSO

Interesting puzzle. I am not sure whether this logical thought is right but if it is it could be a simpler way to solve from the "easy" point you reached.

Looking at row 5, note that as a pair 2,7 are restricted from occupying
r5c1, r5c3, r5c4, r5c7 and r5c8 ie 5 cells in that row. Of the 3 cells that remain where the 2,7 could go, r5c6 is certain to have either a 4 or 7.

Thus this "overlap" introduces a 4 to the 2 7 we are seeking a home for within 3 cells. Hence is it not the case that 2, 4, 7 now form a "chained triplet" that must occupy r5c2, r5c5 and r5c6?

At this point, though we know that r5c6 MAY be either 4 or 7, we *don't* know that r5c2+r5c5+r5c6 MUST contain a 4. At this point, 4's could be at r5c1 and r4c6 instead ...

su_doku wrote:Consequently r5c5=2 and the rest solves fom there.

... and r5c5 could still be 9.

by **tso** » Sat Jul 30, 2005 6:55 pm

Hi Nick,

Nick70 wrote:
The increasing levels of difficulty I am currently using are
0) single candidate
1) single sector candidate
2) naked pairs
3) hidden pairs
4) x-wing
5) naked triplets
6) hiddent triplets
7) swordfish
8) naked quadruples
9) hidden quadruples
10) jellyfish
11) xy-wing
12) turbot fish
13) double forcing chains
14) multi forcing chains
15) guessing

I don't feel as strongly about it as I did a month ago, but I feel that tactics that can do not require using cells with 3 or more candidates are -- especially for paper solvers -- generally easier. I don't know if my method is representitive, but I never fill in cells with 3 or more candidates until I can go no further. This means that in some cases I may find a forcing chain before having a chance to try many of the other tactics that would require all cells to have all candidate lists complete.

Nick70 wrote:The could be a lot of arguing about the order above. You could say for example that a xy-wing is easier to see than even a hidden pair under certain circumstances.

Absolutely.

by **angusj** » Sat Jul 30, 2005 10:35 pm

Nick70"][quote="angusj wrote:You don't need hidden quad for that, hidden triplet is enough.

Well, in my solver, the hidden quad is required for row 5 which has nine blank cells.
This is the point I got to where I needed a hidden quad:

Code: Select all: {4} {7} {3} {8} {5} {9} {6} {1} {2} {28} {28} {5} {6} {3} {1} {4} {7} {9} {9} {1} {6} {4} {2} {7} {3} {58} {58} {37} {5} {1} {379} {6} {8} {29} {249} {47} {367} {2489} {248} {3579} {49} {245} {15} {59} {1567} {67} {249} {24} {579} {1} {245} {8} {3} {567} {12} {24} {7} {159} {8} {3} {29} {6} {145} {5} {3} {248} {19} {49} {6} {7} {29} {148} {18} {6} {9} {2} {7} {45} {15} {458} {3}

by **angusj** » Mon Aug 01, 2005 12:05 pm

angusj wrote:
Nick70 wrote:You don't need hidden quad for that, hidden triplet is enough.

Well, in my solver, the hidden quad is required for row 5 which has nine blank cells.
This is the point I got to where I needed a hidden quad:
Code: Select all
{4} {7} {3} {8} {5} {9} {6} {1} {2} {28} {28} {5} {6} {3} {1} {4} {7} {9} {9} {1} {6} {4} {2} {7} {3} {58} {58} {37} {5} {1} {379} {6} {8} {29} {249} {47} {367} {2489} {248} {3579} {49} {245} {15} {59} {1567} {67} {249} {24} {579} {1} {245} {8} {3} {567} {12} {24} {7} {159} {8} {3} {29} {6} {145} {5} {3} {248} {19} {49} {6} {7} {29} {148} {18} {6} {9} {2} {7} {45} {15} {458} {3}

by **angusj** » Mon Aug 01, 2005 12:08 pm

angusj wrote:Well, in my solver, the hidden quad is required for row 5 which has nine blank cells.

Well, water under the bridge and a few posts lost here due to the server reload. Anyhow, there was a bug in my solver and of course Nick was right.

Anyhow, here's a real "hidden quad":

Code: Select all: 5.2|6..|7.. ...|9..|.1. ...|...|385 ----------- ..4|.96|1.. ...|...|... ..5|27.|9.. ----------- 837|...|... .6.|..9|... ..9|..8|2.3

by **Nick70** » Mon Aug 01, 2005 1:18 pm

angusj wrote:Anyhow, here's a real "hidden quad":

True, nice find.

Try looking for a Jellyfish now!

by **Nick70** » Tue Aug 02, 2005 12:20 pm

After paying attention to how I solve puzzles manually, it's obvious to me that I use the turbot fish pattern an awful lot, so I've decided to move it where it belongs in the difficulty scale: after x-wing, but before swordfish.

I've also moved swordfish before hidden triplet, since at least with candidate filtering it's much easier to see.

I still have to decide where to put xy-wing.

Unfortunately the changes made the "hidden quad" example above no longer rate as such

Turbot fish and swordfish (or hidden triplet) are enough to solve it.

So the quest for the hidden quad is still open

The New Sudoku Players' Forum

Ratings of puzzles needing forcing chains; connected groups

Ratings of puzzles needing forcing chains; connected groups