The New Sudoku Players' Forum

[tarek]

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

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]

[Pat]

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

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

• oysterkite had already posted it in our forum on 2007.May.24
  
• the text in WikiPedia was only added on 2007.Aug.12
  -- and the anonymous writer is actually AMcDermot,
  who states "This puzzle has been released to the public domain with no licensing restrictions. I created the JPG image of it."
  

[champagne]

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

[tarek]

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

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.

----------

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

[gsf]

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

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

[tarek]

"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

[champagne]

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

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.

[tarek]

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

[champagne]

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.

[tarek]

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

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.

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

[champagne]

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

[tarek]

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

[ronk]

Where can I find the Ruud's canonicalizing algorithm.

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

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

[champagne]

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

[tarek]

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