The hardest sudokus

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

Postby udosuk » Thu Nov 13, 2008 9:48 pm

eleven wrote:
Mauricio wrote:One more automorphic puzzle
Code: Select all
+-------+-------+-------+
| . . . | . . 1 | . . 2 |
| . 1 . | . 3 . | . 4 . |
| . . 5 | 6 . . | . . . |
+-------+-------+-------+
| . . 2 | 7 . . | 8 . . |
| . 8 . | . . 4 | . 3 . |
| 1 . . | . 9 . | . . . |
+-------+-------+-------+
| . . . | 3 . . | 5 . . |
| . 9 . | . 8 . | . 1 . |
| 6 . . | . . . | . . 7 |
+-------+-------+-------+ ER=11.3/11.3/10.5
Again very easy to solve. After clearing the diagonal there is a UR 1.1 (12 or 16), then only 2 pairs to the end.

There are 2 paths to solve this puzzle.



Path 1 - using a "pseudo UR" (sorry, forgot the official name of this technique), i.e. the path adopted by eleven:

After filling the leading diagonal with the 3 self-mapping digits {1,5,7}, and applying the ensuring singles:

Code: Select all
+----------------------+----------------------+----------------------+
| 7      346    34689  | 459    45     1      | 369    5689   2      |
| 289    1      689    | 59     3      2789   | 679    4      5689   |
| 23489  234    5      | 6      247    2789   | 1      789    389    |
+----------------------+----------------------+----------------------+
| 459    45     2      | 7      6      3      | 8      59     1      |
| 59     8      679    |*2     *1      4      | 679    3      569    |
| 1      3467   3467   | 8      9      5      | 2467   267    46     |
+----------------------+----------------------+----------------------+
| 248    247    1      | 3      247    2679   | 5      2689   4689   |
| 2345   9      347    | 45     8      267    | 2346   1      346    |
| 6      2345   348    |*1     -245    29     | 2349   289    7      |
+----------------------+----------------------+----------------------+

Consider r59c45: these 4 cells are not part of the initial givens, so can't form a deadly pattern (otherwise the original puzzle must have multiple solutions). Therefore r9c5 can't be 2.

Thus r19c5={45} (naked pair @ c5).

4 @ r3,b1 locked @ r3c12, can't be @ r1c23.
4 @ r4,b4 locked @ r4c12, can't be @ r6c23.
4 @ c3,b7 locked @ r89c3, can't be @ r789c12.

Hidden single @ r7: r7c9=4.
Symmetry: r9c7=9.

All naked singles from here.

(eleven seems to suggest that this puzzle can be solved by 2 pairs and singles only after the pseudo UR. I don't see how to do this. I have to use 1 naked pair and 3 intersections (aka locked candidates) plus singles to finish it.:( )



Path 2 - without using UR-related techniques:

From the above pencilmark grid:

r1c45+r2c4={459} (naked triple @ b2).
r4c12+r5c1={459} (naked triple @ b4).

4 @ r3,b1 locked @ r3c12, can't be @ r1c23.
9 @ c3,b1 locked @ r12c3, can't be @ r23c1.
9 @ r3,b3 locked @ r3c89, can't be @ r12c789.

r1c27={36} (naked pair @ r1).

Code: Select all
+-------------------+-------------------+-------------------+
| 7     36    89    | 459   45    1     | 36   *58    2     |
| 28    1     689   | 59    3     278   | 67    4     568   |
| 2348  234   5     | 6     27    278   | 1     789   389   |
+-------------------+-------------------+-------------------+
| 459   45    2     | 7     6     3     | 8    *59    1     |
| 59    8     67    | 2     1     4     | 679   3     569   |
| 1     367   367   | 8     9     5     | 2467  267   46    |
+-------------------+-------------------+-------------------+
| 248   247   1     | 3     247   2679  | 5    *2689  4689  |
| 2345  9     347   | 45    8     267   | 2346  1     346   |
| 6     2345  348   | 1     245   29    | 2349 *289   7     |
+-------------------+-------------------+-------------------+


Now consider r79c8.
By symmetry these 2 cells can't be {26}.
So r79c8 must have at least one of {89}.
Thus r1479c8 form a killer naked triple {589} @ c8.
Therefore r36 can't have {589}.

Hence, r3c8=7.
Symmetry: r8c3=7.

All naked singles from here.

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Fri Nov 14, 2008 8:45 pm

Code: Select all
Dark Reflector (ER=11+)

.....1..2
..1.2..3.
.4.5..6..
...7...5.
..3..8...
6...1.9..
..9.7.2..
.7...9.4.
8..1....9

Solvable with hidden singles, naked singles, hidden pairs, simple uniqueness (and without pencilmarks).:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Mauricio » Sat Nov 15, 2008 10:39 am

Anyone interested in the hardest automorphic sudokus I found, the list is here, 1318 puzzles. First move is very difficult, unless you use Gurth's ST.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Glyn » Sat Nov 15, 2008 6:21 pm

udosuk For Dark Reflector.
Did you do some careful counting to determine something special about the pairs 1-9,3-6,4-5 and the single digits 2,7 and 8?
Then something special about Boxes 3,4 and 8?
Just locked 2's + singles to find.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby ronk » Sat Nov 15, 2008 7:51 pm

udosuk wrote:
Code: Select all
Dark Reflector (ER=11+)

.....1..2
..1.2..3.
.4.5..6..
...7...5.
..3..8...
6...1.9..
..9.7.2..
.7...9.4.
8..1....9

Solvable with hidden singles, naked singles, hidden pairs, simple uniqueness (and without pencilmarks).:!:

Applied permutation -pr(14)(25)(36)(89)c(12)(49)(57)(68) for ...
Code: Select all
 . . . | . . 5 | . . 7
 . . 3 | . . . | . 8 .
 . 6 . | . 9 . | 1 . .
-------+-------+-------
 . . . | 2 . . | . 1 .
 . . 1 | . . 3 | 2 . .
 4 . . | . 6 . | . . 5
-------+-------+-------
 . . 9 | . 2 . | 7 . .
 . 8 . | 9 . . | . . 1
 7 . . | . . 4 | . 9 .

... but I still had to use pencilmarks.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Sun Nov 16, 2008 3:36 am

Great observation ronk! Nothing gets by you!:)



However you don't need that much work to transform the grid. Just reorder the rows as the following:

r546879231

You can easily permute the rows using Notepad etc. Anything involving columns permutation/rotation/transposing is tedious to do without special tools.



Code: Select all
..3..8...
...7...5.
6...1.9..
.7...9.4.
..9.7.2..
8..1....9
..1.2..3.
.4.5..6..
.....1..2

Here are the steps to solve it without PM:

1. Knowing what should be on d\ (leading diagonal), you can fill in r4c4 & r6c6. Also inspecting r2 (or c2) you should know what must go in r2c2. Hence you can also fill in r1c1 & r3c3.

2. Now you can find 2 hidden pairs, one in r1c2+r2c1, another in r7c9+r9c7. This enables you to fill in r2c3+r3c2 & r8c9+r9c8.

3. The hidden pair in r7c9+r9c7 should enable you to find 2 hidden singles in r3c9+r9c3.

It's all singles from here, although finding naked singles without PM is not that straight forward, but should be manageable by most.:idea:



Besides the puzzle, here are 2 bonus challenges for you guys::)

1. Why is the puzzle such named?

2. Why do I use this particular isomorph?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Sun Nov 16, 2008 8:45 am

udosuk wrote:You can easily permute the rows using Notepad etc. Anything involving columns permutation/rotation/transposing is tedious to do without special tools.

the -p option of my solver applies row,col,value,transpose cyclic permutations
also, given two isomorphic puzzles, it can list the cyclic permutation that maps the first to the second
ronk showed the -p form in his post
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Mon Nov 17, 2008 5:53 am

gsf I regard your solver as a very special tool.:)

For the people still puzzled about my name and isomorph selection, here is another puzzle:

Code: Select all
Hiring Mr Irons

.2...67..
4...8..3.
..83.....
..9..3..5
.8..1..9.
7..9..1..
...5...4.
6....1...
.9..3...2

See if you can see the underlying connections.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Mon Nov 17, 2008 6:51 am

Same thing.

Too easy when using the symmetry (just a hidden pair), but what a monster without.
Added: Ah, very same, its equivalent to the last one.
eleven
 
Posts: 1536
Joined: 10 February 2008

Postby udosuk » Mon Nov 17, 2008 1:18 pm

eleven, the game now is not about how to solve the puzzles but to figure out the names and reasons for the particular isomorphs. There are three puzzles involved, two posted by me and one posted by someone else...

Perhaps it can help you notice something if you look at one of the solution grids.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Sat Nov 22, 2008 3:52 am

Okay, time to reveal answers.

My "Dark Reflector" and "Hiring Mr Irons" are both isomorphs of Mauricio's "Shining Mirror" (available on the previous page). These 3 are special in that they are all lexicographically minimal in some ways.

Of course, "Hiring Mr Irons" is just an anagram of "Shining Mirror" while "Dark Reflector" is meant to be a hint to make readers associate to that name. "Reflector" is a synonym of "Mirror" while "Dark" is an antonym of "Shining" (because the reflection symmetry of Mauricio's puzzle was obvious while mine was somewhat hidden).

My point is, if Mauricio had posted his puzzle in the form of "Dark Reflector" I bet it wouldn't have been cracked so easily (without extra hints). Then it would have given a bigger impression to the newcomers of automorphism/symmetry (such as champagne & Allan Barker).

Sorry for sidetracking this thread for so long. Now it can be back to its normal role (for posting the hardest sudokus).:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Sat Nov 22, 2008 4:44 am

udosuk wrote:Okay, time to reveal answers.
My "Dark Reflector" and "Hiring Mr Irons" are both isomorphs of Mauricio's "Shining Mirror" (available on the previous page). These 3 are special in that they are all lexicographically minimal in some ways. ...

My point is, if Mauricio had posted his puzzle in the form of "Dark Reflector" I bet it wouldn't have been cracked so easily (without extra hints). Then it would have given a bigger impression to the newcomers of automorphism/symmetry (such as Champagne & Allan Barker).

OK udosuk; well done.

I stated long ago, answering to coloin, that in my view, any puzzle having an easy path to be cracked should be ranked consequently. This came when SK loop appeared.

Being consistent and unable to solve Mauricio's puzzle, I deducted that I had to include in my solver some symmetry analysis. I started implementation.

I was waiting for traps as your's:D

So I initiated a morphing analysis integrated in my solver.

Unhappily, I had in the same time to improve my first trial to handle Allan model, a much wider scope for resisting puzzles (including 2 unsolved as well on my side). So, my work on morphing has been delayed.:(


I am very much interested, to save time, in getting your detailed path connecting your puzzle to Mauricio's puzzle. (somehow the de morphing key). This can be a sample file to test my solver in due time.

My idea was that morphing has to take place after basic moves has been done (they must not destroy the symmetry. reversely, they must at my view fill the gap to the point where the symmetry appears).

BTW, nobody else found your trick. At least I can say I have been lazy or to much occupied, waiting for the answer.

May be Merlin made similar game!!!:D

(But I feel this was higher degree of sophistication).
champagne
2017 Supporter
 
Posts: 5650
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Sat Nov 22, 2008 5:14 am

champagne, thanks for your interest and kind words.:)

To show that 2 puzzles are isomorphs to each other, I think one of the easier approach is to normalise both grids and compare. There are 3 ways:

Method 1: work out the lexicographically minimal 81-char string of each puzzle.

Method 2: work out the lexicographically minimal 81-char string of the "mask of givens" of each puzzle, and then label the givens in the lexicographically minimal manner.

Method 3 (least preferred): solve the puzzles first (assuming they're solvable), and then work out the lexicographically minimal 81-digit string of the solutions (but you must keep track of the positions of the given clues).

Method 1 will give "Dark Reflector".

Method 2 will give "Shining Mirror".

Method 3 will give "Hiring Mr Irons".

Also, if the puzzle has diagonal reflection symmetry, method 2 should probably show the symmetry explicitly (because the "mask of givens" should follow the symmetry). However there might be rare counter-examples.

I think there are efficient algorithms to find the lexicographically minimal isomorphs of a given puzzle (one of the above 3 ways) but I'm currently working out one myself (as an exercise in my limited leisure time).:idea:



PS: I'm not anticipating the rugby match between our corresponding countries. Not after the disappointment in tonight's world cup final.:(
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Sat Nov 22, 2008 6:49 am

udosuk wrote:Method 1: work out the lexicographically minimal 81-char string of each puzzle.

Method 2: work out the lexicographically minimal 81-char string of the "mask of givens" of each puzzle, ...

Method 3 (least preferred): ...
Method 1 will give "Dark Reflector".
Method 2 will give "Shining Mirror".
Method 3 will give "Hiring Mr Irons".


From that I understand these are just morphs of the initial with same number of given. Easier to use as sample file.

It should not be a problem to come back to a symmetry.

I have my own algortithm to find isomorphs. Here the problem is slightly different. Gsf has one option in his program to create isomorphs with the "best symmetry". It is more that kind of task the solver has to do, knowing that we are only looking for puzzles having really a symmetry of given.

The next trap, as you said, is that, if the puzzle is not minimal, some given can be erased. In that case, you have first to find them back (if possible), before establishing the symmetry. I thought it was the case here.

Thanks for clarification

champagne
champagne
2017 Supporter
 
Posts: 5650
Joined: 02 August 2007
Location: France Brittany

Postby coloin » Sat Nov 22, 2008 10:54 am

I get it now..... but there are hefty assumptions going on here [how are you supposed to know ? !]
Code: Select all
+---+---+---+
|...|..5|..7|
|..3|...|.8.|
|.6.|.9.|1..|
+---+---+---+
|...|2..|.1.|
|..1|..3|2..|
|4..|.6.|..5|
+---+---+---+
|..9|.2.|7..|
|.8.|9..|..1|
|7..|..4|.9.|
+---+---+---+


There is [simultaneous] paired clue symmetry for 4 pairs of clues in the grid solution.

[1-9] 2-perm unavoidable [1xU18]
[3-6] 2-perm unavoidable [1xU18]
[4-5] 2-perm unavoidable [1xU18]
[2-7] 8-perm unavoidable [3xU6]

Code: Select all
+---+---+---+
|214|835|967|
|973|641|582|
|568|792|143|
+---+---+---+
|837|259|614|
|651|483|279|
|492|167|835|
+---+---+---+
|149|328|756|
|385|976|421|
|726|514|398|
+---+---+---+



The line of syymmetry diagonal is not specified either.

the paired clue values arnt specified, although intuitively they can be guessed at

Of couse - all the puzzles from this grid solution will have an extra easy method of solving if you know thw pairings and the symmetry. Admittedly the clue removals to make the puzzle would have to me done with this symmetry in mind.

Edit, 1255/1318 of mauricios's puzzles were from different grids.

the grid solutions all have identical pairs of 3 bands and 3 chutes.

[index416 of one of the grid solutions [ 113 255 376 , 113 255 376]]


I am not sure that this technique can be tested for and used generally.

C
coloin
 
Posts: 1632
Joined: 05 May 2005

PreviousNext

Return to General