Top95: Our common benchmark?

Ruud · Site Admin

I can see that #290 and #314 were equivalent.

#351 is missing a 3 in r6c6, when added, it's equivalent to the other 2.

#73 and #81 are also equivalent (toughest known)

I don't think that the symmetry has anything to do with it's toughness. You can permutate this puzzle into a non-symmetrical variant, that would have the same difficulty level.

Ruud.

dukuso · Posted: Sat Nov 05, 2005 4:20 am Post subject:

OK, I removed equivalent ones and superfluous clues now.
The result is at:
http://magictour.free.fr/top870
870 nonequivalent sudokus over 861 nonequivalent grids
I can't say, where I got the puzzles from. They were picked from other
people's lists, from internet postings, from randomly generated
sudokus etc..
I'm always interested to get new hard sudokus to be included
in that list. Please send them to sterten(at).com if they rate
more than 600 with
http://magictour.free.fr/suexrate.exe

the reason why symmetric puzzles often rated high could be just
because many people generate symmetric puzzles, from which
the hardest are then filtered and the rest forgotten.

-Guenter.

Bob Hanson · Posted: Sat Nov 05, 2005 4:39 am Post subject:

Solved in 59 steps by Sudoku Assistant http://www.stolaf.edu/people/hansonr/

Step 8 is the key logical step:

Bob Hanson · Posted: Sat Nov 05, 2005 4:50 am Post subject:

Ah, this is a great list. Thank you! #5 there illustrates that subset elimination in general requires a sort of "subset" hypothesis and proof that I've not implemented in Sudoku Assisant. Excellent.

.4.7...6...39............57.......3.2...8.....19...57.6...4.....5.1......2...6.84
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

rubylips · Posted: Sat Nov 05, 2005 11:14 am Post subject:

Ruud · Site Admin

Funny how different solvers have a different approach at handling these puzzles.

#5 Enabled my solver to spot the following, before it required tabling:

- Hidden triple in box 5
- Naked triple in col 5
- Coloring digit 7 inconsistent chain
- Uniqueness test 4 in R36C56

I do like the uniqueness test 4. The samples given by others often require me to disable other techniques, otherwise it dissolves before it can be spotted.

Ruud.

Bob Hanson · Posted: Sat Nov 05, 2005 1:57 pm Post subject:

oops. OK, very sorry about that long URL. I won't do that again!
I don't suppose it is possible for me to go back and edit that....

regarding

.4.7...6...39............57.......3.2...8.....19...57.6...4.....5.1......2...6.84

and uniqueness.

OK, so the subset thing is this:

Say you want to solve a puzzle strictly with forcing chains and no bifurcation. Then I think there are (at least) two options:

a) look for subsets the "standard way"

b) recognize that when doing that final, critical hypothesis step of "N-1 FALSE, so Nth TRUE" that in itself establishes somewhat of a "subset" of the board. I haven't explored this except to convince myself that if you do NOT do this, you need to bifurcate.

So, for example, you can leave out block-based row/column exclusions (block-based Xwings and such), but you cannot leave out subset elimination (tuples, xwings, swordfish, and such) if using strictly force-chain logic (forward or reverse) to solve a puzzle. With no bifurcation.

This is easily demonstrated with this particular puzzle.

Am I correct there?

Regarding uniqueness tests. I guess if they are helping your solver they are helping your solver. Can you show us the exact point in this solution where your solver applies the uniqueness test?

I understand that you are saying that there are other placements of 1 and 2, but each 12 there is a short strong chain. Each is doubly linked, either in a weak fashion (because that X is there) or in a strong fashion (because no other 1 or 2 is there) to each other. Or are there also other X and Y in there right in the 12 cells?

Here's what I observe:

Say you have other 1s and 2s there:

12 ..... 12.....1

12 ..... 12........2

If this falls to a uniqueness test, ok, but I guess it's hard to believe that really helps if you are also using forcing chains. Because on the bottom row there, for example, we have the strong chain 2--1--1--2, which forces elimination of the 2 on the right. Likewise for the 1. So this simply CANNOT arise in a valid, unique-solution Sudoku.

Same goes for that 4x4 grid just presented.

The

12....12X

right there (provided no more 1s or 2s are in that row) constitutes a uniqueness violation ALREADY. It just can't be there. (Because simple logic eliminates the X just in terms of subsets on that line.)

I guess it all depends where the other 1s and 2s are.

I think the uniqueness test is a great and clever idea. Probably what I'm missing is a good actual example of what you are talking about. If this puzzle does the trick, great. Can you send us the full grid so we can see the uniqueness test step?

Thanks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Here is the diagram:

Moschopulus · Posted: Sat Nov 05, 2005 11:37 pm Post subject:

rubylips · Posted: Sat Nov 05, 2005 11:46 pm Post subject:

Yes, the 3 in r6c6 is superfluous. The puzzle appeared three times in the original list of 888 - twice with the 3, once without. Personally, I like it in.
_________________
Java 5.0 Solver/Composer Applet: http://act365.com/sudoku
GPL Source Code: http://sf.net/projects/sudoku

Lummox JR · Posted: Sun Nov 06, 2005 7:28 am Post subject:

A minor qualm so far:

In Bob's post last night, it appears that his implementation of bifurcating chains is broken. Specifically at least the j in column 9, digit 6, should have become K in all 6's for that column, box, and row. That's not the only problem, though, because there's absolutely no way to go from B to b. Note the complete lack of any lowercase b in the puzzle; Bob's analysis skipped to c instead. I come up with this analysis:

Bob Hanson · Posted: Sun Nov 06, 2005 2:03 pm Post subject:

Well, I know that one's pretty messy. But I asure you it is correct. The reason there is no "b" is that in this case it must have been that there were no "free" nodes to assign "b" to. I think if you load that table into Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku (using the Number BLock Input, which reads just about anything), you will see that the logic step "b" doesn't add anything new. So it just went on.

It is correct that the two lowercase "h"s in row 7 provide the necessary proof in the end. It must have stopped there.

When I load this one, I'm not getting exactly the same proof, but the idea is the same.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Lummox JR · Posted: Sun Nov 06, 2005 5:56 pm Post subject:

Bob Hanson · Posted: Sun Nov 06, 2005 7:48 pm Post subject:

OK, let me see if I can figure this out. The problem is, between that posting and now, I did some rearranging in the code, and I'm not coming up with the same logic step. But I'll try.

One thing to keep in mind is that if a node has already been labeled, it isn't
labeled again.

Lummox JR · Posted: Tue Nov 08, 2005 1:10 am Post subject:

Yes, I'm using bifurcating chains as described by Nick70, with the exception of course that he didn't describe the proof in which a placement may be false.

But it's clear that the diagram you posted didn't do that quite right. Where there should be b's, there are c's. Oddly enough though there are still C's, which shouldn't even be possible under the circumstances. You have a j in column 9 that never propagated K's in the next step. I believe your solver is looking at the first clue it can propagate, and then moving on without propagating others. That doesn't explain the missing b's, but it does explain how you could have a j and a v in the same constraint. That shouldn't be possible because the j should propagate K's all through column 9 for the 6's.