## The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections
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.

tarek

Posts: 2650
Joined: 05 January 2006

### re: Qassim Hamza

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 --

Pat

Posts: 3550
Joined: 18 July 2005

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: 6246
Joined: 02 August 2007
Location: France Brittany

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

tarek

Posts: 2650
Joined: 05 January 2006

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

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

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

tarek

Posts: 2650
Joined: 05 January 2006

Hi tarek

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

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: 6246
Joined: 02 August 2007
Location: France Brittany

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

tarek

Posts: 2650
Joined: 05 January 2006

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,

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: 6246
Joined: 02 August 2007
Location: France Brittany

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

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 )

tarek

tarek

Posts: 2650
Joined: 05 January 2006

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 with other solutions
champagne
2017 Supporter

Posts: 6246
Joined: 02 August 2007
Location: France Brittany

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

tarek

Posts: 2650
Joined: 05 January 2006

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 . . | . . . | . . 3Golden 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

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: 6246
Joined: 02 August 2007
Location: France Brittany

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

tarek

Posts: 2650
Joined: 05 January 2006

PreviousNext