The hardest sudokus

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

Postby AllanTrojan » Sat Oct 11, 2008 8:30 pm

StrmCkr wrote:Our ratings are only from solvers that don't rely on trial and error till completion.


How do you define 'trial and error'?

ALL algorithms use trial and error in some form or other.

(Don't tell me that a human can find a Jellyfish without trial and error!)

My program uses 'basic techniques'
a few fish
followed by a colouring algorithm
some forcing chains
and
for the most difficult problems
a 'backtracking' algorithm
that at most requires a search to level-3 depth.
AllanTrojan
 
Posts: 3
Joined: 11 October 2008

Postby StrmCkr » Sat Oct 11, 2008 10:28 pm

trial and error.

is plugging in a candaidate and following its "changes" till either a: stops and solves a puzzle. doesnt complete too much- no information gained.
B: shows a contradition.

from here you can back track which proved that test candidate A is wrong. and start over.

a human player does not plug in a candidate for a "fishy cycel".

it is a scan of the pm grid for the arangment of the pattern and apply the induced reduction based on said identifyed cover set. when they are identified.

there is a diffrence.

ALL algorithms use trial and error in some form or other
this is false as well. all algorithms scan the Pms for the program pattern and imply the reduction based on the cover set they found.

some "forcing chains" rely on
testing a candidate in a cell and based on permations they induce prove true or false or inflect identicall reductions at induced line of sight cells.

i am a manual solver
i have solved ever single one of these hard puzzle using non trial and error methods.

dont tell me ahuman cannot identify comlex patterns.

i do not implore guess and test methods.

i look for cover set limits. ie pattern restriction arangmentts.
and costrait propagation of pairs.

all ratings here in this thread and others
are based on none trial and error approaches.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Re: ER/EP/ED

Postby tarek » Sat Oct 11, 2008 11:59 pm

AllanTrojan wrote:I would be grateful if someone could explain to me
what the notations ER/EP/ED mean
and how they are calculated.

Welcome to the forum AllanTrojan,

These terms have been introduced in the Patterns Game. They represent different ratings by Sudoku Explainer 121 for the same puzzle. ER is the overall rating until complete solution, EP is the overall rating until the 1st uncovered cell, ED is the rating of the 1st Move.

You can review all of this including all the relevant links in the head post of the Patterns Game thread.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Sun Oct 12, 2008 3:37 am

StrmCkr wrote:all ratings here in this thread and others
are based on none trial and error approaches.


Well, there is a fine and blurry line as to what is deemed acceptable and what could be described as T&E !

I think most of the rating programs have an element of T&E.

Implication tabling, tagging, and any SE >7.1 has a T&E process [arguably]

champagnes solver uses processing time to attribute a difficulty.

"Suexrat9" gives the average node count for a back-tracking program to crack a puzzle.

gsf's "sudoku -q2" gives a value on the relative merits of a wide range of added proposition paired clues.

Easy puzzles are solved without any T&E.

We use Sudoku Explainer - but we do acknowledge that newer solving techniques arent considered when it allocates a "rating"

StrmCkr has "superhuman" solving power - and speed - and some of his solving techniques [fishy patterns excepted] also have this T&E component [which is completely OK in my book]:D

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: ER/EP/ED

Postby AllanTrojan » Sun Oct 12, 2008 2:35 pm

Thanks, Tarek, for the information.
Just what I wanted.
AllanTrojan
 
Posts: 3
Joined: 11 October 2008

Postby Obi-Wahn » Mon Oct 13, 2008 9:01 am

There was just a stupid bug in the Jelly check function of my solver. Luckily it only affected the rare case when the initial number of candidates was a multiple of 32.

So here's my current top list of puzzles that at least need more than one Jelly to solve:
Code: Select all
Puzzle___________________________________________________________________________  ITR_________  SE121 Label________________
1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1  1St-7Je-27Sw  11,8  coloin-04/13-1414
6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1  1St-7Je-17Sw  11,8  coloin-04/13-1600
1.......2.9.4...5...6...7...5.3.4......96.........8.4...2...6...3...9.8.7.......1  1St-5Je-11Sw  11,7  coloin-04/13-1426
1.......5.9.2...4...3...7...8.9.6.......5.......84..9...5...3...6...4.2.7.......1  7Je-23Sw      11,5  OW081008
1.......6.5.7...8...3...4.....5.8.9.....3.....8.92....6.....3...7...5.2...4.....1  6Je-19Sw      11,8  colx006
1.......6.5.7...8...3...4.....2.8.9.....1.....8.95....6.....3...7...5.2...4.....1  5Je-14Sw      11,7  OW081006
....71......9....1.6.4.2...5.....7...1...4..6..3....8..9.2....4..7...3..8......5.  4Je-23Sw      11,3  tarek071223170000-170
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1  3Je-11Sw      11,6  Easter Monster
6.......2.9.4...5...1...7...5.34........6.......8.5.4.2.....6...3...9.8...7.....1  2Je-14Sw      11,5  coloin-04/13-1397
6.......2.9.4...5...1...7...5.8.........15......9.3.4.7.....6...3...9.8...2.....1  2Je-14Sw      11,2  coloin-04/13-1535
........4.1...3.9.6...9.8.....3.5.....71......3...2.1...4...7...9.5...2.8.......6  2Je-12Sw      11,3  Tarek_Pearly_#3298
1.......7.4.6...8...3...5...8.9.........16......4.2.9...5...3...6...4.2.7.......1  2Je-11Sw      11,4  OW081007

ITR = Implication Table Rating


I will calculate the Jelly and Sword counts for the hardest step of each puzzle now and publish a complete list of Jelly+ puzzles.

Greetz, Obi
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby tarek » Mon Oct 13, 2008 2:30 pm

Obi-Wahn wrote:By altering the central box I managed to generate another hard one with 5 Jellies and 14 Swords for fifth place.
Code: Select all
OW081006
1 . .|. . .|. . 6
. 5 .|7 . .|. 8 .
. . 3|. . .|4 . .
-----+-----+-----
. . .|2 . 8|. 9 .
. . .|. 1 .|. . .
. 8 .|9 5 .|. . .
-----+-----+-----
6 . .|. . .|3 . .
. 7 .|. . 5|. 2 .
. . 4|. . .|. . 1
SE121 = 11.7
This puzzle was in my database ... Your method (& SE) saw in it what other methods didn't see:D

q2=95161; sx9=1418; sxt=668

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Sat Nov 01, 2008 2:41 pm

Two more contenders.......
Code: Select all
1.......2....1..3...5..34....2..1..4....8.7..6..9.......1..5.4.8.....5..9...6....

+---+---+---+
|1..|...|..2|
|...|.1.|.3.|
|..5|..3|4..|
+---+---+---+
|..2|..1|..4|
|...|.8.|7..|
|6..|9..|...|
+---+---+---+
|..1|..5|.4.|
|8..|...|5..|
|9..|.6.|...|
+---+---+---+   coly001

st9 :   4535 ,
sxt :   2651 ,
-q1 :   99001 FNBP C21.m/M3.416.1277
-q2 :   98788 FNBP C21.m/M3.416.1277

Code: Select all
.......1...6....23.2..3.4..8....5....3..1...4..96........9..7...1..2..4.5....8...

+---+---+---+
|...|...|.1.|
|..6|...|.23|
|.2.|.3.|4..|
+---+---+---+
|8..|..5|...|
|.3.|.1.|..4|
|..9|6..|...|
+---+---+---+
|...|9..|7..|
|.1.|.2.|.4.|
|5..|..8|...|
+---+---+---+  coly002

sx9 :   3383 ,
sxt :   2021 ,
-q1 :   96570 FNP  C21.m/M2.1.242757
-q2 :   99404 FNBP C21.m/M2.1.242757


C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby champagne » Sat Nov 01, 2008 10:12 pm

coloin wrote:Implication tabling, tagging, and any SE >7.1 has a T&E process
C


This is somehow an outdated debate, nevertheless, I can answer (late) to that point.

If my solver can not solve a puzzle using a "T&E free" set of rules, it gives up. I have no outlet to go ahead.

Up to now, this is limited to 2 puzzles, "Fata Morgana" and "Trompe l'oeil" but others will come.

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

Postby Mauricio » Mon Nov 10, 2008 6:52 am

How hard is really this sudoku?
Code: Select all
+-------+-------+-------+
| . . . | . . 1 | . . 2 |
| . . 3 | . . . | . 4 . |
| . 5 . | . 6 . | 7 . . |
+-------+-------+-------+
| . . . | 8 . . | . 7 . |
| . . 7 | . . 3 | 8 . . |
| 9 . . | . 5 . | . . 1 |
+-------+-------+-------+
| . . 6 | . 8 . | 2 . . |
| . 4 . | 6 . . | . . 7 |
| 2 . . | . . 9 | . 6 . |
+-------+-------+-------+ ED=11.3, ER=?

To solve it, I only need to suppose uniqueness and to use not more than hidden pair.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby champagne » Mon Nov 10, 2008 7:26 am

Mauricio wrote:How hard is really this sudoku?
To solve it, I only need to suppose uniqueness and to use not more than hidden pair.


Interesting animal.
Should receive a name if others confirm my diagnostic.:D

Not solved by my solver.:(
(to be sure this was not due to recent changes in the solver, I run several old versions of the program).

Using Allan Barker method, I did not find any eliminations before combining six floors:?:
(an option I added, the search was limited to five floors, enough for the toughest known).

Where does it come from??


You should publish your solution


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

Postby ronk » Mon Nov 10, 2008 7:38 am

Mauricio wrote:To solve it, I only need to suppose uniqueness and to use not more than hidden pair.

Perhaps something to do with diagonal symmetry and digit relabeling: 1-9, 3-5 and 6-7.

hidden answer wrote:These six digits may be removed as candidates in the diagonal. Gurth's symmetry, right?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Glyn » Mon Nov 10, 2008 8:48 am

ronk Excellent observation. Just leaving a naked pair and a naked triple to finish.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Mauricio » Mon Nov 10, 2008 9:36 am

ronk wrote:
hidden answer wrote:These six digits may be removed as candidates in the diagonal. Gurth's symmetry, right?

Completely right. That puzzle was the "hardest" of 1.8 million puzzles having the following properties:
a)Minimal
b)First move not a single
c)Each minirow/minicolumn has at most 1 given
d)Automorphic if reflexed along the main diagonal
If I did not have oversights in my search, those 1.8 M puzzles are all puzzles having those properties.
Last edited by Mauricio on Mon Nov 10, 2008 5:48 am, edited 1 time in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby champagne » Mon Nov 10, 2008 9:47 am

Hi all

This is a wonderful example. I suggested Allan to study it, but I doubt he finds a simple answer.

SK loop was already a very powerful way to go ahead in some puzzles, but this is still better if you consider that classical paths fail.

I think I got your point, may be not to the level necessary to teach it to my solver. Where is it described?

champagne

EDIT:

Thanks to Mike Barker and it's usefull index, I found the discussion. Very convicing.

For sure this is avery specific family of puzzles, but also very easy to identify.
champagne
2017 Supporter
 
Posts: 5683
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to General