The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections

Postby AW » Sat Feb 17, 2007 2:39 pm

{removed posted too early in the morning}

Stupid "improvements" break program again... fixed now.
AW
 
Posts: 27
Joined: 31 January 2007

Postby ab » Sat Feb 17, 2007 5:41 pm

ronk wrote:
AW wrote:Is my back-door finder broken or does Mike's

Code: Select all
500000009020100070008000300040702000000050000000006010003000800060004020900000005


really not have any strict back-door pairs (that crack the puzzle with only naked or hidden singles remaining) ????

If I understand your meaning of "backdoor pairs" ...

(r1c5=7 and r9c6=8) or (r2c6=9 and r9c8=4) or (r5c8=3 and r7c9=6)

... require only following singles.


I wondered about this. I think the thing is it's possible to put other pairs in those cells without getting a straight-forward contradiction.
ab
 
Posts: 451
Joined: 06 September 2005

Postby ronk » Sat Feb 17, 2007 5:50 pm

ab wrote:I wondered about this. I think the thing is it's possible to put other pairs in those cells without getting a straight-forward contradiction.

Correct, there are three possible outcomes to an assumptive pair of assertions: 1) contradiction, or 2) solution or 3) neither.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby StrmCkr » Sun Feb 18, 2007 9:14 am

hey here's another

11.4 rated pattern..

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


Code: Select all
 *-----------*
 |*..|...|..*|
 |.*.|..*|.*.|
 |..*|...|*..|
 |---+---+---|
 |..*|...|*..|
 |.*.|*..|.*.|
 |*..|...|..*|
 |---+---+---|
 |...|*.*|.*.|
 |...|.*.|...|
 |.*.|*..|...|
 *-----------*


i also found it weird that the 7 in r6c7 can be placed in r9c6 as well and still have a valid 1 solution puzzle.

omiting this 7 creates 120 diffrent solutions
where all other numbers moved individually create 500+ solutions.


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


Code: Select all
 *-----------*
 |*..|...|..*|
 |.*.|..*|.*.|
 |..*|...|*..|
 |---+---+---|
 |..*|...|*..|
 |.*.|*..|.*.|
 |*..|...|..*|
 |---+---+---|
 |...|*..|.*.|
 |...|.*.|...|
 |.*.|*.*|...|
 *-----------*
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 673
Joined: 05 September 2006

Postby ronk » Sun Feb 18, 2007 2:09 pm

StrmCkr wrote:hey here's another

11.4 rated pattern..

[edit: skip to 2nd puzzle]
Code: Select all
 *-----------*
 |9..|...|..5|
 |.7.|..1|.2.|
 |..3|...|8..|
 |---+---+---|
 |..8|...|3..|
 |.2.|4..|.6.|
 |5..|...|..9|
 |---+---+---|
 |...|2..|.4.|
 |...|.5.|...|
 |.1.|6.7|...|
 *-----------*
[edit:incorrect cite showed r7c6=7 instead of r9c6=7]

Your puzzle can be permuted to ...
Code: Select all
 9 . . . . . . . 5
 . 7 . 1 . . . 2 .
 . . 3 . . . 8 . .
 . 1 . 7 . 6 . . .
 . . . . 5 . . . .
 . . . . . 2 . 4 .
 . . 8 . . . 3 . .
 . 2 . . . 4 . 6 .
 5 . . . . . . . 9
 

... which is the same pattern as m_b_metcalf's puzzle here.
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . .
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5  # SE at least 11.4

I didn't check for equivalency.

[edit: AFAIK this pattern with an additional clue at r6c4 was first presented by JPF here. If anyone is aware of prior history please advise, either here or by PM as you deem appropriate. TIA, Ron]
Last edited by ronk on Mon Feb 19, 2007 1:30 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sun Feb 18, 2007 3:39 pm

ronk wrote:Your puzzle can be permuted to ...
...
... which is the same pattern as m_b_metcalf's puzzle here.
...
I didn't check for equivalency.

Don't think they are equivalent, but very close. Some quick manual swapping gives:
Code: Select all
 *-----------*
 |5..|...|..9|
 |.2.|1..|.7.|
 |..8|...|3..|
 |---+---+---|
 |.4.|..2|...|
 |...|.5.|...|
 |...|7.6|.1.|
 |---+---+---|
 |..3|...|8..|
 |.6.|..4|.2.|
 |9..|...|..5|
 *-----------*

The same as Mike's puzzle, except that one given '7' has moved from r4c4 to r6c4.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Sun Feb 18, 2007 6:48 pm

m_b_metcalf wrote:Here is a cousin of the first, almost an isomorph, but the central value is a repeat of r3c3 and r7c7, rather than of r1c1 and r9c9:
Code: Select all
 3 . . . . . . . 4
 . 8 . 2 . . . 7 .
 . . 6 . . . 5 . .
 . 1 . 9 . 8 . . .      SE >=11.4
 . . . . 6 . . . .
 . . . . . 7 . 2 .
 . . 5 . . . 6 . .
 . 9 . . . 1 . 8 .
 4 . . . . . . . 3

I'm not sure to which puzzle "cousin of the first" refers, but it [edit3: is] isomorphic to this:
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . .  SE at least 11.4
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5

Belated congratulations for breaking Sudoku Explainer rating records:!:

[edit: replaced this post after deleting it because I thought it was a duplicate]:(
Last edited by ronk on Mon Feb 19, 2007 1:06 am, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Sun Feb 18, 2007 8:21 pm

ronk wrote:
StrmCkr wrote:hey here's another

11.4 rated pattern..

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

Your puzzle can be permuted to ...
Code: Select all
 9 . . . . . . . 5
 . 7 . 1 . . . 2 .
 . . 3 . . . 8 . .
 . 1 . 7 . 6 . . .
 . . . . 5 . . . .
 . . . . . 2 . 4 .
 . . 8 . . . 3 . .
 . 2 . . . 4 . 6 .
 5 . . . . . . . 9
 

... which is the same pattern as m_b_metcalf's puzzle here.
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . .
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5  # SE at least 11.4

I didn't check for equivalency.

Ron, obviously (in Carcul's sense) you were under the effect of some substance when you made the above post...:D

If you swap bands 2 & 3 of StrmCkr's puzzle, and then reverse each row, you'll find it's 100% identical to m_b_metcalf's puzzle...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Sun Feb 18, 2007 8:41 pm

ronk wrote:
m_b_metcalf wrote:Here is a cousin of the first, almost an isomorph, but the central value is a repeat of r3c3 and r7c7, rather than of r1c1 and r9c9:
Code: Select all
 3 . . . . . . . 4
 . 8 . 2 . . . 7 .
 . . 6 . . . 5 . .
 . 1 . 9 . 8 . . .      SE >=11.4
 . . . . 6 . . . .
 . . . . . 7 . 2 .
 . . 5 . . . 6 . .
 . 9 . . . 1 . 8 .
 4 . . . . . . . 3

I'm not sure to which puzzle "cousin of the first" refers, but it appears to be isomorphic to this:
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . .  SE at least 11.4
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5

Ron, the "cousin" is isomorphic to the following puzzle:
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 6 . 2 . . .
 . . . . 5 . . . .
 . . . . . 7 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5

Which if you look carefully, has 2 different clues to the original puzzle (r4c4 & r6c6 being swapped)... So I think they're definitely non-isomorphic cousins... (Wrong conclusion!)

Edited: As Ron has shown below, he was right all along about this one... If we add one more transformation (anti-diagonal reflection) these 2 puzzles are isomorphic to each other...
Last edited by udosuk on Sun Feb 18, 2007 11:03 pm, edited 4 times in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Sun Feb 18, 2007 8:55 pm

To recap, here is m_b_metcalf's original SE 11.4 puzzle:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
.....6.1.
..3...8..
.6...4.2.
9.......5

Where he later found a cousin by swapping r4c4 & r6c6: (Note: this is isomorphic to the original)
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.6.2...
....5....
.....7.1.
..3...8..
.6...4.2.
9.......5

And it seems StrmCkr has found a 2nd cousin to the original, by moving the 7 from r4c4 to r6c4 (and thanks Ron and RW for re-permutations):
Code: Select all
5.......9
.2.1...7.
..8...3..
.4...2...
....5....
...7.6.1.
..3...8..
.6...4.2.
9.......5




Along the lines, I'm proposing 3 more cousins to this family::)
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
...6...1.
..3...8..
.6...4.2.
9.......5

5.......9
.2.1...7.
..8...3..
.4...2...
....5....
...6.7.1.
..3...8..
.6...4.2.
9.......5

5.......9
.2.1...7.
..8...3..
.4.6.2...
....5....
...7...1.
..3...8..
.6...4.2.
9.......5

The 3rd cousin is created by moving the 6 from r6c6 to r6c4 from the original. The 4th and 5th are created by exchanging the 6 & 7 in b5 from the 2nd & 3rd cousins respectively...

Could someone please check if all 6 of these puzzles are non-isomorphic to each other, and all have an SE rating of 11.4?

Edited: as Ron pointed out, the 4th & 5th puzzles each has 2 solutions, and the 6th is just isomorphic to the 3rd (from StrmCkr) with an anti-diagonal reflection...
Last edited by udosuk on Sun Feb 18, 2007 11:04 pm, edited 2 times in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Sun Feb 18, 2007 9:36 pm

udosuk wrote:Where he later found a cousin by swapping r4c4 & r6c6:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.6.2...
....5....
.....7.1.
..3...8..
.6...4.2.
9.......5

Wouldn't that be a reflection about the anti-diagonal making puzzles 1 & 2 isomorphic?

udosuk wrote:Could someone please check if all 6 of these puzzles are non-isomorphic to each other, and all have an SE rating of 11.4?

Obviously (in Carcul's sense), you've contracted a case of buck fever.:)

Puzzles 4 & 5 each have 2 solutions. Puzzle 6 is puzzle 3 reflected about the anti-diagonal.

gsf's solver shows only the following (your puzzles 1 & 3) to be non-isomorphic.

udosuk wrote:m_b_metcalf's original SE 11.4 puzzle:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
.....6.1.
..3...8..
.6...4.2.
9.......5

[...]

And it seems StrmCkr has found a [...] cousin to the original, by moving the 7 from r4c4 to r6c4:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4...2...
....5....
...7.6.1.
..3...8..
.6...4.2.
9.......5
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Mon Feb 19, 2007 3:09 am

Ron, you're darn right about the buck fever...:oops:

Hopefully you'd be the doctor who cured it and stopped it from spreading around any further...:)

Okay, let's give a thorough recap one last time...

Mike Metcalf originally posted this marvellous SE 11.4 puzzle in this post:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
.....6.1.
..3...8..
.6...4.2.
9.......5

Later, in this post, he claimed he'd found a "cousin" to the original puzzle:
Code: Select all
3.......4
.8.2...7.
..6...5..
.1.9.8...
....6....
.....7.2.
..5...6..
.9...1.8.
4.......3

Little did he realise, it is actually isomorphic to the original, via the following transformations:
Code: Select all
1. r1<->r3, r7<->r9, c1<->c3, c7<->c9
2. Permutation of symbols: [123456789]->[418395726]
3. Anti-diagonal reflection

Later, in this post, StrmCkr posted this puzzle:
Code: Select all
9.......5
.7...1.2.
..3...8..
...2.7.4.
....5....
.1.6.....
..8...3..
.2.4...6.
5.......9

... which is just the original puzzle reflected horizontally. (BTW I don't think it's an automorphism because this isomorphism is applicable universally to all puzzles... You can only call it "automorphic" if there is a particular transformation which will change a certain puzzle to an isomorphic form of itself but won't work on some other puzzles...)

Next, in this post, StrmCkr posted these two:
Code: Select all
9.......5
.7...1.2.
..3...8..
..8...3..
.2.4...6.
5.......9
...2.7.4.
....5....
.1.6.....


9.......5
.7...1.2.
..3...8..
..8...3..
.2.4...6.
5.......9
...2...4.
....5....
.1.6.7...

He didn't realise the 1st one is another isomorphic clone to the original (r456 <-> r789, horizontal reflection) but he did find a genuine non-isomorphic cousin in his 2nd puzzle, best transformed to the following for comparison of Mike Metcalf's original form:
Code: Select all
5.......9
.2.1...7.
..8...3..
.4...2...
....5....
...7.6.1.
..3...8..
.6...4.2.
9.......5

The only change is 7 is moved from r4c4 to r6c4...

In the very next post, Ron made an attempt to transform the 1st puzzle to the original, but somehow performed the permutation on the 2nd one instead, therefore missing the obvious isomorphic relationship between StrmCkr's first puzzle and Mike Metcalf's original...

And shortly after, I made 3 quick posts, with 2 of them containing errors (I overlooked the anti-diagonal reflection being an isomorphic transformation and didn't check puzzles for multiple solutions)...

So I've corrected my mistakes, and hopefully this run of carelessness would stop right here...:) Off to watch the NBA All-star game now...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby StrmCkr » Mon Feb 19, 2007 11:05 am

sweet i thought i found something there : )
i knew the first two where isomophiric (just pointing out a pattern that could work)..then i found the 7 could move around by testing each number for pattern changes and the 7 controlls solution count of less 500 (where all other numbers controlls 500+) and placemnts that happens cover all 120 soultions falls in 2 specific locations in that puzzle giving 2 similar grids.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 673
Joined: 05 September 2006

Postby ravel » Mon Feb 19, 2007 11:08 am

Thanks Mike for the information by Nicolas, how to reserve more memory for Explainer.

I updated the post, i am pointing to from the top page, how to get the ratings.
I also added the options for gsf's program how to canonicalize sudokus (for determining isomorphic sudokus), to calculate (singles) backdoor cells/pairs and to get all minimal puzzles to a sudoku.

Concerning the backdoors, gsf's backdoor conjecture is still living (every sudoku has at least one pair of singles backdoor cells). The puzzles with fewest backdoor pairs i know are dml07/1 (2) and Mike M's puzzle above with 3.

StrmCkr's variant of Mikes puzzle is a bit easier for my program - 14 points and 5 subnets in the first step (compared to 16/6) and also has much more backdoor pairs, namely 13.
[Added:] This is Explainers output for the variant (ER 11.4):
61 Hidden Single
4 Pointing
3 Claiming
4 Naked Pair
1 X-Wing
3 Hidden Pair
2 Naked Triplet
1 Swordfish
2 XY-Wing
3 Bidirectional Y-Cycle
3 Turbot Fish
4 Bidirectional Cycle
14 Forcing Chain
2 Nishio Forcing Chains
7 Region Forcing Chains
1 Cell Forcing Chains
1 Dynamic Cell Forcing Chains
1 Dynamic Double Forcing Chains
6 Dynamic Region Forcing Chains
11 Dynamic Contradiction Forcing Chains
5 Dynamic Contradiction Forcing Chains (+)
6 Dynamic Contradiction Forcing Chains (+ Forcing Chains)
6 Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Wed Feb 21, 2007 3:26 pm

ravel wrote:Thanks Mike for the information by Nicolas, how to reserve more memory for Explainer.


Well, back from a long weekend and I see lots of dust in the air. I'm glad the information from Nicolas is useful. I accept that my two puzzles were only one (I found them independently and didn't investigate the isomorphisnm sufficiently). The only question that remains is that, like JPF, I'm surprised that neither the 21-clue parents at SE 10.7 (and gsfr=99992 ) nor the 20-clue derivatives at 11.4 make it into your most difficult list:( . Is some recalibration called for?

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8427
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to General