The hardest sudokus

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

Postby udosuk » Sat Nov 22, 2008 1:07 pm

champagne wrote:From that I understand...

coloin wrote:I get it now...

But you guys have both missed the point completely.:!:

Note the term "lexicographically minimal" has nothing to do with the "minimality" of the puzzle grids. Perhaps I should have said "lexicographically smallest" instead.

None of the methods I specified is a sure-killing way to expose the symmetry of a given symmetrical puzzle (method 2 might have a very high success rate of exposing the diagonal symmetry but it is (probably) still not 100%).

The 3 isomorphs are all equivalent to each other on a puzzle perspective (as a result their solution must also be equivalent). Perhaps later I'll show you how to work them out step-by-step, in another thread.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Mauricio » Sat Nov 22, 2008 1:14 pm

There's a mathematical way to identify if a puzzle is isomorph to a puzzle with an "easy to see" automorphism:
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

If you have a software that can identify the automorphisms of a puzzle, then you can know that a automorhism of dark reflector is the following:
Reflect along the diagonal, then change the columns according to the permutation (157248369), in cyclic notation, and then change the rows according to the permutation (196384275) (note that the permutations of rows is inverse of the permutation of columns). From here one could identify that the given automorphism is conjugate of just reflecting along the diagonal, and so dark reflector has an isomorph which automorphism is easier to see.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby udosuk » Sat Nov 22, 2008 1:29 pm

coloin wrote: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|
+---+---+---+

Shouldn't there be unavoidables for these 2 pairs as well?

Code: Select all
+---+---+---+
|2..|8..|...|
|...|...|.82|
|..8|..2|...|
+---+---+---+
|8..|2..|...|
|...|.8.|2..|
|..2|...|8..|
+---+---+---+
|...|.28|...|
|.8.|...|.2.|
|.2.|...|..8|
+---+---+---+

+---+---+---+
|...|8..|..7|
|.7.|...|.8.|
|..8|7..|...|
+---+---+---+
|8.7|...|...|
|...|.8.|.7.|
|...|..7|8..|
+---+---+---+
|...|..8|7..|
|.8.|.7.|...|
|7..|...|..8|
+---+---+---+



Mauricio, does your identifying method work for all grids or just this particular puzzle?:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Mauricio » Sat Nov 22, 2008 1:50 pm

It shoudl work for all puzzles, but have in mind the following requirements
  1. A list of easy to see automorphisms.
  2. A software (preferentially) that can identify automorphism of a puzzle.
  3. Being able to identify if the automorphism obtained by 2, is conjugate of any of the automorphisms in the list given by 1.
Of course, a sophisticated solver using properties based on symmetries, should be capable of handling any automorphism, not just the easy ones.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby eleven » Sat Nov 22, 2008 2:35 pm

Mauricio wrote:Of course, a sophisticated solver using properties based on symmetries, should be capable of handling any automorphism, not just the easy ones.

At least so far i always could, when i knew, that there is one.
Can you post puzzles with hard automorphisms ?
eleven
 
Posts: 1582
Joined: 10 February 2008

Postby Mauricio » Sat Nov 22, 2008 2:59 pm

eleven wrote:
Mauricio wrote:Of course, a sophisticated solver using properties based on symmetries, should be capable of handling any automorphism, not just the easy ones.

At least so far i always could, when i knew, that there is one.
Can you post puzzles with hard automorphisms ?

I did not mean to use the word "hard", but "easy to indentify". Surely you could identify the automorphism of "Shining Mirror" easily, but how much did you take to identify the automorphism of "dark reflector"?
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby coloin » Sat Nov 22, 2008 4:45 pm

udosuk wrote:But you guys have both missed the point completely.:!:


not completely, maybe on a couple of pairs, but not on the isomorph issue.

you missed my question completely though:D

Given a random isomorph of said puzzle - How are you supposed to know the puzzle has these properties in the solution grid ?

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby champagne » Sat Nov 22, 2008 10:08 pm

coloin wrote:
udosuk wrote:But you guys have both missed the point completely.:!:


not completely, maybe on a couple of pairs, but not on the isomorph issue.

you missed my question completely though:D

Given a random isomorph of said puzzle - How are you supposed to know the puzzle has these properties in the solution grid ?

C


Nothing to add, except maybe the way I see it:

1) fill assigned candidates following basic rules
2) look for symmetry of (given + assigned) locations

if ok (likely several possibilities in some puzzles)

3) look for symmetries of (given + assigned) including paired digit.


This process is not 100% granted. In case a puzzle is given not symmetric (for locations) and basic rules can't fill the gap, detection of symmetry properties fail.

You still have the possibility to check whether the solution has the symmetry properties, but it is not the same game:D
champagne
2017 Supporter
 
Posts: 5745
Joined: 02 August 2007
Location: France Brittany

Postby eleven » Sun Nov 23, 2008 2:55 am

Mauricio wrote:... how much did you take to identify the automorphism of "dark reflector"?

For this pattern it is very clear, what you have to try.
There are 3 boxes with 2 candidates in a "rectangle".
So the only chance you have is to map box 1 to box 6 and box 4 to itself. The rest is routine and would be a nice kids game, if you could make band/stack/row/column changes, diagonal reflection and number cycling with clicks.
eleven
 
Posts: 1582
Joined: 10 February 2008

Postby udosuk » Sun Nov 23, 2008 7:30 am

If you guys are looking for a sure-killing way to identify any type of symmetry within a random isomorph of an automorphic puzzle then I'm afraid you'll be disappointed. There is no such thing. You must use your ingenuity and observation power to work it out. You can probably get some help from my POCKET principle though.

That said, for diagonal symmetry (one of the easiest-to-see of the 6 major automorphism types) there should be some systematic ways. My "method 2" of normalising a puzzle grid is one, Mauricio's "reflecting+rows/columns permutating" is another. But I'm not sure these methods are 100% bulletproof though.

Also, for diagonal symmetry you can morph any random isomorph to show the symmetry explicitly using rows permutations only. It needs some serious analysis though.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Sun Nov 23, 2008 8:24 am

Hm, to give an algorithm i would do it exactly as described above:

First find all possible pattern automorphisms, where the number in most cases is effectively reduced by the number and pattern of givens in the boxes (note that in any case a transformed band/stack always contains the same boxes, a minirow/column the same givens and so on), and then check, if number cycles can map to the original puzzle.
eleven
 
Posts: 1582
Joined: 10 February 2008

Postby Cuorenero » Sun Nov 30, 2008 5:39 am

Hi to everybody in the first place.
I'm relatively new to sudoku, so excuseme if some of my questions/answers will sound a bit naif:)

Is there a sudoku 9x9 puzzle with a unique solution that can be solved only by making a guess at some point ?
If there is one, it may be as well considered as the most difficult for a human, because one has to rely on chance.

Another curiosity about all the known rules for candidate elimination: can they be reversed ? What i mean by that is:
Can a candidate removal technique be used to place candidates in a bottom up construction of a puzzle ? Suppose you have a certain solution, one has to create a grid for which that filled square is a unique solution.
You remove a number, you place a candidate, or a set of them (according to general col-row-block uniqueness, or the aforementioned rules).
So, all one must do is to remove numbers from the grid accorging to rules someway "specular" to those of candidate elimination ? Reversing those eliminations would result in placement/candidate elimination.
This kind of inverse problem seems to me more fasible than that of pregenerating patterns and bruteforcing to find "difficult ones". I think in this way one can generate a puzzle of "arbitrary difficulty" (arbitrary in the sense of having as a result a puzzle that must unergo certain simplifications, defined one by one by the creator, in order to be solved), even by hand.

Please let me know if i told something incredibly stupid ;).
At times, the inverse problem is much more simple than the original one.
Cuorenero
 
Posts: 1
Joined: 29 November 2008

Postby champagne » Sun Nov 30, 2008 5:54 am

Cuorenero wrote:Is there a sudoku 9x9 puzzle with a unique solution that can be solved only by making a guess at some point ?
If there is one, it may be as well considered as the most difficult for a human, because one has to rely on chance.


Up to now, the answer is no if you use all known techniques.
Using the main process applied by my solver, full taging, at least three identified puzzles are not solved. One will disappear when symmetry properties will be integrated in the solver.

The 2 other puzzles are "relatively" easy to solve using Allan Barker model and AIC's integrating deadly patterns.

Regarding reverse process, I have the feeling that puzzles producers are following quite differents lanes.

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

Postby denis_berthier » Tue Dec 02, 2008 7:49 pm

Hi Cuorenero, Welcome on this forum,
Cuorenero wrote:Is there a sudoku 9x9 puzzle with a unique solution that can be solved only by making a guess at some point ?

All the known puzzles can be solved by singles after at most 3 guesses (but most of them after only 1 or 2); the minimal such number for a puzzle is called its backdoor size. The chances of making 3 correct random guesses are very low.
"Making a guess" must be distinguished from T&E (in Trial and Error, you just try a candidate z and eliminate it if it leads to a contradiction; you do nothing if it leads to a solution, i.e. you just keep z as a candidate and you forget this solution).
All the known puzzles can be solved using repeated T&E at depth 2 or less. This is a much stronger result than the previous one.
Still stronger: all the known puzzles can be solved with zt-braids(FP) for some relatively simple family FP of patterns (for details on all this, see the T&E vs braids" thread, here: http://forum.enjoysudoku.com/viewtopic.php?t=6390)

Now, the real question is: what do you consider as an acceptable pattern? And the answer can only be subjective. If you don't accept nets, it is likely you'll have a very hard time with the hardest puzzles. But how many players want to solve EasterMonster & C° for breakfast?
From a theoretical POV, the way I see all this is: given some set of resolution rules, what can I hope to solve with them? Some answers are provided in the aforementioned thread for different families of braids. Of course, there may be some difference between what I can hope to solve with these rules and what I'm effectively able to solve (it is likely that a human player won't find all the possibilities of applying these rules in a grid). But I think this is still a valuable indication.

Cuorenero wrote:Another curiosity about all the known rules for candidate elimination: can they be reversed ? What i mean by that is: Can a candidate removal technique be used to place candidates in a bottom up construction of a puzzle ? Suppose you have a certain solution, one has to create a grid for which that filled square is a unique solution.
You remove a number, you place a candidate, or a set of them (according to general col-row-block uniqueness, or the aforementioned rules).

There's no a priori reason why this couldn't be done - except perhaps the complexity of the procedure.
General purpose generators, such as suexg, generate random puzzles and can hardly provide very hard puzzles (which are very rare). For suexg, I've shown that all the puzzles generated in a collection of 1,000,000 could be solved by the simplest braids: nrczt-braids. (And for the first 10,000 of them, by simpler nrczt-whips.)
I've almost no experience in puzzle creation, but I tried to generate variants of EM with different x2y2-belts. I used SudokuExplainer. It has the advantage of propagating the elementary constraints. But it doesn't allow candidate elimination. It'd be a nice feature to be able to select a rule (or a set of rules) and apply all the eliminations it allows. That could help creating new puzzles in which no rule in the chosen set can be applied and which would accordingly be rated high.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby coloin » Sun Jan 04, 2009 6:12 am

Maybe these new puzzles may challenge .....

Code: Select all
.......1......4.32.2..3.5.......7....4..2...5..89..4....78..6...3..1..5.9........ # coly004 #
..6.....1.7.4...2.....5.3...8...7........4.8.9.28.......1...5...2.9...7.3.......6 # coly005 #
...1....8.7......9..3.9.5....8.3...57....23.....4..6....6.8..5.4....1...2........ # coly006 #
...2....87.......9..3.9.5....8.3...51.....3.....4..6....6.8..5..7...1...2....4... # coly007 #
...1....87.......9..3.9.5....9.3...5.....23.....4..6....6.8..5.47...1...2........ # coly008 #
7....4..8.1......9..6.9.5....8.6...5.....23.....4..6....3.8..5.2....1......7..... # coly009 #
.1......8.7...4..9..3.9.5....8.3...5.2....3.....4..6....6.8..5.2....1......7..... # coly010 #
.1...4..87.......9..6.9.5....8.6...5.2....3.....4..6....3.8..5.2..1........7..... # coly011 #
...1....87.......9..6.9.5....8.6...5.....23...7.4..6....3.8..5..2...1....4....... # coly012 #
....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7 # coly013 #


Code: Select all
# puzzle  # -q1   # -q2                          #  sx9 #  sxt
# coly004 # 99346 # 99246 FNBP C21.m/M3.323.1645 # 3876 # 1161
# coly005 # 95573 # 98759 FNBP C21.m/M2.1.144342 # 3444 # 2074
# coly006 # 13410 # 77102 FNBP C21.m/M2.23.285   # 5350 # 1543
# coly007 # 96827 # 98813 FNBP C21.m/M2.1.577368 # 5842 # 1497
# coly008 # 95325 # 98371 FNBP C21.m/M2.2.88560  # 4493 # 1877
# coly009 # 95026 # 95048 FNBP C21.m/M2.18.728   # 4807 # 1534
# coly010 # 74933 # 96538 FNBP C21.m/M2.10.3936  # 4082 # 1426
# coly011 # 84559 # 97542 FNBP C21.m/M2.3.52488  # 4529 # 1268
# coly012 # 94748 # 95002 FNBP C21.m/M2.7.5622   # 5390 # 1473
# coly013 # 95385 # 98821 FNBP C21.m/M2.2.75440  # 6610 # 3169


coly004 and coly013 would appear to be up there in these ratings......

C
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General