Cracking”The World’s Hardest Sudoku Puzzle” with XSLT in less than 1.5 seconds

Update: Andrew Welch found out that he had been referring not to the genuine AI Escargot puzzle:

  

While this is considered to be a harder puzzle for humans, both our XSLT solvers had less trouble and took less time (Andrew’s did decrease dramatically) on the new AI Escargot.

Times for solving the "genuine AI Escargot":

DN:  1.302 seconds

AW: 1.760  seconds


If you, like me, have missed last November’s story of a a Finnish mathematician claiming to create the most difficult Sudoku-puzzle known so far, you’d probably try to check whether such a claim was likely to be true.

Both I and Andrew Welch are big fans of XSLT programming, putting it to use for solving seemingly strange kinds of problems, Sudoku-puzzles included. For a long time we have been rivals each trying to outperform the solution of the other. Thus both of us managed to speed up our initial creations literally hundreds of times.

At the end we achieved a state of a tie-in, in which each solution was shown to outperform the other for certain classes of Sudoku-puzzles and to lag behind significantly in other cases.

My own explanation has been that Andrew’s solution is much faster for simple Sudoku-puzzles (usually taking only a fraction of a second), while needing potentially tens of seconds for more complicated Sudoku-puzzles, on which my solution needed not more than two seconds. Of course, I cannot seriously claim this statement is correct, because no one can define what a "simple" and "complex" Sudoku-puzzle is.

Anyway, when yesterday Andrew sent me the link to the

 
AI Escargot
,

 

 

the first thing I did was to run my XSLT 2.0 solution and measure the time:

       It took 1.432 seconds on a 3MHz, 2GB RAM Pentium IV desktop using Saxon 8.9.2J.

In the meantime Andrew reported on his blog that his solution took about 24 seconds — probably on a less powerful computer, as on mine it runs for 17.172 seconds.

I have an idea how to combine our two solutions into one that will have most of the strengths and almost none of the shortcomings of each of the two separate ones  — this is a topic of a future article.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s