The hardest sudokus

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

Postby tarek » Mon Mar 03, 2008 11:35 pm

I finally found where this "Qassim Hamza" hardest sudoku allegation came from.

AMcDermot on wikipedia wrote:More recently, an even more perplexing puzzle has been developed, which has become known as "Qassim Hamza". This puzzle has proven to be extremely daunting, and even an exhaustive application of all basic solution methods will not advance this puzzle towards a solution.


This can be found in "Exceptionally difficult Sudokus" of "Algorithmics of sudoku" on "Wikipedia", follow this link for a shortcut: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku

tarek

[Edit: corrected wiki writer's name]
Last edited by tarek on Tue Mar 04, 2008 7:52 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

re: Qassim Hamza

Postby Pat » Tue Mar 04, 2008 2:36 pm

tarek wrote:I finally found where this "Qassim Hamza" hardest sudoku allegation came from.

rogue wiki writer wrote:More recently, an even more perplexing puzzle has been developed, which has become known as "Qassim Hamza". This puzzle has proven to be extremely daunting, and even an exhaustive application of all basic solution methods will not advance this puzzle towards a solution.



This can be found in "Exceptionally difficult Sudokus" of "Algorithmics of sudoku" on "Wikipedia", follow this link -- http://en.wikipedia.org/wiki/Algorithmics_of_sudoku

User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby champagne » Tue Mar 04, 2008 4:25 pm

I don't know what give usual rating ratios, but this is a puzzle not requesting level 4 in full tagging. solved in 17 seconds to compare to about 95 seconds to Golden Nugget.

Not an easy puzzle, but far from the top list of hardest
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Tue Mar 04, 2008 4:27 pm

Thanks Pat, just to remind everyone that it was posted after & is isomorphic to Ocean's #5 puzzle of the so called gold list.

Ocean wrote:Check for equivalence with this one, the so-called gold list #5:
Code: Select all
001002000030040050600700800006000007010000030900000600007001008040030020000500900
(Posted 3 nov 2006, and stayed on top of ravel's hardest list for about one month.)
Curious about what path the puzzle has taken to appear in its new form, and how it got its new name. I am pleased that somebody has enjoyed playing with it.


----------

champagne wrote:I don't know what give usual rating ratios, but this is a puzzle not requesting level 4 in full tagging. solved in 17 seconds to compare to about 95 seconds to Golden Nugget.

This was posted long before the Easter Monster or the Golden Nugget, the period was when the AI Etana, Terek's Gyroscope #1, many of Ocean's puzzles were considered among the most difficult. It needs not just a correction of attribution but also an update.

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

Postby gsf » Thu Mar 06, 2008 2:29 am

tarek wrote:This was posted long before the Easter Monster or the Golden Nugget, the period was when the AI Etana, Terek's Gyroscope #1, many of Ocean's puzzles were considered among the most difficult. It needs not just a correction of attribution but also an update.

not to mention the brute force algorithm is a bad example
gsf on eureka last summer wrote:there's brute force and stupid force
the wiki article leans towards the latter
in particular, examining the cells with the least number
of choices first would dramatically change the wiki algorithm performance

which alludes to the algorithm's reliance on cell label order
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Sun Apr 13, 2008 7:33 pm

"Exceptionally difficult Sudokus" of "Algorithmics of sudoku" on "Wikipedia" has been receiving updates from people who do not frequent these parts of the internet.

follow this link for a shortcut: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku

I was hoping that someone with more wiki experience would try to correct & add some info.

Let's see if I can do something:)

tarek

Edit: Apparantly I can't. As I'm using a shared internet connection, the IP address has been blocked for abusing multiple accounts:D:(
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby champagne » Sun Apr 13, 2008 9:45 pm

Hi tarek

I got to read your post late (for me) to-day.

If it is not easy for a native english speaker, I let you guess how tough it will be for a poor french guy to enter that discussion.

Just going thru the pre requisite file to post any edit will request a full day of carefull reading.

I am not sure I have enough free time to do it:D

BTW it seems difficult to pass Golden Nugget. Nothing new for a long time.

I have to say that it was a very challenging puzzle.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Mon Apr 14, 2008 12:47 pm

champagne wrote:I have to say that it was a very challenging puzzle.

I'm glad that enjoyed that challenge.

My intention regarding the wiki is that an updtae regrding the hardest discussed here would be mentioned there.....

As we haven't agreed on a proper rating... The List of puzzles Rated highly by all solvers should probably feature there (at the first instance, those which are rated by downloadable solver programs)

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

Postby champagne » Mon Apr 14, 2008 2:09 pm

tarek wrote
The List of puzzles Rated highly by all solvers should probably feature there (at the first instance, those which are rated by downloadable solver programs)



I fully agree with you. unhappily,

1) My program is written in C++, using Windows Object Library, which is not the proper way to share code,

2) I have no downloading procedure to share the exec file. May be next month.

3) I should make small adjustments (cancelling printfile for example), to use it as a rating program.

The best I can do for the time being is to deliver the results or to send the program as attached file in a mail to anybody willing to test its own files.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Mon May 19, 2008 2:59 pm

somewhere else, coloin wrote:Firstly, in response to tarek I only started searching for new hardest - my computor was inactive and I had a little idea - which once running wouldnt be stopped !
You little ideas are most welcome .... The last idea resulted in finding so many new hardest puzzles:D

somewhere else, coloin wrote:Im loathe to complicate matters to post a ream of probably useless puzzles, although I will post one which has 5 single clues and then has a massive apparent difficulty, we might learn from this puzzle.
that is why it was suggested that a service similar to gfroyle's can be started for hardest puzzles.

somewhere else, coloin wrote:I am also loathe to post random morphic versions of puzzles. My version of GN shows the puzzle in all its flawed symmetry. I wonder if it is worth suggesting a furthur canonicalizing pattern.
I've suggested that a modified form of Ruud's canonicalizing algorithm be used.
1. pattern canonicalization by
1.a. highest symmetry order with the smallest binary representitive
1.b. binary pattern minlex if no symmetry
2. clue normalization.
It will be slow but should unify matters (this would be good if added to gsf's solver:D )

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

Postby champagne » Mon May 19, 2008 7:43 pm

tarek wrote:I wonder if it is worth suggesting a furthur canonicalizing pattern
I've suggested that a modified form of Ruud's canonicalizing algorithm be used.


1)Where can I find the Ruud's canonicalizing algorithm.

I am interested in applying the standard form used in that forum.

2)BTW "Silver Plate" from coloin is now the hardest for my solver

Code: Select all
100000007020400060003000500090040000000062040000900800005000003060200080700001000     Silver Plate     


Higher processing time, longer print, at minimum in the same group, likely harder.

to compare:?::D with other solutions
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Mon May 19, 2008 8:15 pm

It wasn't documented....

If you download Sudocue .... it has an option to canonicalize puzzles using that algorithm.

1. replace clues with 1s
2. no clues with 0
3. minlex (I think row normal)
4. normalize clues in sequence (1,2,3....)

My suggestion is to add Symmetry to preserve & identify symmetrical patterns.

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

Postby ronk » Mon May 19, 2008 9:13 pm

champagne wrote:Where can I find the Ruud's canonicalizing algorithm.

See Ruud's post here. I agree with tarek's interpretation above.

tarek wrote:My suggestion is to add Symmetry to preserve & identify symmetrical patterns.

Agree here too. However, while obtaining maximal symmetry, it is also desirable to optionally ignore one box, which would presumably become the center box. For example, Golden Nugget could become ...

Code: Select all
 . . . | . . . | . 3 9                . . . | . . 1 | . . 2
 . . . | . . 1 | . . 5                . 3 . | . . . | . 4 .
 . . 3 | . 5 . | 8 . .                . . 5 | . 6 . | 7 . .
-------+-------+-------              -------+-------+-------
 . . 8 | . 9 . | . . 6                . . 6 | . . 5 | 8 . .
 . 7 . | . . 2 | . . .                . . . | 7 8 . | . . .
 1 . . | 4 . . | . . .                9 . . | 6 . . | . . .
-------+-------+-------              -------+-------+-------
 . . 9 | . 8 . | . 5 .                . . 7 | 1 . . | 5 . .
 . 2 . | . . . | 6 . .                . 4 . | . . . | . 9 .
 4 . . | 7 . . | . . .                2 . . | . . . | . . 3
Golden Nuggett (original)             diagonal symmetry modulo-2

... which has diagonal symmetry modulo 1 when ignoring box 5 -- clue at r4c3 instead of r5c3.

BTW, symmetrize might be a better term than canonicalize.

[edits: 1) Had the clues out of order; 2) Found a better row minlex; 3) transposed the pattern.]
Last edited by ronk on Tue May 20, 2008 6:04 am, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Mon May 19, 2008 10:28 pm

Thanks to tarek and ronk, I'll work on it.

I found the brief description of gsf canonical form here

I hope it is the right source
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Mon May 19, 2008 11:02 pm

ronk wrote:while obtaining maximal symmetry ....
maximal symmetry for asymmetrical puzzles is also something worthwhile trying. I know that it was duscussed in another thread. I couldn't remeber an algorithm surfacing from the discussions though.

The algorithm I have in my mind is a tedious backtracking plug/unplug excercise for each grid shuffle. the result would be a pattern minlex with (Symmetry order X minus least number of violating clues)

champagne,
You need to visit also the programmers forum. I do not have the links but that is where I found how it's done.

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

PreviousNext

Return to General